洛谷:P5072 [Ynoi2015]盼君勿忘
- 2019 年 10 月 8 日
- 筆記
原題地址:https://www.luogu.org/problem/P5072
題目簡述
給定一個序列，每次查詢一個區間[l,r]中所有子序列分別去重後的和mod p
思路
我們考慮每個數的貢獻。即該區間內含有這個數的子序列個數。用補集轉化為不含這個數的子序列個數。
那麼，假設這個數在[l,r]內出現了kk次，則一共有2^(r-l+1)-2^(r-l+1-k)個子序列包含這個數。
本題可以離線，因此選擇使用莫隊，過程中維護cnt[k]表示區間內恰好出現k次的數字個數，維護sum[j]表示區間內恰好出現j次的數字之和（區間內出現次數相同的數，對於這些數，區間中包含這些數的子序列個數都相同，因此存數字之和就行）。
然而這樣時間複雜度為O(詢問次數單次詢問複雜度)=O(nmax(sqrt(n),n))=O(nm)，並不可行。我們發現時間瓶頸不在莫隊的sqrt(n)，而是在單次查詢中求解的複雜度n。
有2個套路可供使用：出現次數大於sqrt(n)的數不超過sqrt(n)個，值不為0的cnt[k]少於2sqrt(n)個（反證易得，本質類似）。
對於第一個套路，我們分類討論：出現次數小於等於sqrt(n)，則統計每個出現次數的數字之和；大於sqrt(n)的用哈希表(unordered_set,C++11)存下具體的數字和其出現次數。這樣每次查詢是sqrt(n)。
筆者使用的則是第二個套路：val[x]表示出現次數恰好為x的數字之和（同上文的sum[j]）。隨著莫隊l,r指針的移動，把所有可能變為非0的val[x]記下來，指針移動完畢後再對其進行篩選，把確實非0的val[x]保留，其他去除。這樣計算單次答案的複雜度就等同於單次查詢中莫隊指針移動的平均步數：都是sqrt(n)級別。這樣做不需要用到哈希表之類的，常數小了很多，甚至不需要讀入優化也能輕鬆過。
還沒完。我們發現模數是不定的，為了保證單次查詢的複雜度壓在sqrt(n)以內，我們還有最後一件事情要做：在sqrt(n)的時間內求出2^(r-l+1)和所有的2^(r-l+1-k)。這裡安利一個神奇的方式：每次查詢只需要做一次時間複雜度為sqrt(n)的預處理就可以O(1)查詢了。
假設查詢區間長度為len(len=r-l+1)，我們記siz=sqrt(len)，而後計算2^0,2^1,2^2...2^sqrt(len)，存在數組pow1中；再計算2^sqrt(len),2^(2sqrt(len)),2^(3sqrt(len)),2^(4sqrt(len))...,2^(sqrt(len)sqrt(len))，存在數組pow[2]中。以上計算都在mod p意義下進行。
這樣求2的任意次方都可以O(1)出解:2^k=2^(k/siz)2^(k%siz)=pow2[k/siz]*pow1[k%siz]（記得模p）。
程式碼
#include <bits/stdc++.h> using namespace std; #define MAXN 100005 int n,m; int a[MAXN],val[MAXN*2],cnt[MAXN],ans[MAXN]; int tot,blosiz,powsiz; int bel[MAXN],pow1[MAXN],pow2[MAXN]; bool calced[MAXN]; long long sum[MAXN]; struct query { int id,l,r,p; bool operator<(const query &sb) const { return bel[l]!=bel[sb.l] ? bel[l]<bel[sb.l] : (bel[l]&1 ? r<sb.r : r>sb.r); } } q[MAXN]; void add(int x) { sum[cnt[x]]-=x; cnt[x]++; sum[cnt[x]]+=x; ++tot; val[tot]=cnt[x]; } void del(int x) { sum[cnt[x]]-=x; cnt[x]--; sum[cnt[x]]+=x; ++tot; val[tot]=cnt[x]; } int power(int x,int p) { return 1LL*pow1[x%powsiz]*pow2[x/powsiz]%p; } int main() { scanf("%d%d",&n,&m); blosiz=sqrt(n); for (int i=1;i<=n;i++) scanf("%d",&a[i]),bel[i]=(i-1)/blosiz; 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+m+1); int l=1,r=0; for (int i=1;i<=m;i++) { while (l>q[i].l) add(a[--l]); while (r<q[i].r) add(a[++r]); while (l<q[i].l) del(a[l++]); while (r>q[i].r) del(a[r--]); int newtot=0; int len=r-l+1; for (int j=1;j<=tot;j++) if (val[j]&&sum[val[j]]!=0&&!calced[val[j]]) calced[val[j]]=1,val[++newtot]=val[j]; tot=newtot; powsiz=sqrt(len)+1; pow1[0]=pow2[0]=1; for (int j=1;j<=powsiz;j++) pow1[j]=(pow1[j-1]+pow1[j-1])%q[i].p; for (int j=1;j*powsiz<=len;j++) pow2[j]=1LL*pow2[j-1]*pow1[powsiz]%q[i].p; int powLen=power(len,q[i].p); for (int j=1;j<=tot;j++) { long long num=sum[val[j]]%q[i].p; ans[q[i].id]=(ans[q[i].id]+num*(powLen-power(len-val[j],q[i].p)))%q[i].p; calced[val[j]]=0; } ans[q[i].id]+=q[i].p; ans[q[i].id]%=q[i].p; } for (int i=1;i<=m;i++) printf("%dn",ans[i]); return 0; }