Little Artem has invented a time machine! He could go anywhere in time, but all his thoughts of course are with computer science. He wants to apply this time machine to a well-known data structure: multiset.
Artem wants to create a basic multiset of integers. He wants these structure to support operations of three types:
But what about time machine? Artem doesn‘t simply apply operations to the multiset one by one, he now travels to different moments of time and apply his operation there. Consider the following example.
Note that Artem dislikes exceptions so much that he assures that after each change he makes all delete operations are applied only to element that is present in the multiset. The answer to the query of the third type is computed at the moment Artem makes the corresponding query and are not affected in any way by future changes he makes.
Help Artem implement time travellers multiset.
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of Artem‘s queries.
Then follow n lines with queries descriptions. Each of them contains three integers ai, ti and xi (1 ≤ ai ≤ 3, 1 ≤ ti, xi ≤ 109) — type of the query, moment of time Artem travels to in order to execute this query and the value of the query itself, respectively. It‘s guaranteed that all moments of time are distinct and that after each operation is applied all operations of the first and second types are consistent.
For each ask operation output the number of instances of integer being queried at the given moment of time.
6
1 1 5
3 5 5
1 2 5
3 6 5
2 3 5
3 7 5
1
2
1
3
1 1 1
2 2 1
3 3 1
0
/* 对于只有一个value的情况，可以用树状数组，以时刻为位置（时刻必须离散化），在t时刻添加一个value就是在t位置+1，在t时刻删除一个value就是在t位置-1，在t时刻查询value出现的次数就是查询[1,t]区间和 对于value不同的情况，要把不同的value分开做，每做完一个value就对树状数组进行一次清空操作，注意不要用memset清空，要对添加的值进行记录，依次清空 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100010 using namespace std; int n,tr[maxn*4],h[maxn]; struct node{ int op,t,val,ans,id; }a[maxn]; int st[maxn],top,del[maxn]; bool cmp(node u,node v){ if(u.val!=v.val)return u.val<v.val; return u.id<v.id; } bool cmpp(node u,node v){ return u.id<v.id; } int Qry_tarr(int pos){ int sum=0; while(pos){ sum+=tr[pos]; pos-=(pos^(pos-1))&pos; } return sum; } void Add_tarr(int pos,int delta){ while(pos<=n){ tr[pos]+=delta; pos+=(pos^(pos-1))&pos; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d%d",&a[i].op,&a[i].t,&a[i].val); h[i]=a[i].t; a[i].id=i; } sort(h+1,h+n+1); for(int i=1;i<=n;i++){ a[i].t=lower_bound(h+1,h+n+1,a[i].t)-h; } sort(a+1,a+n+1,cmp); int valnow=a[1].val; for(int i=1;i<=n;i++){ if(a[i].val!=valnow){ while(top){ Add_tarr(st[top],del[top]); top--; } valnow=a[i].val; } if(a[i].op==1){ st[++top]=a[i].t; del[top]=-1; Add_tarr(a[i].t,1); } else if(a[i].op==2){ st[++top]=a[i].t; del[top]=1; Add_tarr(a[i].t,-1); } else { a[i].ans=Qry_tarr(a[i].t); } } sort(a+1,a+n+1,cmpp); for(int i=1;i<=n;i++){ if(a[i].op==3){ printf("%d\n",a[i].ans); } } return 0; }
原文：https://www.cnblogs.com/thmyl/p/12293589.html