题解 P5072 【[Ynoi2015]盼君勿忘】

· · 题解

[Ynoi2015]盼君勿忘

这是 Ynoi 中一道相对偏水的题目，非常简单的莫队。

首先很容易想到，对于一个长度为 a 的序列，如果某个元素出现了 b 次，

我们那么共有 2^{a-b} 个子序列是不包含这一元素的，

而其他的子序列都包含这一元素。

换言之，这个元素的贡献次数是 2^a-2^{a-b}。

我们可以用一个链表来记录一下区间贡献内出现次数相同的数的和。

显然，这个链表内的元素个数最多是根号级别的。

对于 2 的若干次幂，我们可以预处理出 2^1,2^2\ldots 2^{\sqrt n} 与 2^{2\times \sqrt n},2^{3\times \sqrt n} \ldots 2^n。

然后我们就可以 \operatorname{O}(1) 将其求出。

莫队的复杂度是 \operatorname{O}(n\sqrt n)，询问的复杂度为 \operatorname{O}(m\sqrt n)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
    register int x=0;
    register bool f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return f?-x:x;
}
char cr[200];int tt;
inline void print(register int x,register char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=100005;
const int blk=317; 
int n,m;
int a[maxn],cnt[maxn],bl[maxn];
int sum[maxn];
int res[maxn];
struct node{
    int l,r,id,p;
}q[maxn];
inline bool cmp(register node a,register node b){
    return bl[a.l]^bl[b.l]?a.l<b.l:bl[a.l]&1?a.r<b.r:a.r>b.r;
}
struct lian{
    int nxt,pre;
}e[maxn];int tl;
inline void _ins(register int x){
    e[tl].nxt=x;
    e[x].pre=tl;
    tl=x;
}
inline void _del(register int x){
    if(x^tl){
        e[e[x].pre].nxt=e[x].nxt;
        e[e[x].nxt].pre=e[x].pre;
    }
    else{
        tl=e[x].pre;
    }
    e[x].nxt=e[x].pre=0;
}
inline void add(register int x){
    if(cnt[x]){
        sum[cnt[x]]-=x;
        if(!sum[cnt[x]]){
            _del(cnt[x]);
        }
    }
    cnt[x]++;
    if(!sum[cnt[x]]){
        _ins(cnt[x]);
    }
    sum[cnt[x]]+=x;
}
inline void del(register int x){
    sum[cnt[x]]-=x;
    if(!sum[cnt[x]]){
        _del(cnt[x]);
    }
    cnt[x]--;
    if(cnt[x]){
        if(!sum[cnt[x]]){
            _ins(cnt[x]);
        }
        sum[cnt[x]]+=x;
    }
}
int p1[2233],p2[2233],p;
inline int pw(register int x){
    return (ll)p1[x%blk]*p2[x/blk]%p;
}
signed main() {
    n=read();m=read();
    int g=0,f=1;
    for(register int i=1;i<=n;i++){
        a[i]=read();
        bl[i]=f;
        g++;if(g==blk){
            f++;g=0;
        }
    }
    for(register int i=1;i<=m;i++){
        q[i].l=read();q[i].r=read();q[i].p=read();q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    for(register int i=1,l=1,r=0;i<=m;i++){
        while(r<q[i].r){
            add(a[++r]);
        }
        while(l>q[i].l){
            add(a[--l]);
        }
        while(r>q[i].r){
            del(a[r--]);
        }
        while(l<q[i].l){
            del(a[l++]);
        }
        p1[0]=p2[0]=1;
        p=q[i].p;
        for(register int j=1;j<=blk;j++){
            p1[j]=(ll)p1[j-1]*2%p;
        }
        p2[1]=p1[blk];
        for(register int j=2;j<=blk;j++){
            p2[j]=(ll)p2[j-1]*p2[1]%p;
        }
        register int o=q[i].id;
        for(int j=e[0].nxt;j;j=e[j].nxt){
            res[o]+=(ll)sum[j]*(pw(q[i].r-q[i].l+1)-pw(q[i].r-q[i].l+1-j))%p;
            res[o]=(res[o]%p+p)%p;
        }
    }
    for(register int i=1;i<=n;i++){
        print(res[i]);
    }
}