第九回 アルゴリズム実技検定 : M - 名前の変更

ゴリ押し感がある。
https://atcoder.jp/contests/past202112-open/tasks/past202112_m

問題

N個の文字列が与えられる。
以下のクエリをすべて対応した後、各文字列が何になったかを答えよ。
なお、各文字列は5文字以下である。

• 辞書順X番目の文字列をTにする

解法

文字列が5文字以下なので、高々(27^5)以下の整数値で表せる。
そこで文字列とindexを１つの64bit値にエンコードし、Trieに乗せよう。
Trie上を二分探索すれば、置き換えるべき文字列のindexがわかる。

struct BinarySumTrie {
	BinarySumTrie *nex[2];
	ll v;
	BinarySumTrie() {
		nex[0]=nex[1]=NULL;v=0;
	}
	void add(ll s,ll val,int pos=60) {
		v += val;
		if(pos>=0) {
			int c=(s>>pos)&1;
			if(!nex[c]) nex[c]=new BinarySumTrie();
			nex[c]->add(s,val,pos-1);
		}
	}
	ll get(ll s,int pos=60) { // sum [0,s-1]
		if(pos<0) return 0;
		int c=(s>>pos)&1;
		if(c) return (nex[0]?nex[0]->v:0)+(nex[1]?nex[1]->get(s,pos-1):0);
		else return (nex[0]?nex[0]->get(s,pos-1):0);
	}
	ll lower_bound(ll v,int pos=60) { // sum [0,s-1]
		if(pos<0) return 0;
		if((nex[0]?nex[0]->v:0)>=v) {
			return nex[0]->lower_bound(v,pos-1);
		}
		else {
			v-=(nex[0]?nex[0]->v:0);
			return (1LL<<pos)|(nex[1]?nex[1]->lower_bound(v,pos-1):0);
		}
	}
};

int N,Q;
string S[101010];
map<string,int> M;
BinarySumTrie bst;

ll encode(string S,int id) {
	S=S+"`````";
	ll cur=0;
	int i;
	FOR(i,5) cur=cur*27+S[i]-'`';
	return (cur<<20)|id;
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>S[i];
		bst.add(encode(S[i],i),1);
	}
	FOR(i,Q) {
		int X;
		string T;
		cin>>X>>T;
		ll v=bst.lower_bound(X);
		bst.add(v,-1);
		v=v&((1<<20)-1);
		S[v]=T;
		bst.add(encode(S[v],v),1);
	}
	FOR(i,N) cout<<S[i]<<" ";
	cout<<endl;
}

まとめ

pb_dsはいまいち使い方覚えてないんだよな。