TopCoder SRM 755 Div1 Hard DejaVu

これもCodeforcesなら1250ptのCぐらいじゃないですかね…。
https://community.topcoder.com/stat?c=problem_statement&pm=15420

問題

整数列Mが与えられる。
この部分列のうち、ちょうど２回だけ登場する数字がいくつあるか、最大値を求めよ。

解法

範囲加算と最大値を求められるSegTreeで解く。
左端を端から走査しつつ、それぞれ最適な右端を求めることを考えよう。

今左端が固定されているとする。
ある数値vの左端以降の登場位置が、p[0],p[1],p[2]...だったとする。
その場合、右端の位置が[p[1],p[2]-1]の範囲内であった場合、その数字は２回登場することになる。
よって、SegTreeで[p[1],p[2]-1]の範囲に1加算しよう。
この処理を事前に全vに対し行っておく。

左端を1個ずらすと、それにより1個ずらして追い出された数字に対して、p[0],p[1],p[2]...がスライドするので、対応してSegTreeに1加減算すればよい。

ll A[202020];
ll M[202020];
map<int,vector<int>> memo;
int pre[201010];
int nex[201010];

static ll const def=-1<<20;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	void init(){
		val.resize(NV*2,0); ma.resize(NV*2,0);
	}
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<int,1<<20> st;

class DejaVu {
	public:
	int mostDejaVus(int N, int seed, int R) {
		A[0]=seed;
		int i;
		for(i=1;i<N;i++) A[i]=(A[i-1]*1664525+1013904223)%4294967296;
		memo.clear();
		FOR(i,N) {
			M[i]=A[i]%R;
			memo[M[i]].push_back(i);
			pre[i]=-1;
			nex[i]=N;
		}
		nex[N]=N;
		st.init();
		FORR(m,memo) {
			vector<int> V=m.second;
			if(V.size()>=2) {
				for(i=0;i<V.size();i++) {
					if(i) pre[V[i]]=V[i-1];
					if(i+1<V.size()) nex[V[i]]=V[i+1];
				}
				int f=V[0];
				st.update(nex[f],nex[nex[f]],1);
			}
		}
		int ma=0;
		FOR(i,N) {
			ma=max(ma,st.getval(0,N));
			st.update(nex[i],nex[nex[i]],-1);
			st.update(nex[nex[i]],nex[nex[nex[i]]],1);
		}
		return ma;
		
	}
}

まとめ

なんか今回Codeforcesっぽいよな。