前言

開始感覺很麻煩，想想其實很清真

題目相關(guān)

題目鏈接

題目大意

給一個字符串$s$，每一個位置都有一個權(quán)值$v$
求有多少個子串滿足其倒順序排名等于子串權(quán)值和

數(shù)據(jù)范圍

$len\le 200000{，}^{\prime }{a}^{\prime }\le s_i{\le }^{\prime }{z}^{\prime }，0\le v\le 10000$

題解

考慮后綴數(shù)組（萬年不寫）
直接后綴排序、求height后
我們發(fā)現(xiàn)，對于一個后綴，我們分析以當前左端點開始的子串的情況
我們發(fā)現(xiàn)，左端點固定，子串長度越長，倒序的排名值下降，權(quán)值的和上升
所以對于一個左端點至多只有一個右端點滿足條件
可以直接二分
我們發(fā)現(xiàn)，要維護權(quán)值和很方便，直接前綴和即可
維護倒序排名值，我們發(fā)現(xiàn)每個后綴都和上個串的$lcp$排名值一樣，剩下部分補上一個公差為$1$的等差數(shù)列
直接用線段樹維護，并在線段樹上二分即可（因為要二分，所以其實可以只記錄當前區(qū)間左端點的值和一個賦值標記）
復(fù)雜度$\Theta (nlogn)$
事實證明，題解不是越長越好，我開始沒想出來這題怎么做，看了一篇很長的題解很久沒搞懂在說什么

代碼

#include<cstdio> #include<cctype> #include<cstring> #include<algorithm> namespace fast_IO {const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);} } using namespace fast_IO; #define getchar() getchar_() #define putchar(x) putchar_((x)) #define rg register typedef long long LL; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void Swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } const int maxn=200003; char s[maxn]; int sa[maxn],height[maxn],val[maxn],len; namespace SA {int xx[maxn],yy[maxn],*x,*y,b[maxn],a[maxn],p;int rank[maxn];int cmp(int i,int j,int l) { return y[i]==y[j]&&(i+l>=len?-1:y[i+l])==(j+l>=len?-1:y[j+l]);}void get_SA() { x=xx;y=yy;int m=26;for(rg int i=0;i<len;i++)x[i]=a[i],b[a[i]]++;for(rg int i=1;i<=m;i++)b[i]+=b[i-1];for(rg int i=len-1;i>=0;i--)sa[--b[x[i]]]=i;for(rg int k=1;k<=len;k<<=1){p=-1;for(rg int i=len-k;i<len;i++)y[++p]=i;for(rg int i=0;i<len;i++) if(sa[i]>=k)y[++p]=sa[i]-k;for(rg int i=0;i<=m;i++)b[i]=0;for(rg int i=0;i<len;i++)b[x[y[i]]]++;for(rg int i=1;i<=m;i++)b[i]+=b[i-1];for(rg int i=len-1;i>=0;i--)sa[--b[x[y[i]]]]=y[i];Swap(x,y);p=1;x[sa[0]]=0;for(rg int i=1;i<len;i++) x[sa[i]]=cmp(sa[i-1],sa[i],k)?p-1:p++;if(p>=len)break;m=p;}p=0;for(rg int i=0;i<len;i++)rank[sa[i]]=i;for(rg int i=0;i<len;i++){if(rank[i]==0)continue;int j=sa[rank[i]-1];while(i+p<len&&j+p<len&&s[i+p]==s[j+p])p++;height[rank[i]]=p;p=max(0,p-1);}} }; const int MAX=524288; int l[MAX],r[MAX],mid[MAX];LL irt[MAX],mark[MAX]; void ini(const int root,const int ll,const int rr) {l[root]=ll,r[root]=rr,mid[root]=(ll+rr)>>1;if(ll==rr)return;ini(root<<1,ll,mid[root]),ini(root<<1|1,mid[root]+1,rr); } void down(const int root) {if(mark[root]){if(l[root]!=r[root]){irt[root<<1]=mark[root<<1]=mark[root];irt[root<<1|1]=mark[root<<1|1]=mark[root]-mid[root]+l[root]-1;}mark[root]=0;} } void insert(const int root,const int ll,const int rr,const LL val) {if(ll==l[root]&&rr==r[root]){irt[root]=mark[root]=val;return;}down(root);if(rr<=mid[root])insert(root<<1,ll,rr,val);else if(ll>mid[root])insert(root<<1|1,ll,rr,val);else insert(root<<1,ll,mid[root],val),insert(root<<1|1,mid[root]+1,rr,val-mid[root]+ll-1);irt[root]=irt[root<<1]; } int ef(const int root,const int rr,const int begin,const int cut) {if(l[root]==r[root])return irt[root]==val[l[root]+begin]-cut?l[root]+begin:-1;down(root);if(rr<=mid[root])return ef(root<<1,rr,begin,cut);if(val[l[root<<1|1]+begin]-cut<=irt[root<<1|1])return ef(root<<1|1,rr,begin,cut);return ef(root<<1,rr,begin,cut); } LL all; struct seg {int l,r;bool operator <(const seg&b)const{return l<b.l;} }Q[maxn]; int ans; int main() {scanf("%s",s),len=strlen(s);for(rg int i=0;i<len;i++)read(val[i]);for(rg int i=0;i<len;i++)SA::a[i]=s[i]-'a'+1;SA::get_SA();ini(1,1,len);all=(LL)len*(len+1)/2;for(rg int i=1;i<len;i++)all-=height[i],val[i]+=val[i-1];for(rg int i=0;i<len;i++){if(height[i]+1<=len-sa[i])insert(1,height[i]+1,len-sa[i],all),all-=len-sa[i]-height[i];const int rr=ef(1,len-sa[i],sa[i]-1,sa[i]?val[sa[i]-1]:0);if(rr!=-1)Q[++ans]=(seg){sa[i],rr};}std::sort(Q+1,Q+ans+1);print(ans),putchar('\n');for(rg int i=1;i<=ans;i++)print(Q[i].l+1),putchar(' '),print(Q[i].r+1),putchar('\n');return flush(),0; }

總結(jié)

好久沒寫sa了
感覺不是很難，但是不知為何一開始沒理解
寫的時候由于一些細節(jié)問題調(diào)了一會兒
好像可以后綴自動機轉(zhuǎn)后綴樹做

總結(jié)

以上是生活随笔為你收集整理的[bzoj5405]platform的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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