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

· · 题解

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

珂朵莉，要永远幸福哦。

我们考虑每个数的贡献。即该区间内含有这个数的子序列个数。用补集转化为不含这个数的子序列个数。

那么，假设这个数在[l,r]内出现了k次，则一共有2^{r-l+1}-2^{r-l+1-k}个子序列包含这个数。

所以，我们莫队，维护所有出现k次的不同数的和，然后包含这些数的子序列个数都相同，所以直接用和来计算贡献即可。

时间复杂度O(nm)，非常优秀。

考虑根号内分类讨论。

对于出现次数大于\sqrt n的数，这种数最多不到\sqrt n个。

所以我们莫队，统计出现次数小于等于\sqrt n的所有出现次数为i的和s_i，然后用一个东西来维护所有出现次数大于\sqrt n的数。

这样的话，每次询问的复杂度就是O(\sqrt n)了。

看上去好像没什么问题，实际上你会发现求2的幂次还有个\log，而且模数会改，不好预处理。

有一种分块O(\sqrt n)预处理，O(1)求幂次的方法，具体就是求出2^0,2^1,2^2,\dots,2^{{\sqrt n}-1}和2^{\sqrt n},2^{2\sqrt n},\dots,2^n（模意义），然后每个幂都分成两部分相乘即可。

每次询问重新计算一遍即可。

然后我们考虑用什么东西来维护出现次数大于\sqrt n的数。我用了unordered_set，理论上是线性的（当然这个理论有多可靠就不知道了）。

这样总时间复杂度O((n+m)\sqrt n)，空间复杂度O(n)。

Code：

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<vector>
#include<unordered_set>
#ifdef ONLINE_JUDGE
struct istream{
    char buf[23333333],*s;
    inline istream(){
        buf[fread(s=buf,1,23333330,stdin)]='\n';
        fclose(stdin);
    }
    inline istream&operator>>(int&d){
        d=0;
        for(;!isdigit(*s);++s);
        while(isdigit(*s))
        d=(d<<3)+(d<<1)+(*s++^'0');
        return*this;
    }
}cin;
struct ostream{
    char buf[8000005],*s;
    inline ostream(){s=buf;}
    inline ostream&operator<<(int d){
        if(!d){
            *s++='0';
        }else{
            static int w;
            for(w=1;w<=d;w*=10);
            for(;w/=10;d%=w)*s++=d/w^'0';
        }
        return*this;
    }
    inline ostream&operator<<(const char&c){*s++=c;return*this;}
    inline void flush(){
        fwrite(buf,1,s-buf,stdout);
        s=buf;
    }
    inline~ostream(){flush();}
}cout;
#else
#include<iostream>
using std::cin;
using std::cout;
#endif
#define siz 317
#define N 100005
int n,m,a[N],buc[N],_2[siz+2],__2[siz+2],out[N];
long long bvc[siz+2];
std::vector<int>lr;
std::unordered_set<int>s;
inline int pow2(int b,const int&md){
    int ret=1,a=2;
    for(;b;b>>=1,a=1LL*a*a%md)
    if(b&1)ret=1LL*ret*a%md;
    return ret;
}
inline int pw2(int m,const int&md){
    return 1LL*_2[m%siz]*__2[m/siz]%md;
}
struct que{
    int l,r,id,md;
    inline bool operator<(const que&rhs)const{
        return(l/siz!=rhs.l/siz)?(l<rhs.l):(r<rhs.r);
    }
}q[N];
inline void add(int pos){
    const int val=a[pos];
    if(buc[val]>siz)++buc[val];else
    if(buc[val]==siz)bvc[buc[val]++]-=lr[val],s.insert(val);else
    bvc[buc[val]]-=lr[val],bvc[++buc[val]]+=lr[val];
}
inline void del(int pos){
    const int val=a[pos];
    if(buc[val]>siz+1)--buc[val];else
    if(buc[val]==siz+1)s.erase(val),bvc[--buc[val]]+=lr[val];else
    bvc[buc[val]]-=lr[val],bvc[--buc[val]]+=lr[val];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;lr.push_back(a[i++]))cin>>a[i];
    std::sort(lr.begin(),lr.end());
    for(int i=1;i<=n;++i)a[i]=lower_bound(lr.begin(),lr.end(),a[i])-lr.begin();
    for(int i=1;i<=m;++i)
    cin>>q[q[i].id=i].l>>q[i].r>>q[i].md;
    std::sort(q+1,q+m+1);
    int l=1,r=0;
    for(int i=1;i<=n;++i)*bvc+=a[i];
    *_2=*__2=1;
    for(int i=1;i<=m;++i){
        while(r<q[i].r)add(++r);
        while(l>q[i].l)add(--l);
        while(r>q[i].r)del(r--);
        while(l<q[i].l)del(l++);
        const int md=q[i].md,len=r-l+1;
        for(int j=1;j<siz;++j)
        _2[j]=2LL*_2[j-1]%md;
        __2[1]=pow2(siz,md);
        for(int j=2;j<=siz;++j)
        __2[j]=__2[1]*1LL*__2[j-1]%md;
        int&ans=out[q[i].id];
        const int all=pw2(len,md);
        for(int j=1;j<=siz;++j)
        (ans+=1LL*(all-pw2(len-j,md)+md)*bvc[j]%md-md)+=ans>>31&md;
        for(int j:s){
            (ans+=1LL*(all-pw2(len-buc[j],md)+md)*lr[j]%md-md)+=ans>>31&md;
        }
    }
    for(int i=1;i<=m;++i)cout<<out[i]<<'\n';
    return 0;
}