TopCoder SRM 832 : Div1 Hard PopChartDominance

MediumよりHardの方が楽では…。
https://community.topcoder.com/stat?c=problem_statement&pm=17670

問題

N要素の整数列Aが与えられる。
区間[L,H]で構成されるクエリがQ個与えられるので、それぞれ以下の値を求めよ。

A[t]が同じ値となるtのうち、[L,H]の範囲内で2個以上該当するtがある場合、最大値と最小値の差を取る。
A[L...H]のうちそれぞれ異なる値に対し、上記値を取ったものの和を求めよ。

解法

A[x]=yとなる添え字xを並べた数列をXとする。
今X[i]＜L＜X[i+1]かつX[j]＜H＜X[j+1]となるケースを考える。
この時、解に計上されるのはX[j]-X[i+1]である。

もしLを固定し、Hを動かすことを考えると、HがX[i+2]、X[i+3]、X[i+4]以上…と大きくなるごとに、(X[i+2]-X[i+1])、(X[i+3]-X[i+2])、(X[i+4]-X[i+3])が解に計上されると考えることができる。
これは、数列のprefix sumを取れるBITを用いれば、各Hに対しO(logN)で容易に計算できる。

ここまでを踏まえ、クエリをL順にソートし、Lを小さい順に走査しながらBITを更新しつつBITで上記和を求めていこう。

なお、自分は最初Mo's Algorithmの適用を考えたが、これだとちょっとTLに間に合わなかった。

vector<int> ev[303030];
deque<int> D[303030];
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;}
};
BIT<ll,20> bt;
const ll mo=1000000007;


class PopChartDominance {
	public:
	
	int count(int N, int Q, vector <int> Aprefix, int Alimit, vector <int> Lprefix, vector <int> Hprefix, int minQL, int maxQL, int seed) {
		ll state = seed;
		int i;
		vector<ll> A,L,H;
		FORR(a,Aprefix) A.push_back(a);
		while(A.size()<N) {
			state = (state * 1103515245 + 12345) % (1LL<<31);
		    A.push_back(state%Alimit);
		}
		
		FORR(a,Lprefix) L.push_back(a);
		FORR(a,Hprefix) H.push_back(a);
		while(L.size()<Q) {
			state = (state * 1103515245 + 12345) % (1LL<<31);
			ll ql = minQL + (state % (maxQL-minQL+1));
			state = (state * 1103515245 + 12345) % (1LL<<31);
			ll lo = state%(N-ql+1);
		    L.push_back(lo);
		    H.push_back(lo+ql);
		}
		
		ZERO(bt.bit);
		FOR(i,N) D[i].clear(), ev[i].clear();
		FOR(i,N) {
			if(D[A[i]].size()) bt.add(i,i-D[A[i]].back());
			D[A[i]].push_back(i);
		}
		FOR(i,Q) {
			ev[L[i]].push_back(i);
		}
		ll ret=0;
		FOR(i,N) {
			FORR(e,ev[i]) {
				ll a=bt(H[e]-1)%mo;
				(ret+=a*(e+1))%=mo;
			}
			D[A[i]].pop_front();
			if(D[A[i]].size()) {
				bt.add(D[A[i]][0],i-D[A[i]][0]);
			}
		}
		return ret;
	}
}

まとめ

600ptと900ptが並ぶと、時々難易度の逆転が起きるよな…。