题解 CF641E 【Little Artem and Time Machine】
龙之吻—水货
2019-04-19 18:00:07
# CF641E Little Artem and Time Machine
## 题目大意
直接看翻译还是能看懂的吧 QwQ
## 个人感觉
CDQ 分治入门题目
## 解题报告
其他题解也有 CDQ 分治的做法，不过似乎及其概括，这里稍微补充一下。
首先，这道题有三维 ： 操作的顺序，时间轴，以及 x 的值。
由于第一维本身有序，所以暂时不考虑去动它，选择对第二维进行 CDQ 分治。
考虑如何统计左区间对右区间的影响，假设 $a[i]$ 在左区间， $a[j]$ 在有区间，发现只有当 $a[i].t <= a[j].t$, 且 $a[i].x == a[j].x$ 的时候， $a[i]$ 对 $a[j]$ 才会产生贡献，所以在 CDQ 分治的时候只需要维护一个桶就可以了。
因为 $x$ 可能会比较大，所以可以使用 unordered_map 或者先离散化一下。
复杂度 : $O(n\log n)$
实测结果(时间常数大小) ：
[离散化 + 桶](https://www.luogu.org/recordnew/show/18350392) < [un_map + 逐个删除](https://www.luogu.org/recordnew/show/18350482) << [un_map + un_map::clear()](https://www.luogu.org/recordnew/show/18349711)
附上使用离散化的 Code ：
```cpp
#include<cstdio>
#include<algorithm>
class Solution{
private :
static const int maxn = 1e5 + 7;
struct Oper{
int op, t, x, id;
};
int n, cnt, b[maxn], ct, ans[maxn];
Oper p[maxn];
void CDQ(int l, int r) {
if (l == r) {
return;
}
int mid = (l + r) >> 1;
CDQ(l, mid), CDQ(mid + 1, r);
static Oper tmp[maxn];
static int tot[maxn];
int i = l, j = mid + 1, tp = l;
while (i <= mid && j <= r) {
if (p[i].t <= p[j].t) {
if (p[i].op == 1) {
tot[p[i].x]++;
} else if (p[i].op == 2) {
tot[p[i].x]--;
}
tmp[tp++] = p[i++];
} else {
if (p[j].op == 3) {
ans[p[j].id] += tot[p[j].x];
}
tmp[tp++] = p[j++];
}
}
while (i <= mid) {
tmp[tp++] = p[i++];
}
while (j <= r) {
if (p[j].op == 3) {
ans[p[j].id] += tot[p[j].x];
}
tmp[tp++] = p[j++];
}
for (register int i = l; i <= mid; i++) {
tot[p[i].x] = 0;
}
for (register int i = l; i <= r; i++) {
p[i] = tmp[i];
}
}
public :
Solution() {
get();
solve();
}
void get() {
scanf("%d", &n);
for (register int i = 1; i <= n; i++) {
scanf("%d %d %d", &p[i].op, &p[i].t, &p[i].x);
b[i] = p[i].x;
if (p[i].op == 3) {
p[i].id = ++cnt;
}
}
}
void solve() {
std::sort(b + 1, b + 1 + n);
ct = std::unique(b + 1, b + 1 + n) - b + 1;
for (register int i = 1; i <= n; i++) {
p[i].x = std::lower_bound(b + 1, b + 1 + ct, p[i].x) - b;
}
CDQ(1, n);
for (register int i = 1; i <= cnt; i++) {
printf("%d\n", ans[i]);
}
}
};
Solution sol;
int main() {}
```