F-序列查询
v5zsq题解
假设数字xxx在区间[l,r]种出现y次，那么包含x的子区间个数为2r−l+1−y⋅(2y−1)2^{r-l+1-y}·(2^y-1)2r−l+1−y⋅(2y−1)，因此对询问贡献是x⋅2r−l+1−y⋅(2y−1)=x[2r−l+1−2r−l+1−y]x·2^{r-l+1-y}·(2^y-1)=x[2^{r-l+1}-2^{r-l+1-y}]x⋅2r−l+1−y⋅(2y−1)=x[2r−l+1−2r−l+1−y]
其中第一部分非常好维护第二部分的贡献，可以把出现次数相同的数一起维护贡献sum[k]维护出现从次数为k的数字总和是多少。用个链表加快计算。
注意到一起区间中只有O(n)O( \sqrt n )O(n)种不同的出现次数因为1+2+...+n=O(n)1+2+...+\sqrt n = O(n)1+2+...+n=O(n)这是一个自然根号所以我们可以用一个均摊的莫队来维护区间可能的出现次数，从而维护区间中所有出现次数然后为了O(1)实现快速幂，我们可以每次O(n)O(\sqrt n)O(n)算出21,22…2nmodp2^1,2^2…2^{\sqrt n} \mod p21,22…2nmodp以及2n,22n…2nnmodp2^{\sqrt n},2^{2\sqrt n}…2^{\sqrt n\sqrt n} \mod p2n,22n…2nnmodp
#include<bits/stdc++.h>#pragma GCC optimize(2)using namespace std;using ll=long long;template <class T=int> T rd(){T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg;}ll qmi(ll a,ll b,ll mod){ll v=1;while(b){if(b&1) v=v*a%mod;a=a*a%mod;b>>=1;}return v;}const int N=100005;int Bs,b[N],a[N],n,m;struct node{int l,r,p,id;bool operator<(const node&o)const{if(b[l]==b[o.l]){if(b[l]&1) return r<o.r;return r>o.r;}return b[l]<b[o.l];}}q[N];int num[N],cnt[N];ll sum[N];int h,fr[N],ne[N];int ans[N];int mod;void insert(int x){ne[x]=h;fr[h]=x;fr[x]=0;h=x;}void del(int x){if(h==x) return h=ne[x],void();ne[fr[x]]=ne[x];fr[ne[x]]=fr[x];}void update(int x,int v){// 出现个数为num[x]-xif(num[x]){sum[num[x]]-=x;cnt[num[x]]--;if(!cnt[num[x]]) del(num[x]);}num[x]+=v;if(num[x]){sum[num[x]]+=x;cnt[num[x]]++;if(cnt[num[x]]==1) insert(num[x]);}}int add(int a,int b){a+=b;if(a>=mod) a-=mod;return a;}int mul(int a,int b){ll z=1ll*a*b;return z-z/mod*mod;}int f[1005],g[1005];void init(int n){f[0]=1;for(int i=1;i<=Bs;i++) f[i]=add(f[i-1],f[i-1]);g[0]=1;for(int i=1;i<=n/Bs;i++) g[i]=mul(g[i-1],f[Bs]);}int Pow(int n){return mul(g[n/Bs],f[n%Bs]);}int query(int l,int r,int p){mod=p;int len=r-l+1;init(n); int ans=0;for(int i=h;i;i=ne[i]) ans=add(ans,mul(sum[i]%p,add(Pow(len),p-Pow(len-i))));return ans;}int main(){n=rd(),m=rd();for(int i=1;i<=n;i++) a[i]=rd();Bs=sqrt(n)+1;for(int i=1;i<=n;i++) b[i]=(i-1)/Bs+1;for(int i=1;i<=m;i++) q[i].l=rd(),q[i].r=rd(),q[i].p=rd(),q[i].id=i;sort(q+1,q+1+m);int l=1,r=0;for(int i=1;i<=m;i++){while(r<q[i].r) update(a[++r],1);while(r>q[i].r) update(a[r--],-1);while(l<q[i].l) update(a[l++],-1);while(l>q[i].l) update(a[--l],1);ans[q[i].id]=query(q[i].l,q[i].r,q[i].p);}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);}
如果觉得《牛客练习赛10 F-序列查询（莫队+链表）》对你有帮助，请点赞、收藏，并留下你的观点哦！
