TopCoder SRM 747 Div1 Hard RochesterSequence

勉強になりました。
https://community.topcoder.com/stat?c=problem_statement&pm=15288

問題

あるN要素の数列AがRochester列であるとは以下を意味する。

• Nが偶数である。
• (0-indexedにおいて) i＜N/2-1であるiに対し、A[i]+A[N-1-i]≦A[i+1]+A[N-1-(i+1)]

ここで、数列Bが与えられる。
ここからいくつかの要素を取り除きRochester列を構築したい。

そのために取り除く最小要素数と、その取り除き方の組み合わせを求めよ。

解法

• dp(L,R) := B[L...R]の部分列のうち、B[L]とB[R]は先頭・末尾に含み、Rochester列であるようなものにおける、要素数の最大数とその組み合わせ数

とする。Rochester列として次にどの要素をBから取り込むか…を考えると、L'＜L'かつR＜R'であるL',R'に対しdp(L',R')を総当たりする必要があるためO(N^4)となりTLEする。
この２次元領域における最大値を高速に求められれば良い…ということで２次元BITを用いよう。

まず、探索順を工夫する。
L,Rを順に埋めるのではなく、B[L]+B[R]の大きい順に(L,R)の対を総当たりしていく。
B[L]+B[R]が等しい(L,R)の対の場合、R-Lが小さいものを先に処理させたいので、以下では(B[L]+B[R])*1000+1000+L-Rの降順にソートした。

あとは、２次元BITの各ノードにおいて、(要素数, 組み合わせ数)のpairを値として持たせ、その加算を要素数が大きい方を取るとして定義させれば、上記２次元領域の最大値を容易に求められる。
ただ、加算の定義では減算が行えない（加算時に要素数が小さい方の情報が失われる）ため、SegTreeならまだしも２次元BITはそのまま載せることができない。
そこで、２次元BITの座標(L,N-R)にdp(L,R)の値を載せることにすると、dp(L,R)を求める際(0,0)-(L-1,N-R-1)の区間の総和を求めればよくなり減算が要らなくなる。

int mo=1000000007;

template<class V,int MA> class BIT_2d {
public:
	V val[1<<MA][1<<MA];
	BIT_2d(){ZERO(val);};
	V add(V a,V b) {
		if(a.first>b.first) return a;
		if(a.first<b.first) return b;
		a.second+=b.second;
		if(a.second>=mo) a.second-=mo;
		return a;
	}
	V total(int x,int y) {
		V s={0,0};
		for(int i=x+1;i>0;i-=i&-i) for(int j=y+1;j>0;j-=j&-j) s=add(s,val[i-1][j-1]);
		return s;
	}
	void update(int x,int y,V v) {
		for(int i=x+1;i<=1<<MA;i+=i&-i) for(int j=y+1;j<=1<<MA;j+=j&-j) val[i-1][j-1]=add(val[i-1][j-1],v);
	}
};
BIT_2d<pair<int,int>,10> bit;


class RochesterSequence {
	public:
	
	vector <int> solve(vector <int> S, int n, int a, int b, int m) {
		while(S.size()<n) S.push_back((1LL*S.back()*a+b)%m);
		ZERO(bit.val);
		vector<vector<ll>> C;
		int i,j;
		FOR(j,n) FOR(i,j) C.push_back({(S[i]+S[j])*1000LL+1000+i-j,i,j});
		sort(ALL(C));
		
		pair<int,int> ret={0,1};
		FORR(c,C) {
			int L=c[1],R=c[2];
			auto a=bit.total(L-1,n-R-1);
			if(a.first==0) a.second++;
			a.first+=2;
			ret=bit.add(ret,a);
			bit.update(L,n-R,a);
		}
		
		return {ret.first,ret.second};
		
	}
}

まとめ

減算使えないのにどうBITに載せればいいんだと思ったけど、座標を反転させるというテクがあったか。