Codeforces 669E CDQ分治

传送门：

题意：

三个操作：

1.在第x秒插入一个值y

2.在第x秒移走一个值y

3.查询第x秒有多少个y

题解：

有版本的查询，我们很容易想到可以基于时间给他排序

cdq的写法， 基于时间排序后分为两边，左边的坐标为j ，右边的坐标为i，如果a[j].t<a[i].t，那么就可以在a[j].pos的位置 上添加a[i].val,由于只有1e5个数但是值域是1e9，很容易想到是离散话一下用位置存val，emmm常规套路了，最后根据id排个序输出答案即可，小技巧是可以把查询的op置为0，删除的op置为-1，添加的op置为1，这样我当前位置的数量就可以直接添加上op 就可以得到了

代码：

#include
    
     using namespace std;const int maxn = 1e5 + 5;struct node {    int op;    int t, x;    int pos, id;} a[maxn];vector
     
       vec;bool cmp1(node a, node b) {    return a.t < b.t;}bool cmp2(node a, node b) {    return a.id < b.id;}int getid(int x) {    return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;}int num[maxn];int ans[maxn];void CDQ(int l, int r) {    if(l == r)return;    int mid = (l + r) / 2;    CDQ(l, mid);    CDQ(mid + 1, r);    sort(a + l, a + mid + 1, cmp1);    sort(a + mid + 1, a + r + 1, cmp1);    int j = l;    for(int i = mid + 1; i <= r; i++) {        while(j <= mid && a[j].t <= a[i].t) {            num[a[j].pos] += a[j].op;            j++;        }        if(a[i].op == 0)ans[a[i].id] += num[a[i].pos];    }    for(int i = l; i < j; i++)num[a[i].pos] -= a[i].op;}int main() {    int n;    scanf("%d", &n);    for(int i = 1; i <= n; i++) {        scanf("%d%d%d", &a[i].op, &a[i].t, &a[i].x);        if(a[i].op == 2) a[i].op = -1;        if(a[i].op == 3) a[i].op = 0;        a[i].id = i;        vec.push_back(a[i].x);    }    sort(vec.begin(), vec.end());    vec.erase(unique(vec.begin(), vec.end()), vec.end());    for(int i = 1; i <= n; i++)    a[i].pos = getid(a[i].x);    CDQ(1, n);    sort(a + 1, a + n + 1, cmp2);    for(int i = 1; i <= n; i++)if(a[i].op == 0)printf("%d\n", ans[i]);}