洛谷P5072 [Ynoi2015] 盼君勿忘题解

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人，人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩

题目链接：P5072 [Ynoi2015] 盼君勿忘

题意：

珂朵莉给了你一个序列，每次查询一个区间 \([l,r]\) 中所有子序列分别去重后的和 \(\bmod\ p\)。

输入格式：

第一行两个整数 \(n,m\)。

第二行 \(n\) 个整数表示这个序列。

之后 \(m\) 行，每行三个整数 \(l,r,p\) 表示查询的区间与模数。

输出格式：

\(m\) 行，每行输出一个整数表示答案。

数据范围：

\(1\leq n,m,a_i \leq 10^5\)，\(1\leq p\leq 10^9\)，\(1\leq l\leq r\leq n\)。

可以发现，如果一个数 \(a_i\) 在区间中出现了 \(k\) 次，则它的贡献为 \[ a_i \times \left(2^{r-l+1}-2^{r-l+1-k}\right) \] 这个贡献方式使得出现次数相等的数可以把 \(a_i\) 加起来一起算。

考虑莫队，跳 \(l,r\) 的时候用一个双向链表维护区间内出现次数为 \(k\) 的数的 \(\sum a_i\) 。

然后遍历这个链表算答案（记得要用光速幂，否则多一个 \(\log\) ），单次扫的复杂度是 \(\mathcal{O}(\sqrt{n})\) 的

时间复杂度 \(\mathcal{O}(n \sqrt{n})\)

代码：（~~我偏要用 std::list ！~~）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(ll &x, int y, const int P) { (x += y) >= P ? x -= P : 0; }
#define N ((int)(1e5 + 15))

list<int> lst; list<int>::iterator pos[N];
struct node { int l, r, p, id, bl; } q[N];
int S, a[N], cnt[N]; ll sum[N], ans[N], pw1[N], pw2[N];
void init(const int P)
{
    pw1[0] = pw2[0] = 1;
    for(int i = 1; i <= S + 5; i++) pw1[i] = pw1[i - 1] * 2 % P;
    for(int i = 1; i <= S + 5; i++) pw2[i] = pw2[i - 1] * pw1[S] % P;
}
ll qpow(int x, const int P) { return pw1[x % S] * pw2[x / S] % P; }
void add(int ax)
{
    if(!(sum[cnt[ax]] -= ax)) lst.erase(pos[cnt[ax]]);
    if(!sum[++cnt[ax]]) { lst.push_back(cnt[ax]), pos[cnt[ax]] = prev(lst.end()); }
    sum[cnt[ax]] += ax;
}
void del(int ax)
{
    if(!(sum[cnt[ax]] -= ax)) lst.erase(pos[cnt[ax]]);
    if(!sum[--cnt[ax]]) { lst.push_back(cnt[ax]), pos[cnt[ax]] = prev(lst.end()); }
    sum[cnt[ax]] += ax;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; S = sqrt(n);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r >> q[i].p;
        q[i].id = i; q[i].bl = (q[i].l - 1) / S + 1;
    }
    sort(q + 1, q + 1 + m, [](node a, node b) { 
        return a.bl == b.bl ? a.r < b.r : a.bl < b.bl;
    });
    int l = 1, r = 0;
    for(int i = 1; i <= m; i++)
    {
        const int P = q[i].p; init(P);
        while(l > q[i].l) add(a[--l]);
        while(r < q[i].r) add(a[++r]);
        while(l < q[i].l) del(a[l++]);
        while(r > q[i].r) del(a[r--]);
        for(const int k : lst)
        {
            const ll _1 = qpow(r - l + 1, P);
            const ll _2 = qpow(r - l + 1 - k, P);
            add(ans[q[i].id], (_1 + P - _2) * sum[k] % P, P);
        }
    }
    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
    return 0;
}

参考文献：

[1] https://www.luogu.com.cn/article/1ca3a0bv

题目背景：

说起来，幸福本身就是因人而异的

有些人认为只要能混口饭吃就行了

有些人只要有书读就能满足

有些人认为只有全力地生存才是最重要的

有些人只要得到克服某种目标的瞬间就能满足

有些人只要某个人得到幸福，自己就会跟着幸福

也有些人则令人伤透脑筋地刚好相反

但是，大部分人都没有自觉

他们不知道究竟什么能给自己带来幸福

但是，他们会异口同声地表示想要获得幸福

那样的人即使能察觉到幸福

也没办法变得幸福

最重要的是要敢于正视自己的内心

【珂朵莉已经基本上不剩什么了】

【心灵和身体，珂朵莉基本上快要全部失去了】

【全部被我替换了】

【幸好你在失去一切之前，回到了这里】

【喜悦和悲伤】

【还有喜欢某个人的情绪】

【现在依旧还残存着一些吧？】

嗯...

确实还有那么一丝...

【那就没问题了】

【珂朵莉你，依旧是珂朵莉】

威...廉...？