Codeforces #893 : Div2 E2. Rollbacks (Hard Version)

こういう問題、なんかCodeforcesっぽく感じる。
https://codeforces.com/contest/1858/problem/E2

問題

整数列Aを考える。初期状態で空である。
以下のクエリに順次答えよ。

• Aの末尾にxを追加する
• Aの末尾k要素を削除する
• 直前の、追加または削除クエリを巻き戻す
• A中のdistinctな要素数を答える

解法

整数列Bを、
B[i]:= A中にiが1個以上あるなら1、そうでないなら0
とする。BをBITで管理すれば、4つ目のクエリには高速で答えられる。

あとは実行履歴を持ちながら愚直にクエリをこなしていけばよい。
削除クエリは重いものの、均しで追加クエリ以上の回数は行われないので余り気にしなくてよい。

int Q;
int A[1010101];
int R;
set<int> S[1010101];

template<class V, int ME> class BIT {
public:
	V bit[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) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	vector<pair<int,int>> hist;
	
	MINUS(A);
	
	cin>>Q;
	while(Q--) {
		cin>>s;
		if(s=="+") {
			cin>>x;
			y=A[R];
			hist.push_back({0,y});
			if(y!=-1) {
				bt.add(*S[y].begin(),-1);
				S[y].erase(R);
				if(S[y].size()) bt.add(*S[y].begin(),1);
			}
			A[R]=x;
			if(S[x].size()) bt.add(*S[x].begin(),-1);
			S[x].insert(R);
			bt.add(*S[x].begin(),1);
			R++;
		}
		else if(s=="-") {
			cin>>x;
			R-=x;
			hist.push_back({1,x});
		}
		else if(s=="!") {
			if(hist.back().first==1) {
				R+=hist.back().second;
			}
			else {
				x=hist.back().second;
				R--;
				y=A[R];
				bt.add(*S[y].begin(),-1);
				S[y].erase(R);
				if(S[y].size()) bt.add(*S[y].begin(),1);
				
				A[R]=x;
				if(x>=0) {
					if(S[x].size()) bt.add(*S[x].begin(),-1);
					S[x].insert(R);
					bt.add(*S[x].begin(),1);
				}
			}
			hist.pop_back();
		}
		else {
			cout<<bt(R-1)<<endl;
		}

		
	}
}

まとめ

これ系のデータ構造ゲー、あまり面白さを感じないな…。