Codeforces #1051 : Div2. D2. Inversion Graph Coloring (Hard Version)

Eまではかなりすんなり。
https://codeforces.com/contest/2143/problem/D2

問題

N要素の整数列Aが与えられる。
この部分列Bのうち、以下を満たすものは何通りか。

• Bを、順番を保って2つの部分列に分割した場合、どちらも昇順になる

解法

f(n,a,b) := Aのうちn要素目までをBに入れるかどうか試したとき、2つの部分列の末尾がa,b(a＜b)となるような組み合わせの数。

n+1要素目がxの場合、

• xをBに加える場合、
  • x≧bなら、f(n+1,a,x) += f(n,a,b)
  • b＞x≧aなら、f(n+1,x,b) += f(n,a,b)
• xをBに加えない場合、
• f(n+1,a,b) += f(n,a,b)

上記はDのBITを使えば、1要素あたりaまたはbを総当たりしてBITの操作をO(N)回で済む。

const ll mo=1000000007;
template<class V,int MA> class BIT_2d {
public:
	V val[1<<MA][1<<MA];
	BIT_2d(){ZERO(val);};
	V total(int x,int y) {
		V s=0;
		for(int i=x+1;i>0;i-=i&-i) for(int j=y+1;j>0;j-=j&-j) s+=val[i-1][j-1];
		return s%mo;
	}
	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]+=v)%=mo;
	}
};
BIT_2d<ll,11> dp;

int T;
int N;
int A[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		ZERO(dp.val);
		cin>>N;
		dp.update(0,0,1);
		FOR(i,N) {
			cin>>x;
			// x>=a>=bの場合、(a,b)->(x,b)に遷移
			for(j=0;j<=x;j++) {
				ll a=dp.total(x,j)-dp.total(x,j-1)+mo;
				dp.update(x,j,a);
			}
			// a>x>=bの場合、(a,b)->(a,x)に遷移
			for(j=x+1;j<=2000;j++) {
				ll a=dp.total(j,x)-dp.total(j-1,x)+mo;
				dp.update(j,x,a);
			}
		}
		ll ret=dp.total(2010,2010);
		cout<<ret%mo<<endl;
		
	}
}

まとめ

まぁここはすんなり。