Codeforces #728 Div1 : D. Inverse Inversions

こういうのとっさに解ける気しないな…。
https://codeforces.com/contest/1540/problem/D

問題

1～Nの順列Pに対し、数列Bは以下のように定義される。

• B[i]は、j＜iかつP[j]＞P[i]であるjの数。

数列Bが与えられる。以下のクエリに順次答えよ。

• Bの1要素を指定した値で上書きする。
• 添字iが指定されるので、Bを生成するPに対し、P[i]を答えよ。

解法

数列Cを以下のように定義する。

• C[i]は、i＜jかつP[j]＞P[i]であるjの数。これはj＜iかつP[j]＜P[i]であるjの数と等しい。

するとC[i]=i-B[i]となる。以後、BではなくCを管理しよう。
P[i]を求めるには、C[i]は、P[i]はP[0...i]の中において小さい順に何番目の数であるかを示す。
以後、P[i+1]...P[N-1]にP[i]未満の要素がいくつあるかを求めれば、P[i]を求めることができる。

この手順を平方分割する。
分割したブロック毎に、「ブロックの手前でprefix中小さい順にn番目の要素が、ブロック内の要素も含めるとn'番目になる」という情報が高速に求められれば良い。
これには、ブロック内の要素がprefix内で小さい順に何個目に当たるかという配列を持っておけば、二分探索でnからn'を計算できる。

int N,Q;
int C[101010];
const int D=200;
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;}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,18> bt;
vector<int> add[101010];


void update(int b) {
	int L=b*D;
	int R=min((b+1)*D,N);
	add[b].clear();
	int i;
	for(i=L;i<R;i++) {
		int tar=bt.lower_bound(C[i]);
		add[b].push_back(tar);
		bt.add(tar,1);
	}
	FORR(tar,add[b]) bt.add(tar,-1);
	sort(ALL(add[b]));
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		C[i]=i-x;
	}
	FOR(j,N+1) if(j) bt.add(j,1);
	FOR(i,N/D+5) update(i);
	
	
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>i>>x;
			i--;
			C[i]=i-x;
			update(i/D);
		}
		else {
			cin>>x;
			x--;
			int loc=C[x];
			for(i=x+1;i<min(N,(x/D+1)*D);i++) if(C[i]<=loc) loc++;
			for(i=x/D+1;i<N/D+2;i++) loc+=lower_bound(ALL(add[i]),loc+1)-add[i].begin();
			cout<<loc+1<<endl;
			
		}
	}
	
}

まとめ

平方分割はいつもブロック数を決めるのに手間取る。