【学习笔记】[JSOI2019]节日庆典

学习笔记】[JSOI2019]节日庆典"/>

【学习笔记】[JSOI2019]节日庆典

考虑枚举右端点到 r r r时，维护可能成为答案的位置的集合。显然对于相邻两个元素 i , j i,j i,j，我们有 lcp(S[i:],S[j:]) > r − j \text{lcp(S[i:],S[j:])}>r-j lcp(S[i:],S[j:])>r−j，否则可以删去 i , j i,j i,j其中之一。画图不难发现我们只需要保证对于任意 k k k，满足 lcp(S[i:],S[k:]) > r − k \text{lcp(S[i:],S[k:])}>r-k lcp(S[i:],S[k:])>r−k，也就是只用和第一个位置进行比对。注意 lcp \text{lcp} lcp的长度是不随右端点 r r r变化的，可以看成常数。

假设已经检查完了 i i i之前的所有位置，那么对于之后的一个位置 j j j，假设 j − i < r − j j-i<r-j j−i<r−j，那么不难发现 S [ i : j ) = S [ j : 2 j − i ) S[i:j)=S[j:2j-i) S[i:j)=S[j:2j−i)，我们记这一段为 A A A（更确切地说 A A A是 S [ i : r ] S[i:r] S[i:r]的周期）， 2 j − i 2j-i 2j−i以后的为 B B B，那么我们得到 A + A + B , A + B + A , B + A + A A+A+B,A+B+A,B+A+A A+A+B,A+B+A,B+A+A三种方案。容易观察出中间那种肯定是不优的，也就是 j j j一定不优。那么有 2 j ≥ r + i 2j\ge r+i 2j≥r+i，显然只有最多 log ⁡ \log log个需要检查，这道题就做完了。因为 lcp \text{lcp} lcp已经匹配到了底所以用 z z z函数辅助检查一下即可。

复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)。

代码咕了。其实是我不会打 z z z函数

至于维护集合那个部分，可以自己编一个做法，事实上发现每次暴力重构就完了。

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N=3e6+5;
int n,z[N],res;
string s;
vector<int>f,g;
int solve(int pos1,int pos2,int last){if(pos1==-1)return 1;pos1+=last-pos2+1;if(z[pos1]<last-pos1+1){return s[z[pos1]]<s[pos1+z[pos1]];}pos1=last-pos1+1;if(pos1+z[pos1]>=pos2)return 0;return s[z[pos1]]>s[pos1+z[pos1]];
}
void ins(int pos,int last){while(g.size()&&s[g.back()+last-pos]!=s[last]){if(s[g.back()+last-pos]<s[last])return;g.pop_back();}if(!g.size()||2*pos>=last+g.back()){g.pb(pos);}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>s,n=s.size();for(int i=1,l=0,r=0;i<n;i++){if(r>=i&&z[i-l]<r-i+1)z[i]=z[i-l];else{z[i]=max(0,r-i+1);while(i+z[i]<n&&s[i+z[i]]==s[z[i]])z[i]++;}if(i+z[i]-1>r)l=i,r=i+z[i]-1;}for(int i=0;i<n;i++){g.clear(),res=-1;for(auto x:f)ins(x,i);ins(i,i),f=g;for(auto x:g){if(solve(res,x,i))res=x;}cout<<res+1<<" ";}
}