P5072 [Ynoi2015] 盼君勿忘

查询一个区间 $[l, r]$ 中所有子序列分别去重后的和 $\bmod p$ 。

拆贡献。一个区间的所有子序列，共有 $2 ^ {r - l + 1}$ 个，对于每一个数 $n$ ，$cnt _ n$ 表示在区间中出现的次数。没有这个数 $n$ 的子序列共有 $2 ^ {r - l + 1 - cnt _ n}$ 个。那么共有 $2 ^ {r - l + 1} - 2 ^ {r - l + 1 - cnt _ n}$ 个序列至少存在一个 $n$ 。在每个子序列中去重，那么序列中不论 $n$ 有多少个，都算作一个 $n$ 。所以一个数对一个区间的贡献为 $n (2 ^ {r - l + 1} - 2 ^ {r - l + 1 - cnt _ n})$ 。
维护答案。如果直接计算需要将值域遍历一次，需要 $O(n)$ 的时间。用 $sum _ m$ 表示出现次数为 $m$ 的 $n$ 的和，那么此时通过 $sum$ 计算需要将所有出现的次数遍历一次。现在考虑出现的次数有多少种。出现的次数的种数最多的时候，那么出现 $1, 2, \ldots , k$ 次，那么 $1 + 2 + …\ldots+ k = \frac {k(1 + k) } 2 \le n$ 可以发现出现的次数的种数是 $\sqrt n$ 级别的，但是并不一定是连续的，即在 $n$ 的范围内出现了 $\sqrt n$ 次。考虑如何维护这 $\sqrt n$ 个数，需要支持插入、删除操作。那么可以使用链表。
光速幂。在这道题中，每次询问的模数不一样，这意味着不能提前预处理 $2$ 的次幂。如果对于每一个 $sum$ 都使用快速幂计算一次 $2$ 的次幂，那么复杂度将多一个 $\log$ ，不能通过这道题。光速幂可以在 $O(\sqrt n)$ 的时间内预处理 $2$ 的次幂，$O(1)$ 回答。将 $n$ 按块长为 $\sqrt n$ 分块，用 $\sqrt n$ 的时间计算出 $1, 2\ldots \sqrt n$ 的 $2$ 次幂，再用 $\sqrt n$ 的时间计算处 $1, 2\ldots \sqrt n$ 块的 $2$ 的次幂，那么询问可以分为若干块和零头，可以直接得到。
莫队。在一般的莫队中， $l$ 和 $r$ 的移动顺序不重要。但是，这里需要注意避免出现 $l, r$ 交叉的情况。此时 $cnt$ 为负数，导致链表下标为负，出现越界。

查看代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int p1[N], p2[N];
int n, m, len, w[N], cnt[N];
LL sum[N], ans[N];
struct Query
{
    int id, l, r, p;
    bool operator<(const Query &_) const
    {
        if (l / len != _.l / len)
            return l < _.l;
        return (l / len) & 1 ? r < _.r : r > _.r;
    }
} q[N];
void init(int p)
{
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= len; i++)
        p1[i] = (LL)p1[i - 1] * 2 % p;
    for (int i = 1; i <= len; i++)
        p2[i] = (LL)p1[len] * p2[i - 1] % p;
}
int lightpow(int k, int p)
{
    return (LL)p1[k % len] * p2[k / len] % p;
}
namespace Chain
{
    int tl, pre[N], nxt[N];
    void insert(int x)
    {
        pre[x] = tl;
        nxt[tl] = x;
        tl = x;
    }
    void remove(int x)
    {
        if (x == tl)
        {
            nxt[pre[x]] = 0;
            tl = pre[x];
        }
        else
        {
            nxt[pre[x]] = nxt[x];
            pre[nxt[x]] = pre[x];
        }
        pre[x] = nxt[x] = 0;
    }
    LL query(int k, int p)
    {
        LL res = 0;
        for (int i = tl; i; i = pre[i])
            res = (res + (LL)sum[i] * (lightpow(k, p) - lightpow(k - i, p)) % p + p) % p;
        return res;
    }
}
void add(int x)
{
    if (cnt[x])
    {
        sum[cnt[x]] -= x;
        if (!sum[cnt[x]])
            Chain::remove(cnt[x]);
    }
    cnt[x]++;
    if (!sum[cnt[x]])
        Chain::insert(cnt[x]);
    sum[cnt[x]] += x;
}
void remove(int x)
{
    sum[cnt[x]] -= x;
    if (!sum[cnt[x]])
        Chain::remove(cnt[x]);
    cnt[x]--;
    if (cnt[x])
    {
        if (!sum[cnt[x]])
            Chain::insert(cnt[x]);
        sum[cnt[x]] += x;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    len = sqrt(n) + 1;
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= m; i++)
    {
        q[i].id = i;
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].p);
    }
    sort(q + 1, q + m + 1);
    for (int i = 1, l = 1, r = 0; i <= m; i++)
    {
        while (l > q[i].l)
            add(w[--l]);
        while (r < q[i].r)
            add(w[++r]);
        while (l < q[i].l)
            remove(w[l++]);
        while (r > q[i].r)
            remove(w[r--]);
        init(q[i].p);
        ans[q[i].id] = Chain::query(q[i].r - q[i].l + 1, q[i].p);
    }
    for (int i = 1; i <= m; i++)
        printf("%lld\n", ans[i]);
    return 0;
}