平方分割で通るのか…。
https://codeforces.com/contest/1093/problem/E
問題
1~NのPermutationとなる、2つの数列A,Bが与えられる。
以下のクエリに答えよ。
- 2つの区間[La,Ra]、[Lb,Rb]が指定されるので、A[La...Ra]とB[Lb...Rb]両方に含まれる要素数を答えよ。
- 指定されたBの2要素をswapする。
解法
数列の数字に具体的な意味はないので、Aが1~Nと昇順となるように数字を付け替えよう。
そうするとB[Lb...Rb]の間に[La...Ra]の範囲の数字が何個あるかを答える問題になる。
これは平方分割で解くことができる。
BをD=√N個のBucketに分け、それぞれBITを作ろう。
各BIT内には、1~Nの登場頻度0/1を書くようにする。
そうすると前者のクエリはBITをO(D)個と、Bucket境界に合わないO(D)を辿ることで[La,Ra]の範囲の数字の登場回数を求められる。
int N,M; int A[202020]; int B[302020]; const int DI=1000; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<int,18> bt[400]; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d%d",&N,&M); FOR(i,N) { scanf("%d",&x); A[x]=i; } FOR(i,N) { scanf("%d",&x); B[i]=A[x]; bt[i/DI].add(B[i],1); } while(M--) { scanf("%d",&i); if(i==1) { int LA,RA,LB,RB; scanf("%d%d%d%d",&LA,&RA,&LB,&RB); LA--; RA--; LB--; int num=0; while(LB<RB && LB%DI) { if(B[LB]>=LA && B[LB]<=RA) num++; LB++; } while(LB<RB && RB%DI) { RB--; if(B[RB]>=LA && B[RB]<=RA) num++; } while(LB<RB) { num+=bt[LB/DI](RA)-bt[LB/DI](LA-1); LB+=DI; } cout<<num<<endl; } else { scanf("%d%d",&x,&y); x--,y--; bt[x/DI].add(B[x],-1); bt[y/DI].add(B[y],-1); swap(B[x],B[y]); bt[x/DI].add(B[x],1); bt[y/DI].add(B[y],1); } } }
まとめ
BITでなくソート済み配列のlower_boundだと間に合わなかった。