一眼看去树套树啊,我可能是数据结构学傻了……
是应该去学一下莫队进阶的东西了。
上面那个东西我没有打,所以这里没有代码,而且应该也不难理解吧。
这么多平衡树就算了,不过线段树还是挺好打的。
正解3:
主席树啊,其实并不需要再加一个树状数组,因为每次修改只影响两个,暴力修改就行了。
正解4:
分块(就是暴力但是跑的好快啊)。
下面是真正的正解:
将兔子以颜色为第一关键字,位置为第二关键字排序,通过二分就能找到一段区间内某种颜色兔子的数量。
至于修改,只需要找到两只兔子,将其位置互换即可,因为两只兔子是相邻的,所以并不会破坏有序性。
1 #include2 #include 3 #include 4 #include 5 #include 6 #define LL long long 7 #define int LL 8 #define MAXN 300010 9 using namespace std;10 int n,m,b[MAXN];11 const int INF=0;12 pair a[MAXN];13 inline int read();14 signed main()15 {16 // freopen("in.txt","r",stdin);17 18 n=read(),m=read();19 for(int i=1;i<=n;i++)a[i].first=read(),a[i].second=i,b[i]=a[i].first;//a[i]=read();20 sort(a+1,a+n+1);21 int op,x,l,r,c;22 for(int i=1;i<=m;i++)23 {24 op=read();25 if(op==1)26 {27 l=read(),r=read(),c=read();28 int len1=(upper_bound(a+1,a+n+1,make_pair(c,r))-a),len2=(lower_bound(a+1,a+n+1,make_pair(c,l))-a);29 printf("%lld\n",len1-len2);30 }31 else32 {33 x=read(); 34 if(b[x]==b[x+1])continue;35 int tem1=lower_bound(a+1,a+n+1,make_pair(b[x],x))-a,tem2=lower_bound(a+1,a+n+1,make_pair(b[x+1],x+1))-a;36 swap(a[tem1].second,a[tem2].second);swap(b[x],b[x+1]);37 }38 }39 }40 inline int read()41 {42 int s=0,f=1;char a=getchar();43 while(a<'0'||a>'9'){ if(a=='-')f=-1;a=getchar();}44 while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}45 return s*f;46 }