Codeforces 669E Little Artem and Time Machine 【CDQ分治+map】

传送门

废话：读错题了，写了半天结果发现写了一道假题。

题意：
三种操作：
操作①：在时间戳为T的多重集合中加入一个数字x。
操作②：在时间戳为T的多重集合中加入一个数字x。
操作③：询问在时间戳为T的多重集合中包好多少个数字x。

解题思路:
基础的二维偏序：对于操作时间 q1 和 q2，时间戳 t1 和 t2 ，数字 x 。 q1<q2 并且 t1<t2  操作②和操作①的数量差。
第一查询时间直接按照输入的来，可以降掉一维，剩下的一维按照时间戳升序，用分治解决。答案直接拿map记录数量就可以了。
如果让你求小于等于x的数量的个数，第三维我们就要用树状数组来维护信息。

代码：

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>
 
#define MT(a, b) memset(a,b,sizeof(a))
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
const double pai = acos(-1.0);
const double E = 2.718281828459;
const ll mod = 20180623;
const double esp = 1e-6;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
 
int n, cnt;
struct node {
    int op, t, x;
    int index;
} q[maxn], temp[maxn];
int ans[maxn];
 
bool cmp(node a, node b) {
    if(a.t == b.t) {
        if(a.x == b.x)
            return a.op < b.op;
        return a.x < b.x;
    }
    return a.t < b.t;
}
 
void cdq(int l, int r) {
    if (l == r)    return;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int ql = l, qr = mid + 1;
    map<int,int>num;
    for (int i = l; i <= r; i++) {
        if ((ql <= mid && cmp(q[ql], q[qr])) || qr > r) {
            if (q[ql].op == 1)
                num[q[ql].x]++;
            else if (q[ql].op == 2)
                num[q[ql].x]--;
            temp[i] = q[ql++];
        } else {
            if (q[qr].op == 3)
                ans[q[qr].index] +=num[q[qr].x];
            temp[i] = q[qr++];
        }
    }
    for (int i = l; i <= r; i++)
        q[i] = temp[i];
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &q[i].op, &q[i].t, &q[i].x);
        if (q[i].op == 3)
            q[i].index = ++cnt;
    }
    cdq(1, n);
    for (int i = 1; i <= cnt; i++)
        printf("%d\n", ans[i]);
    return 0;
}