傻逼CDQ分治模板题。。。本来以为。。。要求小于当前值的数。。。要搞个bit。。。还要离散化下。。。然后发现就TM是。。。count一下当前值。。。于是就套了个map两下就写完了。。。
#include <bits/stdc++.h> using namespace std; int n; struct node{ int t; int type; int num; int id; }a[105000], b[105000]; bool cmp(node a, node b){ return a.t<b.t; } map<int, int>mp; int ans[105000]; void cdq(int l, int r){ if(l==r)return; int m=(l+r)/2; cdq(l, m); cdq(m+1, r); for(int i=l;i<=r;i++){ b[i]=a[i]; } sort(b+l, b+m+1, cmp); sort(b+m+1, b+r+1, cmp); int j=l; for(int i=m+1;i<=r;i++){ while(j<=m&&b[j].t<=b[i].t){ if(b[j].type==1)mp[b[j].num]++; else if(b[j].type==2)mp[b[j].num]--; j++; } if(b[i].type==3)ans[b[i].id]+=mp[b[i].num]; } for(int i=l;i<=m;i++)mp[b[i].num]=0; return; } int main() { scanf("%d", &n); for(int i=1;i<=n;i++){ scanf("%d%d%d", &a[i].type, &a[i].t, &a[i].num); a[i].id=i; } memset(ans, 0, sizeof(ans)); cdq(1, n); for(int i=1;i<=n;i++)if(a[i].type==3)printf("%d\n", ans[i]); }