洛谷3732：[HAOI2017]供给侧改革——题解

题解"/>

洛谷3732：[HAOI2017]供给侧改革——题解

Anihc国提高社会生产力水平.落实好以人民为中心的发展思想。决定进行供给侧结构性改革。

为了提高供给品质.你调查了某个产业近来n个时期的供求关系平衡情况.每个时期的情况都用0或1中的一个数字来表示.于是这就是—个长度为n的01字符串S。为了更好的了解这一些数据.你需要解决一些询问.我们令data(l,r)表示：在字符串S中.起始位置在[l,r]之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。

对于每一个询问L,R.求sigma(data(i,R))。

由于你其实根本没有时间调查，所以这些数据都是乱编的，即串S中的每一位都是在0和1之间随机产生的。

参考：

最后一句话很皮，于是我们思考下发现公共前缀一定很短，连（看）猜（题）带（解）蒙大概是40吧。

于是我们把询问离线，按照$r$排序，从左到右扫一遍$i$，将以$i$为首的40位字符加入到trie树中，以此维护$pos[k]$表示最小的区间$[pos[k],i]$，使得$data(pos[k],i)=k$。

（还是很好维护的，如果不知道怎么维护可以看参考也可以直接看代码。）

为什么我们构造了$pos$数组呢？其实是因为$data$的单调不增性。

由此我们发现$data(pos[k+1]+1,i)$到$data(pos[k],i)$都是$k$。

答案就呼之欲出了。

#include<queue>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X;
}
struct node{int a[2],ed;
}tr[N*40];
struct data{int l,r,id;
}d[N];
char s[N];
int n,q,tot,pos[50];
ll ans[N];
inline bool cmp(data a,data b){return a.r<b.r;
}
void insert(int st){int now=0;for(int i=st;i<=min(n,st+39);i++){int w=s[i]-'0';if(!tr[now].a[w])tr[now].a[w]=++tot;now=tr[now].a[w];if(tr[now].ed)pos[i-st+1]=max(pos[i-st+1],tr[now].ed-i+st);tr[now].ed=i;}
}
int main(){n=read(),q=read();scanf("%s",s+1);for(int i=1;i<=q;i++){d[i].l=read(),d[i].r=read();d[i].id=i;}sort(d+1,d+q+1,cmp);for(int i=1,j=1;i<=n;i++){insert(i);while(j<=q&&d[j].r==i){for(int k=1;k<=40;k++){if(pos[k]>=d[j].l){ans[d[j].id]+=(ll)k*(pos[k]-max(pos[k+1],d[j].l-1));}else break;}j++;}}for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：/+

+++++++++++++++++++++++++++++++++++++++++++

转载于:.html