P2464 [SDOI2008] 郁闷的小 J 题解

Super_Cube · 2024-01-07 14:23:26 · 题解

Solution

第一眼：单点修改，区间查询编号。这不是树套树板题？

然后再一看，空间限制只有 128 MiB。

然后仔细算算，树套树就算离散化空间复杂度再怎么也是 O(n\log^2n)，肯定不够用。

当然数据不一定都能卡满，但我们总不能去赌数据的强度吧。

这时候发现这个题可以离线！而 cdq 分治的作用就是降维，刚好可以把空间复杂度降下来。

具体的，对数据进行离散化，把查询操作改为前缀相减，把修改操作变为原来的编码数量减一，修改后的编码数量加一，离线下来之后时间维度默认有序，在 cdq 内部按照位置排序，归并算贡献的时候对左半部分的修改打桶记录，然后对右半部分的查询查桶。

时间复杂度：O((n+m)\log(n+m))。

空间复杂度：O(n+m)。

Code

#include <bits/stdc++.h>
struct ques {
    int x, y, z, id;
};
std::vector<ques> v;
int cnt[200005];
int ans[100005];
void cdq(int l, int r) {
    if (l == r)
        return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int i = l, j = mid + 1;
    for (; j <= r; ++j) {
        for (; i <= mid && v[i].x <= v[j].x; ++i)
            if (!v[i].id)
                cnt[v[i].y] += v[i].z;
        if (v[j].id)
            ans[v[j].id] += v[j].z * cnt[v[j].y];
    }
    for (int k = l; k < i; ++k)
        if (!v[k].id)
            cnt[v[k].y] -= v[k].z;
    std::inplace_merge(v.begin() + l, v.begin() + mid + 1, v.begin() + r + 1,
                       [&](ques x, ques y) { return x.x < y.x; });
}
std::unordered_map<int, int> mp;
int a[100005];
int n, m, qdx, idx;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        if (!mp.count(a[i]))
            mp[a[i]] = ++idx;
        a[i] = mp[a[i]];
        v.push_back((ques){ i, a[i], 1, 0 });
    }
    for (int l, r, x; m--;) {
        static char op;
        scanf("\n %c%d", &op, &l);
        if (op == 'C') {
            scanf("%d", &x);
            if (!mp.count(x))
                mp[x] = ++idx;
            x = mp[x];
            v.push_back((ques){ l, a[l], -1, 0 });
            v.push_back((ques){ l, a[l] = x, 1, 0 });
        } else {
            scanf("%d%d", &r, &x);
            if (!mp.count(x))
                mp[x] = ++idx;
            x = mp[x];
            ++qdx;
            v.push_back((ques){ r, x, 1, qdx });
            v.push_back((ques){ l - 1, x, -1, qdx });
        }
    }
    cdq(0, v.size() - 1);
    for (int i = 1; i <= qdx; ++i) printf("%d\n", ans[i]);
    return 0;
}