kmjp's blog

競技プログラミング参加記です

Codeforces #457 Div2 D. Jamie and To-do List

これDiv2D…?
http://codeforces.com/contest/916/problem/D

問題

タスク名(文字列)と優先度(数値)の連想配列に関する以下のクエリを順次処理せよ。

  • 連想配列に指定したタスクを追加し、優先度を設定する。すでに連想配列中にそのタスクがある場合は優先度を上書きする。
  • 連想配列から指定したタスクを取り除く
  • 連想配列において、指定したタスクより小さな優先度のタスク数を答える
  • 指定された個数分前のクエリの状態に巻き戻す。

解法

文字列と数値の対、および優先度に関し区間和を求めることができればよいので、考え方としてはmapと加算に関するBITがあればよい。
ただし問題は巻き戻しである。
よって、mapとBITに関しそれぞれ永続木を作り、各クエリ実行後の状態を保存しよう。そうすると巻き戻しクエリに対応できる。
mapは文字列をキーとするのでTrieベースで作ればよい。

とはいえ永続データ構造は慣れてないので、結局Editorialとほぼ同じコードになってしまった。
勉強になりました。

template<int C> struct PersistentStringTrie {
	PersistentStringTrie *nex[C];
	ll v;
	int mp(char c) {
		if(c>='a' && c<='z') return c-'a';
		if(c>='A' && c<='Z') return c-'A'+26;
		assert(0); return 0;
	}
	PersistentStringTrie() {
		v=-1; for(int i=0;i<C;i++) nex[i]=NULL;
	}
	PersistentStringTrie(PersistentStringTrie* pst) {
		v=pst->v; for(int i=0;i<C;i++) nex[i]=pst->nex[i];
	}
	PersistentStringTrie* set(string& s,ll val,int pos=0) {
		PersistentStringTrie* pst=new PersistentStringTrie(this);
		if(pos>=s.size()) {
			pst->v=val;
		}
		else {
			int c=mp(s[pos]);
			if(!nex[c]) nex[c]=new PersistentStringTrie();
			pst->nex[c]=nex[c]->set(s,val,pos+1);
		}
		return pst;
	}
	ll get(string& s,int pos=0) {
		if(pos>=s.size()) return v;
		int c=mp(s[pos]);
		if(!nex[c]) return -1;
		return nex[c]->get(s,pos+1);
	}
};

struct PersistentBinarySumTrie {
	PersistentBinarySumTrie *nex[2];
	ll v;
	PersistentBinarySumTrie() {
		nex[0]=nex[1]=NULL;v=0;
	}
	PersistentBinarySumTrie(PersistentBinarySumTrie* pbst) {
		nex[0]=pbst->nex[0]; nex[1]=pbst->nex[1]; v=pbst->v;
	}
	PersistentBinarySumTrie* add(ll s,ll val,int pos=60) {
		PersistentBinarySumTrie* pbst=new PersistentBinarySumTrie(this);
		pbst->v += val;
		if(pos>=0) {
			int c=(s>>pos)&1;
			if(!nex[c]) nex[c]=new PersistentBinarySumTrie();
			pbst->nex[c]=nex[c]->add(s,val,pos-1);
		}
		return pbst;
	}
	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);
	}
};

int Q;
PersistentStringTrie<26> *st[101010];
PersistentBinarySumTrie *bst[101010];
string OP,A;
int X;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	st[0]=new PersistentStringTrie<26>();
	bst[0]=new PersistentBinarySumTrie();
	cin>>Q;
	for(i=1;i<=Q;i++) {
		cin>>OP;
		if(OP=="set") {
			cin>>A>>X;
			x = st[i-1]->get(A);
			st[i]=st[i-1]->set(A,X);
			if(x>=0) {
				bst[i]=bst[i-1]->add(x,-1)->add(X,1);
			}
			else {
				bst[i]=bst[i-1]->add(X,1);
			}
		}
		if(OP=="remove") {
			cin>>A;
			x = st[i-1]->get(A);
			st[i]=st[i-1]->set(A,-1);
			if(x>=0) {
				bst[i]=bst[i-1]->add(x,-1);
			}
			else {
				bst[i]=bst[i-1];
			}
		}
		if(OP=="undo") {
			cin>>X;
			st[i]=st[i-X-1];
			bst[i]=bst[i-X-1];
		}
		if(OP=="query") {
			st[i]=st[i-1];
			bst[i]=bst[i-1];
			cin>>A;
			x = st[i]->get(A);
			if(x<0) cout<<-1<<endl;
			else cout<<bst[i]->get(x)<<endl;
			
		}
	}
	
	
}

まとめ

この永続木の考え方、競技プログラミングではない別分野のアイデアと近いものがあるな。
ただそれだけにこれを永続データ構造と呼ぶことに違和感がある。
電源切れたら吹っ飛ぶじゃん…。