Codeforces #307 Div2 E. GukiZ and GukiZiana

10秒って。
http://codeforces.com/contest/551/problem/E

問題

N要素の数列A[i]が与えられる。
関数F(A,y)とは、A[j]=A[i]=yとなる(i,j)の対におけるj-iの最大値とする。

A[i]に対し以下のクエリを処理せよ。

• L,R,xが与えられるので、A[L]～A[R]にxを加算する。
• yが与えられるので、F(A,y)を答える。

解法

平方分割を用いる。
例えば数列をDごとに分割して管理する。
区間r(A[r*D]～A[(r+1)*D-1]に対応)に対し、これまで適用された和S[r]を保持する。
また、各区間内のデータはソートしておき、lower_boundを用いて特定の値を持つ添え字を高速に求められるようにしておく。

• 区間更新のクエリについて
  • A[L..R]に含まれる区間ごとに処理する。
  • A[L..R]に区間全体が含まれるなら、S[r]+=xで区間全体の和を高速に処理する。
  • A[L..R]に区間の一部が含まれるなら、対応する区間内のA[i]を更新し、再度ソートする。
• F(A,y)のクエリについて
  • A[i]=A[j]=yとなる最小のi及び最大のjを求めたい。先頭の区間及び末尾の区間から順にyとなる要素を求めよう。
  • 区間r中にA[i]=yとなるものが存在するかは、区間内のソート済みデータからy-S[r]を求めればよい。

int N,Q;
ll A[505050];
const int DI=770;
ll pl[DI];
vector<pair<ll,int> > M[DI],M2[DI];

void rebuild(int id) {
	M[id].clear();
	M2[id].clear();
	
	for(int i=id*DI;i<(id+1)*DI && i<N;i++) {
		A[i]+=pl[id];
		M[id].push_back(make_pair(A[i],i));
		M2[id].push_back(make_pair(A[i],-i));
	}
	sort(ALL(M[id]));
	sort(ALL(M2[id]));
	pl[id]=0;
}

int getmi(ll V) {
	int i;
	FOR(i,DI) {
		ll t=V-pl[i];
		auto it=lower_bound(ALL(M[i]),make_pair(t,0));
		if(it==M[i].end()) continue;
		if(it->first!=t) continue;
		return it->second;
	}
	return -1;
}

int getma(ll V) {
	int i;
	for(i=DI-1;i>=0;i--) {
		ll t=V-pl[i];
		auto it=lower_bound(ALL(M2[i]),make_pair(t,-10000000));
		if(it==M2[i].end()) continue;
		if(it->first!=t) continue;
		return -it->second;
	}
	return -1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	MINUS(A);
	FOR(i,N) cin>>A[i];
	FOR(i,DI) rebuild(i);
	
	
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>l>>r>>x;
			l--;r--;
			
			if(l/DI==r/DI) {
				for(i=l;i<=r;i++) A[i]+=x;
				rebuild(l/DI);
			}
			else {
				int up=0;
				i=l/DI+1;
				while(l/DI!=i) A[l++]+=x, up++;
				if(up) rebuild(l/DI-1);
				while(l+DI<r) pl[l/DI]+=x, l+=DI;
				up=0;
				for(;l<=r;l++) A[l]+=x,up;
				rebuild(r/DI);
			}
		}
		else {
			cin>>y;
			int mi=getmi(y),ma=getma(y);
			if(mi<0) _P("%d\n",-1);
			else _P("%d\n",ma-mi);
			
		}
	}
}

まとめ

本番手を抜いてmap使ったらTLEした。
insert繰り返すケースは気を付けないとな。