P1903 [国家集训队] 数颜色 / 维护队列

P1903 [国家集训队] 数颜色 / 维护队列

带修莫队可以做到 $O(n ^ {\frac 5 3})$ ，见带修莫队模板。

“带修主席树”，和没有修改一样，维护 $pre _ i$ 表示前面第一个和 $i$ 颜色一样的位置，查询区间有多少个数 $< l$ 。

修改会影响到 $3$ 个 $pre$ ，修改前的，自己的，修改后的。

应该有链表做法可以 $O(1)$ 维护 $pre$ ，但是不是瓶颈，可以对于每一个值域开一个 set 。但是发现常数大大增加，不过复杂度 $O(n \log ^ 2 n)$ ，依然吊打莫队。

查看代码

#include <cstdio>
#include <set>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 10, M = 5e7 + 10, K = 1e6 + 10;
int n, m, w[N];
struct Node
{
    int l, r, v;
} tr[M];
int idx, rt[N];
set <int> p[K];
void insert (int &x, int t, int k, int l = 0, int r = n - 1)
{
    !x && (x = ++idx);
    tr[x].v += k;
    if (l == r)
        return;
    int mid = l + r >> 1;
    t <= mid ? insert(tr[x].l, t, k, l, mid) : insert(tr[x].r, t, k, mid + 1, r);
}
void modify (int x, int t, int k)
{
    for (; x <= n; x += x & -x)
        insert(rt[x], t, k);
}
int query (int x, int k, int l = 0, int r = n - 1)
{
    if (r <= k)
        return tr[x].v;
    if (l > k)
        return 0;
    int mid = l + r >> 1;
    return query(tr[x].l, k, l, mid) + query(tr[x].r, k, mid + 1, r);
}
int main ()
{
    read(n), read(m);
    for (int i = 1; i <= 1e6; i++)
        p[i].insert(0), p[i].insert(n + 1);
    for (int i = 1; i <= n; i++)
    {
        read(w[i]);
        modify(i, *--p[w[i]].lower_bound(i), 1);
        p[w[i]].insert(i);
    }
    for (char op[2]; m; m--)
    {
        scanf("%s", op);
        if (op[0] == 'Q')
        {
            int l, r, res = 0;
            read(l), read(r);
            int t = --l;
            for (; l; l -= l & -l)
                res -= query(rt[l], t);
            for (; r; r -= r & -r)
                res += query(rt[r], t);
            write(res), puts("");
        }
        else if (op[0] == 'R')
        {
            int t, k, a, b;
            read(t), read(k);
            a = *p[w[t]].upper_bound(t), b = *--p[w[t]].lower_bound(t);
            modify(t, b, -1);
            modify(a, t, -1);
            modify(a, b, 1);
            p[w[t]].erase(t);
            w[t] = k;
            a = *p[w[t]].upper_bound(t), b = *--p[w[t]].lower_bound(t);
            modify(t, b, 1);
            modify(a, b, -1);
            modify(a, t, 1);
            p[w[t]].insert(t);
        }
    }
    return 0;
}