
题意:你需要维护一个multiset,支持以下操作:
1:在某个时间点向multiset插入一个数。
2:在某个时间点在multiset中删除一个数。
3:在某个时间点查询multiset的某个数的个数。
思路:该题相当于要构建一个在任意位置插入,并查询前缀操作的某个值的多少。乍一看比较棘手,搞不好还要数据结构的嵌套。但是转化一下思路,用cdq分治这题非常简单。分治过程中按时间排序即可,用map维护前半部分产生的影响,后面如果有查询在map中查询即可。
代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct query{
int flag, t, val, id;
};
query q[maxn], tmp[maxn];
int ans[maxn], tot;
map<int, int> mp;
void cdq(int l, int r) {
if(l == r) return;
int mid = (l + r) >> 1;
cdq(l, mid);
cdq(mid + 1, r);
int l1 = l, l2 = mid + 1, pos = l;
mp.clear();
while(l1 <= mid && l2 <= r) {
if(q[l1].t < q[l2].t) {
if(q[l1].flag == 1) mp[q[l1].val]++;
else if(q[l1].flag == 2) mp[q[l1].val]--;
tmp[pos++] = q[l1++];
} else {
if(q[l2].flag == 3) {
ans[q[l2].id] += mp[q[l2].val];
}
tmp[pos++] = q[l2++];
}
}
while(l1 <= mid) tmp[pos++] = q[l1++];
while(l2 <= r) {
if(q[l2].flag == 3) {
ans[q[l2].id] += mp[q[l2].val];
}
tmp[pos++] = q[l2++];
}
for (int i = l; i <= r; i++)
q[i] = tmp[i];
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &q[i].flag, &q[i].t, &q[i].val);
if(q[i].flag == 3) q[i].id = ++tot;
}
cdq(1, n);
for (int i = 1; i <= tot; i++) {
printf("%d\n", ans[i]);
}
}