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

https://www.luogu.org/problemnew/show/P3732

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

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

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

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

参考：https://msy.blog.luogu.org/solution-p3732

最后一句话很皮，于是我们思考下发现公共前缀一定很短，连（看）猜（题）带（解）蒙大概是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+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int a[],ed;

}tr[N*];

struct data{

    int l,r,id;

}d[N];

char s[N];

int n,q,tot,pos[];

ll ans[N];

inline bool cmp(data a,data b){

    return a.r<b.r;

}

void insert(int st){

    int now=;

    for(int i=st;i<=min(n,st+);i++){

        int w=s[i]-'';

        if(!tr[now].a[w])tr[now].a[w]=++tot;

        now=tr[now].a[w];

        if(tr[now].ed)

            pos[i-st+]=max(pos[i-st+],tr[now].ed-i+st);

        tr[now].ed=i;

    }

}

int main(){

    n=read(),q=read();

    scanf("%s",s+);

    for(int i=;i<=q;i++){

        d[i].l=read(),d[i].r=read();

        d[i].id=i;

    }

    sort(d+,d+q+,cmp);

    for(int i=,j=;i<=n;i++){

        insert(i);

        while(j<=q&&d[j].r==i){

            for(int k=;k<=;k++){

                if(pos[k]>=d[j].l){

                    ans[d[j].id]+=(ll)k*(pos[k]-max(pos[k+],d[j].l-));

                }else break;

            }

            j++;

        }

    }

    for(int i=;i<=q;i++)printf("%lld\n",ans[i]);

    return ;

}

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

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

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

巴特西

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

最新文章

热门文章