Luogu P5072 [Ynoi2015]盼君勿忘

题意

给定一个长度为 \(n\) 的序列 \(a\) 和 \(m\) 次询问，第 \(i\) 次询问需要求出 \([l_i,r_i]\) 内所有子序列去重之后的和，对 \(p_i\) 取模。

\(\texttt{Data Range:}1\leq n,m,a_i\leq 10^5,1\leq p_i\leq 10^9\)

题解

人生第一道 Ynoi，写篇题解祭之。

我们与其考虑某个子序列包含了哪些值，还不如看某个值能贡献到多少个子序列。

然而正着做不好做，因为一个子序列中某个值可能出现多次，所以考虑反过来看一个值不能贡献到多少个子序列，再用总的减去这个子序列就好了。

考虑某一个 \([l,r]\) 的询问，其中某个数出现了 \(k\) 次，可以很容易由上面的分析知道这个数将会对 \(2^{r-l+1}-2^{r-l+1-k}\) 个子序列产生贡献。

同时，注意到多个出现次数相同的数可以一起加起来贡献。所以我们可以考虑设 \(b_k\) 为当前的区间内出现了 \(k\) 次的所有数的和，那么我们可以得到答案为

\[\sum\limits_{k}b_k\left(2^{r-l+1}-2^{r-l+1-k}\right)
\]

注意到 \(b_k\) 可以使用莫队来维护，所以我们就得到了一个 \(O(nm\log n)\) 的算法，但是无法通过。

考虑统计答案的时候我们会枚举很多等于 \(0\) 的 \(b_k\)。所以我们在移动区间端点的时候可以同时用链表记录一下满足 \(b_k\neq 0\) 的那些 \(k\)。

注意到链表中记录的 \(k\) 是 \(O(\sqrt{n})\) 的，所以时间复杂度就变为 \(O(m\sqrt{n}\log n)\)，还是会 TLE。

注意到这个 \(\log\) 甚至都可以搞掉，考虑分块打表，对于每个询问都预处理一次，因为一次预处理是 \(O(\sqrt{n})\) 的，所以复杂度为 \(O(m\sqrt{n})\)，可过。

代码

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

typedef int ll;

typedef long long int li;

const ll MAXN=2e5+51;

struct Query{

    ll l,r,p,id;

    inline bool operator <(const Query &rhs)const;

};

Query qry[MAXN];

ll n,qcnt,l,r,p,blockSize,ptrl,ptrr,len,hd;

li rres;

ll x[MAXN],res[MAXN],cntl[MAXN],sum[MAXN],prv[MAXN],nxt[MAXN];

ll blk[MAXN],pw[MAXN];

inline ll read()

{

    register ll num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

}

inline bool Query::operator <(const Query &rhs)const

{

    if(l/blockSize==rhs.l/blockSize)

    {

        return l/blockSize==1?r<rhs.r:r>rhs.r;

    }

    return l<rhs.l;

}

inline void insert(ll x)

{

    prv[x]=0,nxt[x]=hd,prv[hd]=x,hd=x;

}

inline void erase(ll x)

{

    if(x==hd)

    {

        return (void)(hd=nxt[x],prv[nxt[x]]=prv[x]=nxt[x]=0);

    }

    nxt[prv[x]]=nxt[x],prv[nxt[x]]=prv[x],prv[x]=nxt[x]=0;

}

inline void add(ll pos)

{

    if(!(cntl[x[pos]]++))

    {

        sum[1]+=x[pos];

    }

    else

    {

        sum[cntl[x[pos]]-1]-=x[pos],sum[cntl[x[pos]]]+=x[pos];

    }

    if(sum[cntl[x[pos]]]==x[pos])

    {

        insert(cntl[x[pos]]);

    }

    if(!sum[cntl[x[pos]]-1])

    {

        erase(cntl[x[pos]]-1);

    }

}

inline void del(ll pos)

{

    if(!(--cntl[x[pos]]))

    {

        sum[1]-=x[pos];

    }

    else

    {

        sum[cntl[x[pos]]+1]-=x[pos],sum[cntl[x[pos]]]+=x[pos];

    }

    if(sum[cntl[x[pos]]]==x[pos])

    {

        insert(cntl[x[pos]]);

    }

    if(!sum[cntl[x[pos]]+1])

    {

        erase(cntl[x[pos]]+1);

    }

}

inline void setup(ll md)

{

    pw[0]=blk[0]=1;

    for(register int i=1;i<=511;i++)

    {

        pw[i]=(pw[i-1]+pw[i-1])%md;

    }

    blk[1]=(pw[511]+pw[511])%md;

    for(register int i=1;i<=512;i++)

    {

        blk[i]=(li)blk[i-1]*blk[1]%md;

    }

}

inline ll query(ll x,ll md)

{

    return (li)blk[x>>9]*pw[x&511]%md;

}

int main()

{

    blockSize=sqrt(n=read()),qcnt=read();

    for(register int i=1;i<=n;i++)

    {

        x[i]=read();

    }

    for(register int i=1;i<=qcnt;i++)

    {

        l=read(),r=read(),p=read(),qry[i]=(Query){l,r,p,i};

    }

    sort(qry+1,qry+qcnt+1),ptrl=1;

    for(register int i=1;i<=qcnt;i++)

    {

        while(ptrr<qry[i].r)

        {

            add(++ptrr);

        }

        while(ptrr>qry[i].r)

        {

            del(ptrr--);

        }

        while(ptrl<qry[i].l)

        {

            del(ptrl++);

        }

        while(ptrl>qry[i].l)

        {

            add(--ptrl);

        }

        setup(p=qry[i].p),len=qry[i].r-qry[i].l+1,rres=0;

        for(register int j=hd;j;j=nxt[j])

        {

            rres+=(li)sum[j]*(query(len,p)-query(len-j,p));

        }

        res[qry[i].id]=(rres%p+p)%p;

    }

    for(register int i=1;i<=qcnt;i++)

    {

        printf("%d\n",res[i]);

    }

}

巴特西

Luogu P5072 [Ynoi2015]盼君勿忘

题意

题解

代码

最新文章

热门文章