Codeforces #740 Div1 : D. Top-Notch Insertions

ライブラリ部分を除くと、コードは余り長くない。
https://codeforces.com/contest/1558/problem/D

問題

N要素の数列Aに対し、以下のソート手順を考える。
i=2以降、iをインクリメントしながら下記を行う。

• A[i-1]≦A[i]なら何もしない
• A[i-1]＞A[i]の場合、j＜iかつA[j]＞A[i]となる最小のjを求め、A[i]をA[j]に移動する(A[j]～A[i-1]は、A[j+1]～A[i]にシフトする)。

ここで、ある1以上N以下の値を取るN要素の順列Aに対し、上記手順を実行したきの(i,j)の対の列が与えられる。
そのようなソート順を取るAは何通りか。

問題

ソート時(i,j)という操作が成されたということは、A[j-1]＜A[j]ということである。
ソート時の(i,j)の列を後ろから辿り、BITの二分探索を行いながらそのように値が等しくなりえない隣接要素の位置・個数を求めよう。

等しくてもよい隣接要素の個数がSなら、重複組み合わせの要領でAの数字がインクリメントされる位置を考えると、解はBinom(N+S,S)となる。

int T;
int N,M;
int X[202020],Y[202020];
const ll mo=998244353;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[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) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,19> bt;

ll comb(ll N_, ll C_) {
	const int NUM_=500001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

int style[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=300000;i++) bt.add(i,1);
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&M);
		int same=N-1;
		FOR(i,M) {
			scanf("%d%d",&X[i],&Y[i]);
			X[x]=y;
		}
		
		map<int,int> style;
		vector<int> ev;
		for(i=M-1;i>=0;i--) {
			x=bt.lower_bound(Y[i]);
			bt.add(x,-1);
			ev.push_back(x);
			if(x>1&&style.count(x-1)==0) style[x-1]=0;
			if(style.count(x)==0) style[x]=1,same--;
		}
		
		FORR(x,ev) bt.add(x,1);
		_P("%d\n",(int)comb(N+same,same));
		
	}
}

まとめ

Div1Dの割には簡単。1750ptとかではないのね。