[破碎的状态] [-36] 641E
题意:(感谢@似水流年 翻译!)
给你n个操作
每次询问如果是第i个操作,那么就问只有前i个操作的时候的答案
每个操作,是在向一个多重集里面,你有三个操作:
1,在第x秒加一个数
2,在第x秒删一个数(保证存在,如果存在多个只删一次)
3,求在第x秒时每个数在整个数组里面出现了多少次
所以..
这一题我们把把每个数字揪出来,不同数字之间不相互影响的
每次进行一次树状数组上的询问/修改
需要离散化一下..还需要在适当的时候把整个数组清空..
就这样就可以了..代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | #include<set>#include<map>#include<list>#include<queue>#include<stack>#include<math.h>#include<string>#include<time.h>#include<bitset>#include<vector>#include<memory>#include<utility>#include<stdio.h>#include<sstream>#include<fstream>#include<iostream>#include<stdlib.h>#include<string.h>#include<algorithm>using namespace std;struct node{ int type; int time; int x; int id; friend bool operator < (const node &a,const node &b) { if (a.x==b.x) return a.id<b.id; return a.x<b.x; } void read() { scanf("%d%d%d",&type,&time,&x); }};node a[100005];int ans[100005];int b[100005];int n;int sum[100005];void add_val(int x,int y){ x++; for (;;) { sum[x]+=y; x+=x&(-x); if (x>n) return; }}void clean_val(int x){ x++; for (;;) { sum[x]=0; x+=x&(-x); if (x>n) return; }}int query_val(int x){ x++; int ans=0; for (;;) { if (x==0) return ans; ans+=sum[x]; x^=x&(-x); }}int main(){ #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif scanf("%d",&n); int i; for (i=0;i<n;i++) { a[i].read(); a[i].id=i; b[i]=a[i].time; } sort(a,a+n); sort(b,b+n); for (i=0;i<n;i++) { a[i].time=lower_bound(b,b+n,a[i].time)-b; } a[n].x=-1; int last=0; for (i=0;i<n;i++) { if ((i==0)||(a[i].x!=a[i-1].x)) { int j; for (j=last;j<i;j++) { clean_val(a[j].time); } last=i; } if (a[i].type==1) { add_val(a[i].time,1); ans[a[i].id]=-1; } if (a[i].type==2) { add_val(a[i].time,-1); ans[a[i].id]=-1; } if (a[i].type==3) { ans[a[i].id]=query_val(a[i].time); } } for (i=0;i<n;i++) { if (ans[i]==-1) continue; printf("%d\n",ans[i]); } return 0;} |
评论 (0)