正題

題目鏈接:https://www.luogu.com.cn/problem/P5072

---

題目大意

$n$個數(shù)，$m$個詢問$(l,r,p)$表示詢問$[l,r]$的所有子序列的和模$p$。

---

解題思路

一個出現(xiàn)了$k$次的數(shù)會產(chǎn)生貢獻$2^{r?l+1}?2^{r?l+1?k}$次貢獻。那么我們設(shè)$z_i$表示出現(xiàn)了$i$次的數(shù)字和。這樣可以$O(nm)$統(tǒng)計答案。

考慮根號分治，我們把出現(xiàn)小于$\sqrt{n}$的數(shù)用桶來統(tǒng)計，次數(shù)大于$\sqrt{n}$的數(shù)用$set$維護，這樣的數(shù)最多只會有$\sqrt{n}$個。

考慮如何預(yù)處理$2^i\%p$，我們可以先預(yù)處理$2^0,2^1,2^2,...2^{\sqrt{n}},2^{2\sqrt{n}}...$的值，然后詢問時拆成兩部分即可，這樣的時間復(fù)雜度也是$O(n\sqrt{n})$的。

所以時間復(fù)雜度為$O(n\sqrt{n})$

---

$code$

#include<bits/stdc++.h> using namespace std; const int N=1e5+10,siz=317; struct node{int l,r,p,id; }q[N]; int n,m,T,a[N],ans[N],b[N]; int z[N],v[N],q2[N],p2[N]; set<int> s; bool cmp(node x,node y){if(x.l/T==y.l/T)return x.r<y.r;return x.l<y.l; } void add(int x){z[v[x]]-=b[x];if(v[x]==siz)s.insert(x);v[x]++;z[v[x]]+=b[x];return; } void del(int x){z[v[x]]-=b[x];v[x]--;if(v[x]==siz)s.erase(x);z[v[x]]+=b[x];return; } int power(int x,int p) {return 1ll*q2[x/siz]*p2[x%siz]%p;} int main() {scanf("%d%d",&n,&m);T=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}sort(b+1,b+1+n);int cnt=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;for(int i=1;i<=m;i++)scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].p),q[i].id=i;sort(q+1,q+1+m,cmp);int l=1,r=0;set<int>::iterator it;for(int x=1;x<=m;x++){while(r<q[x].r)add(a[++r]);while(l>q[x].l)add(a[--l]);while(r>q[x].r)del(a[r--]);while(l<q[x].l)del(a[l++]);p2[0]=1;for(int i=1;i<=siz;i++)p2[i]=p2[i-1]*2%q[x].p;q2[1]=p2[siz];q2[0]=1;for(int i=2;i<=siz;i++)q2[i]=1ll*q2[i-1]*q2[1]%q[x].p;int pw=power(r-l+1,q[x].p),answer=0,P=q[x].p;for(int i=1;i<=siz;i++)answer=(answer+1ll*(pw-power(r-l+1-i,P)+P)%P*z[i]%P)%P;for(it=s.begin();it!=s.end();it++)answer=(answer+1ll*(pw-power(r-l+1-v[*it],P)+P)%P*b[*it]%P)%P;ans[q[x].id]=answer;}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P5072-[Ynoi2015]盼君勿忘【莫队,根号分治】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。