题解 P2282 【[HNOI2003]历史年份】
qwaszx
·
·
题解
截至2018.12.2 A掉这题的除了我都是抄的@Ressed dalao的...真不知道抄题解有什么意思
神仙题 蒟蒻第一次接触到hash判字符串大小、线段树优化dp
弱化版的P1415 拆分数列是一道可以在O(n^3)时间内通过的题，然后这题直接变成O(nlogn)，惹不起
分两趟dp，第一趟正着把最小的最后一个数算出来，然后再倒着把字典序最大的算出来，差不多的，只以第一趟为例说明
先写原题的dp式子,设f[i]表示把前i个数字拆成单增序列且最后一个数最小时，最后一个数的起始数字下标(也就是在第f[i]个数字前面加最后一个逗号)
这样就有f[i]=max\{j+1|num(f[j],j)<num(j+1,i),1\leq j<i\}，其中num(i,j)表示从第i到第j个数字所组成的数
这个时候的复杂度是O(n^3)
考虑降一次
字符串比较那一个地方的复杂度是O(n)的，优化它
朴素做法：找到最长的公共前缀，然后比下一位
hash$预处理，二分出公共前缀即可做到$O(logn)
降至O(n^2\log n)
然后蒟蒻打开了题解仔细思考了一番
线段树优化转移！
我们先改变一下dp的处理方式，从填表改为刷表，即由一个i去更新其他点
如果不考虑0的话，i这个点能更新的j一定满足j-i\geq i-f[i]+1，就是num(i+1,j)的位数大于等于num(f[i],i)的位数
但这是个必要条件，还需要在位数相同的时候比较一下
这样我们就可以找到i能更新的位置的最小值j，使用线段树更新[j,n]的f值(和i+1取max)
还要取出i这一点的f值，单点查询即可
这样我们在没有0的情况下做到了O(n\log n)(字符串比较、查询和修改是并列的\log n)
然后就是万恶的0，及其难以处理
引入l[i]表示i左边(含i)的第一个非0位置，r[i]表示i右边(含i)的第一个非0位置
如果第$i$位是$0$那么$l[i]=l[i-1],r[i]=r[i+1]$，否则$l[i]=r[i]=i$，两端特判
那么现在更新的$j$满足的条件变为$j-r[i+1]+1\geq i-r[f[i]]+1$，再判一下有没有等号
然后就可以把正着的做完了
倒着做的时候要定住最后一个数不动，并且最后一个数的前导零的$f$一开始全都要指向$n
除此之外还有非常多的细节，具体看代码吧qwq
```cpp
// luogu-judger-enable-o2 可爱的洛咕氧气罐
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
unsigned int h[500000],pow[500000];
char st[500000];
int f[500000],n,l0[500000],r0[500000];
void hs_make(char st[],unsigned int h[])
{
pow[0]=1;
for(int i=1;i<=strlen(st);i++)h[i]=h[i-1]*233+st[i-1]-48,pow[i]=pow[i-1]*233;
}
unsigned int hs(int l,int r){return h[r]-h[l-1]*pow[r-l+1];}
int xy(int l1,int r1,int l2,int r2)
{
if(r1-l1+1<r2-l2+1)return 1;
if(r1-l1+1>r2-l2+1)return 0;
int l=0,r=r1-l1+1,mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(hs(l1,l1+mid-1)==hs(l2,l2+mid-1))l=mid;
else r=mid-1;
}
return l!=r1-l1+1&&st[l1+l-1]<st[l2+l-1];//注意如果前缀就是整个字符串要特判
}
struct Segment_tree
{
int a[200000],tag[200000];
void build(int rot,int lt,int rt)
{
tag[rot]=a[rot]=0;
if(lt==rt)return;
int mid=(lt+rt)>>1;
build(rot<<1,lt,mid),build(rot<<1|1,mid+1,rt);
}
void pushdown(int rot,int lt,int rt)
{
if(tag[rot])
{
int t=tag[rot];tag[rot]=0;
tag[rot<<1]=max(t,tag[rot<<1]),tag[rot<<1|1]=max(t,tag[rot<<1|1]);
a[rot<<1]=max(t,a[rot<<1]),a[rot<<1|1]=max(t,a[rot<<1|1]);
}
}
int query(int rot,int lt,int rt,int q)
{
if(lt==rt)return a[rot];
int mid=(lt+rt)>>1;
pushdown(rot,lt,rt);
if(q<=mid)return query(rot<<1,lt,mid,q);
else return query(rot<<1|1,mid+1,rt,q);
}
void update(int rot,int lt,int rt,int lq,int rq,int w)
{
if(lt>rq||rt<lq)return;
if(lt>=lq&&rt<=rq)
{
a[rot]=max(a[rot],w),tag[rot]=max(tag[rot],w);
return;
}
int mid=(lt+rt)>>1;
pushdown(rot,lt,rt);
update(rot<<1,lt,mid,lq,rq,w),update(rot<<1|1,mid+1,rt,lq,rq,w);
a[rot]=max(a[rot<<1],a[rot<<1|1]);
}
}seg;//线段树
int main()
{
while(scanf("%s",st)==1)
{
hs_make(st,h);n=strlen(st);
for(int i=1;i<=n;i++)if(st[i-1]=='0')l0[i]=l0[i-1];else l0[i]=i;r0[n+1]=n+1;//端点特判
for(int i=n;i>=1;i--)if(st[i-1]=='0')r0[i]=r0[i+1];else r0[i]=i;
// for(int i=1;i<=n;i++)cout<<l0[i]<<" "<<r0[i]<<endl;
seg.build(1,0,n);
for(int i=0;i<n;i++)
{
int fi=seg.query(1,0,n,i);
int t=r0[i+1]+i-r0[fi];
if(!xy(r0[fi],i,r0[i+1],t))t++;
// cout<<i<<" "<<fi<<" "<<t<<endl;
if(t<=n)seg.update(1,0,n,t,n,i+1);
}
// for(int i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl;
int fn=seg.query(1,0,n,n);
seg.build(1,0,n);//清树
seg.update(1,0,n,l0[fn-1]+1,n,n);//先把前导零全都指向n
for(int i=fn;i>1;i--)
{
int fi=seg.query(1,0,n,i);
int t=l0[max(i-1+r0[i]-fi-1,0)]+1;//不可以是负数，特判
if(!xy(r0[t],i-1,r0[i],fi))t=r0[t]+1;
// cout<<i<<" "<<f[i]<<" "<<t<<endl;
seg.update(1,0,n,t,i-1,i-1);
}
int pos=seg.query(1,0,n,1);
for(int i=1;i<=n;i++)
{
putchar(st[i-1]);//普通的输出
if(i==pos&&i!=n)putchar(','),pos=seg.query(1,0,n,i+1);
}
putchar(10);
}
}
```