uoj296/P5211:zjoi2017 字符串

shadowice1984

2019-01-19 14:39:51

Solution

爆肝好题啊…… 我给你讲,这题炒鸡休闲的,我也就写了7.7个k…… ~~怎么zjoi的题都是思维难度高代码实现难度大的duliu题啊~~ ______________ ## 前置芝士:线段树 蛤?不会线段树敢来淦zjoi? ## 前置芝士:字符串哈希 ~~不会蛤希的可以出门左转你站模板区包教包会~~ _______________ # 本题题解 首先我们看到一个肥肠劲爆的操作,维护一个字符串,支持**区间加** 这就十分出乎我们的意料了,我们通常学的串串都是给定一个静态字符串然后询问一些奇奇怪怪的东西,但是这道题不仅询问了一个区间最小后缀这种神奇的东西还要资瓷一个非常有毒的区间加操作…… 那么让我们先从一个naive的静态做法开始……(和正解的联系不是很大,可以选择性阅读) ## 静态做法 由于这是一个静态串我们可以求出字符串的后缀数组来,那么我们现在至少知道了每一个后缀在全局的排名了 那么我们现在需要求出$(l,r]$这段区间内字典序最小的以$r$结尾的后缀了 我们不妨把这个字符串分成两段来看,先求出$(l,mid]$中字典序最小的后缀,然后求出$(mid,r]$中字典序最小的后缀 然后接下来我们的算法简易的令人吃鲸,只要我们保证左侧区间的长度小于等于右侧区间的长度,那么我们只需要求出$(l,mid]$中**全局**字典序最小的后缀然后和右侧区间的结果取个min就能得到答案了 **注意:刚才的描述混用了子串和后缀的概念,以r结尾的后缀其实是整个字符串的一个子串,我们刚才的算法流程其实是将$(pos,r)$和右侧区间分治之后返回的结果取了一个min,其中$(pos,n)$是左端点在$(l,mid]$当中字典序最小的后缀** 为什么这个看起来假的捕星的算法其实是正确的呢? 我们的算法唯一假的地方就是用$(pos,r)$替换了以r结尾的,左端点在$(l,pos]$当中字典序最小的后缀 那么我们来考虑一下当$(pos,r)$是假后缀的时候会发生什么状况 换句话讲就是$(pos,r)$并不是左侧区间当中字典序最小的后缀,存在一个比他更小的串S 那么我们知道$(pos,n)$是全局最小的后缀,那么换句话讲肯定是两个子串分出大小的位置在$r$之后导致另外一个子串由于长度较短,导致在以$r$结尾时字典序较小的串不是$(pos,r)$了 这只能说明一件事,S既是$(pos,r)$的前缀还是$(pos,r)$的后缀,并且S还是一个长度过半的公共前后缀,因为我们右侧区间的长度比左侧区间长度大 那么$(pos,r)$就是一个有周期的串了,所以不好意思$(pos,r)$和S都不是$(l,r)$当中字典序最小的后缀,字典序最小的后缀在右侧区间,而我们求出来的假后缀则会被取min给取掉 所以我们就得到了一个$O(logn)$的优秀静态做法(如果使用st表可以做到$O(1)$回答每个询问) ## 动态做法 当然你也看到了这个静态做法没有任何抢救的空间了,我们首先需要求出全局最小的后缀才行,但是现在有动态修改我们不能用后缀数组了…… 那么我们不妨把刚才的做法反过来,使用线段树维护整个序列,自底向下的求出答案 但是首先我们需要合并左右两个区间 采用左开右闭的建树方式,我们可以保证左孩子的长度永远小于等于右孩子的区间长度,那么我们仿照静态做法,尝试用长度过半的前后缀与周期串之间的关系来搞事情…… 那么我们采用这样一个策略,在每个区间上维护将来可能成为最小字典序后缀的位置,换句话说线段树上每个节点开一个vector存储所有可能成为最小字典后缀的位置 那么假如我们知道了左儿子的vector和右儿子的vector,我们来考虑一下如何得到这个节点的vector 首先这个节点应该继承右孩子的vector,因为右孩子存储的子串后面并没有添加东西,所以这些后缀依然有潜力 接下来我们考虑处理左孩子的vector,我们把左孩子中的串都拉出来并且在这些字符串的后面怼上一个右孩子对应的字符串 接下来我们开始比较这些字符串的字典序大小,如果两个串u,v(这里认为u比v长)满足v不是u的前缀,那么证明这两个字符串已经比出字典序大小了,我们留下字典序更小的那个就可以了 接下来是一个比较有趣的情况,如果v是u的前缀,我们应该留下u而不是v,尽管看起来此时v的字典序更小 为啥呢?我们发现u有过半的公共前后缀,所以u是个周期串 那么我们发现v现在就不是字典序最小的串,至少这个字符串一个更短的周期z就比他小,那么在整个字符串后怼上一个字符之后v有没有潜力成为字典序最小的后缀呢? 答案是否定的,如果加上一个字符之后v仍然是周期串那么v还是凉的,如果加上一个字符之后整个串不再是周期串,我们比较一下这个字符是比应该填的字符大还是小,如果大的话u的字典序比v小如果小的话z的字典序比v小,无论如何v都是凉的 那么如此这般我们发现左孩子中只有一个元素可以加入到父亲节点的vector里,那么这样看来每个节点的vector的size就是log级别的 那么现在询问就非常的好处理了,反正$m$只有3w,我们3个log乱搞完全能过,我们把询问的区间在线段树上拆分成log个区间然后大力取min就做完了 修改也非常的好处理,容易看出如果一个区间被整体加上一个值之后有潜力成为字典序最小后缀的串是没有变化的,那么在一次区间加操作之后我们只需要修改$O(logn)$个节点的vector,暴力合并左右孩子就行了 好了看起来我们需要资瓷的操作就是区间加比较两个字符串的大小,也就是说区间加求两个后缀的lcp 后缀数组和sam都凉了,我们还是老老实实二分哈希求lcp吧 这里我们使用分块来维护hash值,这样我们一次修改是$O(\sqrt{N})$的而查询一次的复杂度是$O(1)$的~~其实常数很大~~ 这里有一个trick就是我们需要在整个字符串加上或者减去一个数字的情况下快速得知hash值,其实非常简单,我们把bas开到3e8的级别,然后直接把原来的hash值加上或者减去aaaaaaaa这样的字符串的hash值就可以了,为了避免减出负数来我们还需要把每个数字加上一个很大的数字以避免负数 如此这般实现两个数据结构,我们就以丢人的$O(nlog^2n+m(log^3n+\sqrt{N}))$完成了这题…… 啊,uoj前面那些人怎么那么块啊? 把hash换成暴力lcp即可,实现简单,由于数据水还不会被卡 当然你也可以用自然溢出hash,不要像我一样很蠢的用双hash 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=2*1e5+10;const int B=450;typedef long long ll; const ll bas=3*1e8+19;const int shif=bas/2;int n;int mde[N];int m;int rk[N<<1]; const ll mod1=998244353;const ll mod2=1e9+7;int TP; inline ll po(ll a,ll p,ll mod){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;} namespace hsa//分块维护hash值 { int bi[N];int bj[N];ll mi1[N];ll imi1[N];ll mi2[N]; ll imi2[N];ll pre1[N];ll pre2[N];ll sf1[N];ll sf2[N]; struct blk { int ch[B+3];ll pr1[B+3];ll pr2[B+3];ll sp1[B+3];ll sp2[B+3];int ad;int siz; inline int& operator [](const int& x){return ch[x];} inline void calh() { for(int i=1;i<=siz;i++)pr1[i]=(pr1[i-1]+mi1[i-1]*ch[i])%mod1; for(int i=1;i<=siz;i++)pr2[i]=(pr2[i-1]+mi2[i-1]*ch[i])%mod2; }inline void ih() { for(int i=1;i<=siz;i++)sp1[i]=(sp1[i-1]+mi1[i-1])%mod1; for(int i=1;i<=siz;i++)sp2[i]=(sp2[i-1]+mi2[i-1])%mod2;calh(); }inline void badd(int l,int r,int del) {for(int i=1;i<=siz;i++)ch[i]+=ad;for(int i=l;i<=r;i++)ch[i]+=del;ad=0;calh();} inline ll gh1(int x){return (pr1[x]+sp1[x]*(mod1+ad))%mod1;} inline ll gh2(int x){return (pr2[x]+sp2[x]*(mod2+ad))%mod2;} }bl[N/B+3]; inline void calp(int st) { for(int i=st;i<=bi[n];i++)pre1[i]=(pre1[i-1]+bl[i].gh1(bl[i].siz)*sf1[i-1])%mod1; for(int i=st;i<=bi[n];i++)pre2[i]=(pre2[i-1]+bl[i].gh2(bl[i].siz)*sf2[i-1])%mod2; } inline void ih(int* mde) { for(int i=1;i<=n;i++)bi[i]=(i-1)/B+1;for(int i=1;i<=n;i++)bj[i]=(i-1)%B+1; mi1[0]=1;for(int i=1;i<=n;i++)mi1[i]=mi1[i-1]*bas%mod1; mi2[0]=1;for(int i=1;i<=n;i++)mi2[i]=mi2[i-1]*bas%mod2; imi1[0]=1;ll iv=po(bas,mod1-2,mod1);for(int i=1;i<=n;i++)imi1[i]=imi1[i-1]*iv%mod1; imi2[0]=1;iv=po(bas,mod2-2,mod2);for(int i=1;i<=n;i++)imi2[i]=imi2[i-1]*iv%mod2; for(int i=1;i<=n;i++)bl[bi[i]][bj[i]]=mde[i]; for(int i=1;i<bi[n];i++)bl[i].siz=B;bl[bi[n]].siz=(n%B)?n%B:B; for(int i=1;i<=bi[n];i++)bl[i].ih(); sf1[0]=1;for(int i=1;i<=bi[n];i++)sf1[i]=sf1[i-1]*mi1[bl[i].siz]%mod1; sf2[0]=1;for(int i=1;i<=bi[n];i++)sf2[i]=sf2[i-1]*mi2[bl[i].siz]%mod2;calp(1); } inline ll gh1(int p){int t=bi[p]-1;return (pre1[t]+bl[t+1].gh1(bj[p])*sf1[t])%mod1;} inline ll gh2(int p){int t=bi[p]-1;return (pre2[t]+bl[t+1].gh2(bj[p])*sf2[t])%mod2;} inline void modify(int l,int r,int del) { int p1=bi[l];int p2=bi[r];if(p1==p2){bl[p1].badd(bj[l],bj[r],del);goto ed;} bl[p1].badd(bj[l],bl[p1].siz,del);bl[p2].badd(1,bj[r],del); for(int i=p1+1;i<p2;i++)bl[i].ad+=del;ed:calp(p1); } inline bool ck(int p1,int p2,int len) { ll v1=(gh1(p1+len-1)+mod1-gh1(p1-1))*imi1[p1-1]%mod1; ll v2=(gh1(p2+len-1)+mod1-gh1(p2-1))*imi1[p2-1]%mod1; if(v1!=v2)return false; v1=(gh2(p1+len-1)+mod2-gh2(p1-1))*imi2[p1-1]%mod2; v2=(gh2(p2+len-1)+mod2-gh2(p2-1))*imi2[p2-1]%mod2;return v1==v2; } inline int gt(int x){return bl[bi[x]][bj[x]]+bl[bi[x]].ad;} } struct str//字符串类 { int st;int len; friend bool operator <(str a,str b) { int c1=hsa::gt(a.st);int c2=hsa::gt(b.st);if(c1!=c2)return c1<c2; int l=0;int r=min(a.len,b.len); if(hsa::ck(a.st,b.st,r))return (a.len>b.len)^TP;r--; while(l!=r) {int mid=(l+r+1)>>1;if(hsa::ck(a.st,b.st,mid))l=mid;else r=mid-1;} return hsa::gt(a.st+l)<hsa::gt(b.st+l); }friend str operator +(str a,int b){return (str){a.st,a.len+b};} }; struct linetree//线段树 { str v[N<<2][20];int cnt[N<<2];str ans; inline void mg(int p,int p1,int p2,int len)//合并两个节点 { cnt[p]=cnt[p2];for(int i=1;i<=cnt[p2];i++)v[p][i]=v[p2][i]; str mi=v[p1][1]+len;for(int i=2;i<=cnt[p1];i++)mi=min(mi,v[p1][i]+len); v[p][++cnt[p]]=mi; } inline void build(int p,int l,int r) { if(r-l==1){v[p][++cnt[p]]=(str){r,1};return;}int mid=(l+r)>>1; build(p<<1,l,mid);build(p<<1|1,mid,r);mg(p,p<<1,p<<1|1,r-mid); } inline void modify(int p,int l,int r,int dl,int dr) { if(dl==l&&r==dr){return;}int mid=(l+r)>>1; if(dl<mid)modify(p<<1,l,mid,dl,min(dr,mid)); if(mid<dr)modify(p<<1|1,mid,r,max(dl,mid),dr);mg(p,p<<1,p<<1|1,r-mid); } inline void qry(int p,int l,int r,int dl,int dr,int pos) { if(dl==l&&dr==r) { int i=1;if(ans.st==-1)ans=(str){v[p][1].st,pos-v[p][1].st+1},i=2; for(;i<=cnt[p];i++)ans=min(ans,(str){v[p][i].st,pos-v[p][i].st+1});return; }int mid=(l+r)>>1; if(dl<mid)qry(p<<1,l,mid,dl,min(dr,mid),pos); if(mid<dr)qry(p<<1|1,mid,r,max(dl,mid),dr,pos); } inline int cqry(int l,int r){ans=(str){-1,0};qry(1,0,n,l-1,r,r);return ans.st;} }lt; int main() { scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&mde[i]); for(int i=1;i<=n;i++)mde[i]+=shif;hsa::ih(mde);lt.build(1,0,n); for(int i=1,tp,l,r,d;i<=m;i++) { scanf("%d%d%d",&tp,&l,&r); if(tp==1) { scanf("%d",&d),TP=0;for(int i=l;i<=r;i++)mde[i]+=d; hsa::modify(l,r,d),lt.modify(1,0,n,l-1,r); } else {TP=1;printf("%d\n",lt.cqry(l,r));} }return 0;//拜拜程序~ } ```