IOI 2011 Elephants

http://www.ioi-jp.org/ioi/2011/tasks/day2/elephants_jpn.pdf

書いた。むずかった
平方分割、と言われても自明に思いつく程簡単でもない＆実装もそこそこ
（まあでも平方分割の実装としては標準的な気がする）

象を最初の方からB個ずつ分ける。
それぞれの象iについて、

• 象iより後ろの同じバケット内の象を被うために必要なカメラ
• その時に、最後のカメラはどこまで被えるか

を記憶。
あとは更新を頑張る。バケットが偏ってきたら全部破壊してやり直す
更新もしゃくとり使うとfasterでgood
Bをうまいこと決めると、O(N^1.5logN)ぐらいになります
subtask5は10秒ぐらいかかるので多分TLEです

API使わないで、入力データから直接読み込み＆プログラム内でチェックしてます

using namespace std;
static const int INF =1000000005;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
int n,l,m;
int pos[200000];
pi seq[200000];
int belong[200000],rank[200005],size[200005];
int need[200000],reach[200000];
static const int B=300;
int each[200000/B+2][B*2+5];
int bn;

void build(int k){
	int j=size[k]-1;

	for(int i=size[k]-1;i>=0;--i){
		int id=each[k][i],jd=each[k][j];
		while(j>i && pos[jd]>pos[id]+l){
			--j;
			jd=each[k][j];
		}
		if(j+1<size[k]){
			jd=each[k][j+1];
			need[id]=need[jd]+1;
			reach[id]=reach[jd];
		}else{
			need[id]=1;
			reach[id]=pos[id]+l;
		}
	}
}
void build(){
	for(int i=0;i<n;++i) seq[i]=make_pair(pos[i],i);
	sort(seq,seq+n);
	for(int i=0;i<n;++i){
		belong[seq[i].second]=i/B;
		rank[seq[i].second]=i%B;
		each[i/B][i%B]=seq[i].second;
	}
	bn=(n-1)/B+1;
	pos[n]=INF;
	for(int i=0;i<bn;++i) size[i]=0;
	for(int i=0;i<n;++i) size[belong[i]]++;
	for(int i=0;i<bn;++i) build(i);
}
int main(){
	scanf("%d%d%d",&n,&l,&m);
	for(int i=0;i<n;++i){
		scanf("%d",&pos[i]);
	}
	int sub=0;
	while(n%B){
		pos[n++]=-INF-10;
		sub=1;
	}
	build();
	for(int hoge=0;hoge<m;++hoge){
		int i,a,ans;scanf("%d%d%d",&i,&a,&ans);
		int buck=0;
		for(int j=0;j<bn;++j) if(pos[each[j][0]]<=a){
			buck=j;
		}

		--size[belong[i]];
		++size[buck];
		int flag=0;
		for(int j=0;j<bn;++j) if(size[j]==0 || size[j]>B*2){
			pos[i]=a;
			build();
			flag=1;
			break;
		}
		if(!flag){
			++size[belong[i]];
			--size[buck];

			for(int j=rank[i];j<size[belong[i]]-1;++j){
				int nxt=each[belong[i]][j+1];
				each[belong[i]][j]=nxt;
				rank[nxt]--;
			}
			--size[belong[i]];
			build(belong[i]);

			pos[i]=a;

			belong[i]=buck;
			for(int j=0;j<size[buck]+1;++j) if(j==size[buck] || pos[each[buck][j]]>=a){
				for(int k=size[buck]-1;k>=j;--k){
					each[buck][k+1]=each[buck][k];
					rank[each[buck][k]]++;
				}
				++size[buck];
				each[buck][j]=i;
				rank[i]=j;
				break;
			}

			build(buck);
		}
		int res=0,cur=0;
		for(int j=0;j<bn;++j){
			res+=need[each[j][cur]];
			int r=reach[each[j][cur]];
			while(j<bn-1){
				int lb=-1,ub=size[j+1];
				while(ub-lb>1){
					int md=(ub+lb)>>1;
					if(pos[each[j+1][md]]<=r) lb=md;
					else ub=md;
				}
				if(lb+1==size[j+1]){
					++j;
					continue;
				}
				cur=lb+1;
				break;
			}
		}
		res-=sub;
		if(res!=ans){
		printf("%d %d\n",res,ans);

				puts("ERROR");
		}


	}

	return 0;
}