Codeforces ECR #013 : F. Lena and Queries

うーん…
http://codeforces.com/contest/678/problem/F

問題

初期状態で整数ペアの集合Sが空であるとする。
以下のクエリ計N個を処理せよ。

• Sに入力値(a,b)を加える。
• Sからi番目のクエリで追加した値を取り除く。
• 入力値qが与えられる。(x,y)∈Sについてx*q+yの最大値を求めよ。

解法

基本的にはConvexHullTrickで解く。
ただし入力順が(a,b)でソートされてなかったり値の削除があるのでCHTで扱いにくい。

そこで平方分割と併用しよう。
以下のコードではDIV=2500個ごとにクエリを分割し、クエリをDIV個処理するたびに、以後DIV個のクエリ中で削除・削除されないS中の値のみConvex Hullを求める。
DIVの値はかなり慎重に決める必要があり、300程度から徐々に増やして2500でようやくTLEを回避した。
その意味でもう少し定数倍高速化が必要だったかもしれない。

const int DIV=2500;
int N;
ll T[303030],A[303030],B[303030];
int del[303030];
vector<int> cur,willadd;

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	int cmptype=1; // 0-min 1-max
	V calc(pair<V,V> p, V x) {
		return p.first*x+p.second;
	}
	int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) { // max or min
		return cmptype^((B.second-C.second)*(B.first-A.first)<=(A.second-B.second)*(C.first-B.first));
	}
	void add(V a, V b) { // add ax+b
		Q.push_back({a,b});
		int v;
		while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
			Q[v-2]=Q[v-1], Q.pop_back();
	}
	void add(vector<pair<V,V>> v) {
		sort(v.begin(),v.end());
		if(cmptype==1) reverse(v.begin(),v.end());
		for(auto r=v.begin();r!=v.end();r++) add(r->first,r->second);
	}
	
	
	V query(V x) {
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			((calc(Q[M],x)<=calc(Q[M+1],x))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>T[i];
		if(T[i]==1) cin>>A[i]>>B[i];
		if(T[i]==2) cin>>A[i], A[i]--;
		if(T[i]==3) cin>>A[i];
	}
	
	for(i=0;i<N;i+=DIV) {
		willadd.clear();
		ConvexHull<ll> ch;
		
		for(j=i;j<min(N,i+DIV);j++) if(T[j]==2 && A[j]<i) willadd.push_back(A[j]), del[A[j]]=2;
		vector<pair<ll,ll>> V;
		FORR(r,cur) if(del[r]==0) V.push_back({A[r],B[r]});
		ch.add(V);
		
		for(j=i;j<min(N,i+DIV);j++) {
			if(T[j]==1) willadd.push_back(j);
			if(T[j]==2) del[A[j]]=1;
			if(T[j]==3) {
				ll ma=-1LL<<60;
				FORR(r,willadd) if(del[r]!=1) ma=max(ma,A[r]*A[j]+B[r]);
				if(V.size()) ma=max(ma,ch.query(A[j]));
				if(ma==-1LL<<60) cout<<"EMPTY SET"<<endl;
				else cout<<ma<<endl;
			}
		}
		
		FORR(r,willadd) if(del[r]==0) cur.push_back(r);
		
	}
}

まとめ

平方分割で分割数ミスると落ちる問題好きじゃない…。