题解 P3732 【[HAOI2017]供给侧改革】
Pine
2018-02-25 10:19:42
# trie树
$\qquad$**因为01串是随机的，所以lcp的长度不会太长，~~据说有个公式，蒟蒻表示不会~~，所以我们猜测lcp长度都不超过40，这样我们就将每一个后缀的前40个位置插入到trie树中即可。**
$\qquad$**从左到右将后缀的前40位插入字典树，字典树路径上存下最后一次访问该点的是以哪一个位置开始后缀，第二次访问这个深度为dep节点的时候就表示当前后缀与之前的一个后缀的$lcp\ge dep$，维护一下这40个值就可以了，查询的时候，直接访问这40个值。**
# 代码
```
#include <bits/stdc++.h>
#define R register
#define eps 1e-12
#define INF (1<<30)
#define LL long long
#define LINF (1ll<<60)
#define MM(x, y) memset(x, y, sizeof x)
#define Fo(i, x, y) for(R int i=x; i<=y; ++i)
#define Ro(i, x, y) for(R int i=x; i>=y; --i)
using namespace std;
template<typename T> inline T Max(R T x, R T y) {return x > y ? x : y;}
template<typename T> inline T Min(R T x, R T y) {return x < y ? x : y;}
template<typename T> inline void in(R T &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; ch>='0'&&ch<='9'; ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
/*************************************Samle*************************************/
#define N 100005
int cnt, n, Q, fina[50*N], o[50*N], son[50*N][2]; LL ans[N]; char ch[N];
struct QUE{int l, r, id;}q[N];
bool operator < (R QUE a, R QUE b) {return a.r < b.r || (a.r == b.r && a.l < b.l);}
inline void insert(R int x)
{
R int p = 0;
for(int i=0; x+i<=n&&i+1<=40; ++i)
{
R int w = ch[x+i] - '0';
if(!son[p][w])
{
son[p][w] = ++cnt;
fina[cnt] = x;
}
else
{
o[i+1] = Max(o[i+1], fina[son[p][w]]);
fina[son[p][w]] = x;
}
p = son[p][w];
}
}
int main()
{
in(n), in(Q); scanf("%s", ch+1);
Fo(i, 1, Q) in(q[i].l), in(q[i].r), q[i].id = i;
sort(q+1, q+Q+1); R int T = 1;
Fo(i, 1, n)
{
insert(i);
while(T <= Q && q[T].r == i)
{
for(R int i=1; i<=40; ++i)
{
if(o[i] >= q[T].l)
ans[q[T].id] += 1ll * i * (o[i]-Max(q[T].l-1, o[i+1]));
else
break;
}
++T;
}
}
Fo(i, 1, Q) printf("%lld\n", ans[i]);
return 0;
}
```