Codeforces #348 Div1. D. Little Artem and Time Machine

途中でNの上限が下がったけど、下がらなかったらTLEしてたかな…。
http://codeforces.com/contest/668/problem/D

問題

multisetを時間順を入れ替えながら操作することを考える。
以下のN通りの操作を1つずつ行え。
ただし行う場合はその都度T[i]が示す時間にワープして行う。

• multisetにX[i]を1つ加える
• multisetからX[i]を1つ取り除く
• multiset中のX[i]の数をカウントする。

解法

異なるX[i]のクエリ群は互いに関係しないので、まずクエリ群をX[i]で分類しよう。
その後、同じX[i]を持つクエリ群に対しT[i]で座標圧縮し、BITで(圧縮後の)T[i]に対し

• 1増加
• 1減少
• T[i]以下の総和計算

を行えばよい。

int N;
int A[1010101];
int T[1010101];
int V[1010101];
vector<int> E[1010101];
int R[1010101];

template<class V> class BIT_var {
public:
	int ME;
	vector<V> bit;
	void init(int count) {
		ME=1;
		while((1<<ME)<=count*2) ME++;
		bit.clear();
		bit.resize(1<<ME);
	}
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) scanf("%d%d%d",&A[i],&T[i],&V[i]);
	vector<int> VM;
	FOR(i,N) VM.push_back(V[i]);
	sort(ALL(VM));
	VM.erase(unique(ALL(VM)),VM.end());
	FOR(i,N) {
		V[i]=lower_bound(ALL(VM),V[i])-VM.begin();
		E[V[i]].push_back(i);
	}
	FOR(i,1010000) if(E[i].size()) {
		vector<int> TM;
		FORR(r,E[i]) TM.push_back(T[r]);
		sort(ALL(TM));
		TM.erase(unique(ALL(TM)),TM.end());
		FORR(r,E[i]) T[r]=lower_bound(ALL(TM),T[r])-TM.begin();
		
		BIT_var<int> bit;
		bit.init(E[i].size());
		FORR(x,E[i]) {
			if(A[x]==1) bit.add(T[x],1);
			if(A[x]==2) bit.add(T[x],-1);
			if(A[x]==3) R[x]=bit(T[x]);
		}
	}
	FOR(i,N) if(A[i]==3) _P("%d\n",R[i]);
	
}

まとめ

面倒だけど難しくはないね。いつものDよりずっと簡単。