并不对劲的复健训练-bzoj5253:loj2479:p4384:[2018多省联考]制胡窜

Dear 丶 2023-08-17 16:46 92阅读 0赞

##### 题目大意 #####

给出一个字符串\\(S\\)，长度为\\(n\\)（\\(n\\leq 10^5\\)），\\(S\[l:r\]\\)表示\\(S\_l,S\_\{l+1\}...,S\_r\\)这个子串。有\\(m\\)（\\(m\\leq 3\\times 10^5\\)）次询问，每次询问给出\\(l,r\\)，问有多少对\\((i,j)\\)（\\(1\\leq i<i+1<j\\leq n\\)），使与\\(S\[l:r\]\\)本质相同的子串出现在\\(S\[1:i\]\\)中或\\(S\[i+1:j-1\]\\)中或\\(S\[j:n\]\\)中。

##### 题解 #####

询问相当于是问有多少种方案在\\(S\\)中找两个缝隙切两刀，使两刀不重合，且存在一个与\\(S\[l:r\]\\)本质相同的子串没被切。  
这个比较难考虑，可以把它转换成 在\\(n-1\\)个缝隙中选两个的总方案数-所有与\\(S\[l:r\]\\)本质相同的子串都被切的方案数。  
所有与\\(S\[l:r\]\\)本质相同的子串都被切的方案数分以下几种情况考虑：  
一、\\(S\\)中存在三个与\\(S\[l:r\]\\)本质相同的子串，且其中每两个的交集大小不超过1  
会发现此时怎么切两刀都切不全这三个串，方案数为0。  
二、\\(S\\)中不存在三个与\\(S\[l:r\]\\)本质相同的子串，且其中每两个的交集大小不超过1：假设所有这样的子串的最左的左端点为\\(ll\\)，最左的右端点为\\(lr\\)，最右的左端点为\\(rl\\)，最右的右端点为\\(rr\\)，\\(S\[l:r\]\\)长度为\\(len\\)，\\(r\_i\\)表示right集合的第\\(i\\)个。  
\\(\\space\\space\\space\\space\\) 1.\\(S\\)中所有与\\(S\[l:r\]\\)本质相同的子串的交集不为空  
\\(\\space\\space\\space\\space\\) \\(\\space\\space\\space\\space\\)(1)靠前的一刀没切到与\\(S\[l:r\]\\)本质相同的子串：另一刀必须切在所有这样的子串的交集\\(\[rl,lr\]\\)上。这部分答案=\\(ll\\times (lr-rl)\\)。注意刀只能切在缝隙上，所以是\\((rl-lr)\\)而不是\\((rl-lr+1)\\)。  
\\(\\space\\space\\space\\space\\) \\(\\space\\space\\space\\space\\)(2)靠前的一刀切到了一些与\\(S\[l:r\]\\)本质相同的子串，但没切在所有与\\(S\[l:r\]\\)本质相同的子串的交集上：会发现第二刀肯定要切在第一刀没切到的子串的交集上。所以对于两种方案，当它们第一刀切的串相同时，第二刀可行的取值范围相同。两种方案的第一刀都在\\(\[r\_i-len+1,r\_\{i+1\}-len+1)\\)时，它们切的串都是\\(\[1,i\]\\)这个区间中的,它们第二刀的取值范围都是\\(\[rl,r\_\{i+1\}\]\\)。也就是说，这部分答案=\\(\\sum(r\_\{i+1\}-r\_i)\\times(r\_\{i+1\}-rl)\\)  
\\(\\space\\space\\space\\space\\) \\(\\space\\space\\space\\space\\)(3)靠前的一刀切到所有与\\(S\[l:r\]\\)本质相同的子串的交集上：其实这部分与(1)合并后就是“存在一刀切在所有与\\(S\[l:r\]\\)本质相同的子串的交集上，但靠前的一刀不是(2)的情况”。两刀都切在交集上的方案数是\\(C\_\{lr-rl\}^2\\)。对于只有一刀切在交集上的情况，相当于其中一刀不能在\\(\[lr-len+1,lr\]\\)上，另一刀必须在\\(\[lr,rl\]\\)上，所以这部分是 \\((n-len)\\times(lr-rl)\\)。也就是说(1)和(3)总共是\\(C\_\{lr-rl\}^2+(n-len)\\times(lr-rl)\\)。  
\\(\\space\\space\\space\\space\\) 2. \\(S\\)中所有与\\(S\[l:r\]\\)本质相同的子串的交集为空：两刀必须都切到与\\(S\[l:r\]\\)本质相同的子串，且都切不到这些子串的交集，和上一种情况的(2)类似。但是第一刀可能切不到最左的串，\\(\[rl,r\_\{i+1\}\]\\)也可能是空集。发现当\\(r\_i-len+1<lr\\)且\\(r\_\{i+1\}>rl\\)时，第一刀切在\\(\[r\_i,r\_\{i+1\})\\)都是合法的。这种情况的答案是\\(\\sum\\limits\_\{r\_\{i+1\}>rl\}^\{r\_i-len+1<lr\}(r\_\{i+1\}-r\_i)\\times(r\_\{i+1\}-rl)\\)。还可能有一段\\(\[r\_i,r\_\{i+1\})\\)，满足\\(lr\\in\[r\_i-len+1,r\_\{i+1\}-len+1)\\)即\\((lr+len-1)\\in\[r\_i,r\_\{i+1\})\\)，这一段中比较靠前的地方\\(\[r\_i-len+1,lr\]\\)可以切，靠后的不可以切。计算这种情况需要求\\(lr+len-1\\)左边第一个right集合的元素\\(r\_p\\)和右边第一个\\(r\_s\\)。这部分的答案是\\((lr-r\_p+len-1)\\times (r\_s-rl)\\)，需要注意的是，当\\(r\_s\\leq rl\\)时这部分的答案是0。

需要维护right集合和\\(\\sum(r\_\{i+1\}-r\_i)\\times(r\_\{i+1\}-rl)\\)，可以拆成\\(s\_1(l,r)=\\sum(r\_\{i+1\}-r\_i)\\)和\\(s\_2(l,r)=\\sum(r\_\{i+1\}-r\_i)\\times r\_\{i+1\}\\)，这样就可以线段树维护区间right集合中最左和最右，合并时\\(s1(l,r)=s1(l,mid)+s1(mid+1,r)+min(mid+1,r)-max(l,mid)\\)，\\(s2(l,r)=s2(l,mid)+s2(mid+1,r)+(min(mid+1,r)-max(l,mid))\\times min(mid+1,r)\\)。  
求right集合需要线段树合并。据说不离线的话，“可持久化 线段树合并”会MLE。

##### 代码 #####

#include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(register int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
    #define view(u,k) for(int k=fir[u];~k;k=nxt[k])
    #define LL long long
    #define maxn 100007
    #define maxnd 200007
    #define maxq 300007
    #define maxk 6400007
    #define ls son[u][0]
    #define rs son[u][1]
    #define mi (l+r>>1)
    #define Ls(u) son[u][0]
    #define Rs(u) son[u][1]
    #define pb push_back
    #define int long long
    using namespace std;
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)&&ch!='-')ch=getchar();
        if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
        return x*f;
    }
    void write(LL x)
    {
        if(x==0){putchar('0'),putchar('\n');return;}
        int f=0;char ch[20];
        if(x<0)putchar('-'),x=-x;
        while(x)ch[++f]=x%10+'0',x/=10;
        while(f)putchar(ch[f--]);
        putchar('\n');
        return;
    }
    int n,ch[maxnd][10],dis[maxnd],rt[maxnd],fa[maxnd],pt[maxn],lst,cnt,rot;
    int son[maxk][2],cntnd,m,c[maxn],ord[maxnd],anc[maxnd][20];
    char s[maxn];
    LL ans[maxq];
    struct node{int mx,mn;LL sum[2];}tr[maxk];
    struct quest{int l,r,id;};
    vector<quest>qt[maxnd];
    void gt(node & x,node y){x.mx=y.mx,x.mn=y.mn,x.sum[0]=y.sum[0],x.sum[1]=y.sum[1];return;}
    void pu(node & x,node ld,node rd)
    {
        x.mx=rd.mx,x.mn=ld.mn,x.sum[0]=ld.sum[0]+rd.sum[0]+(LL)(rd.mn-ld.mx),x.sum[1]=ld.sum[1]+rd.sum[1]+(LL)(rd.mn-ld.mx)*rd.mn; 
        return;
    }
    int build(int u,int l,int r,int x)
    {
        if(!u)u=++cntnd;
        if(x<=l&&r<=x){tr[u].mx=tr[u].mn=x,tr[u].sum[0]=tr[u].sum[1]=0;return u;}
        if(x<=mi)ls=build(ls,l,mi,x);
        else rs=build(rs,mi+1,r,x);
        if(!ls||!rs)gt(tr[u],tr[ls|rs]);
        else pu(tr[u],tr[ls],tr[rs]);return u;
    }
    int merge(int ua,int ub,int l,int r)
    {
        if(!ua||!ub)return ua|ub;
        Ls(ua)=merge(Ls(ua),Ls(ub),l,mi);
        Rs(ua)=merge(Rs(ua),Rs(ub),mi+1,r);
        if(!Ls(ua)||!Rs(ua))gt(tr[ua],tr[Ls(ua)|Rs(ua)]);
        else pu(tr[ua],tr[Ls(ua)],tr[Rs(ua)]);return ua;
    }
    void ask(int u,int l,int r,int x,int y,node & k)
    {
        if(!u||x>y)return;
        if(x<=l&&r<=y){if(k.mx==0)gt(k,tr[u]);else pu(k,k,tr[u]);return;}
        if(x<=mi&&ls)ask(ls,l,mi,x,y,k);
        if(y>mi&&rs)ask(rs,mi+1,r,x,y,k);
        return;
    }
    int pref(int u,int x){node kk;kk.mx=kk.mn=0,ask(u,1,n,1,x,kk);return kk.mx;}
    int sufx(int u,int x){node kk;kk.mx=kk.mn=0,ask(u,1,n,x,n,kk);return kk.mn;}
    int gx(char c){return c-'0';}
    void ext(int i)
    {
        int p=lst,v=gx(s[i]),np=++cnt;dis[np]=i,lst=pt[i]=np;rt[np]=build(rt[np],1,n,i);
        for(;p&&!ch[p][v];p=fa[p])ch[p][v]=np;
        if(!p)fa[np]=rot;
        else
        {
            int q=ch[p][v];
            if(dis[p]+1==dis[q])fa[np]=q;
            else
            {
                int nq=++cnt;
                dis[nq]=dis[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],fa[q]=fa[np]=nq;
                for(;p&&ch[p][v]==q;p=fa[p])ch[p][v]=nq;
            }
        }
    }
    int tp[maxq];
    LL c2(int x){return (LL)x*(x-1)/2ll;}
    signed main()
    {
        rot=lst=cnt=1;
        scanf("%d%d%s",&n,&m,s+1);
        rep(i,1,n)ext(i);
        rep(i,1,cnt)c[dis[i]]++;
        rep(i,1,n)c[i]+=c[i-1];
        rep(i,1,cnt)ord[c[dis[i]]--]=i;
        rep(j,1,cnt)
        {
            int i=ord[j];
            anc[i][0]=fa[i];
            rep(k,1,19)anc[i][k]=anc[anc[i][k-1]][k-1];
        }
        rep(i,1,m)
        {
            int l=read(),r=read(),nd=pt[r];
            dwn(j,19,0)if(dis[anc[nd][j]]>=r-l+1)nd=anc[nd][j];
            quest q;q.l=l,q.r=r,q.id=i;qt[nd].pb(q);
        }
        dwn(j,cnt,1)
        {
            int i=ord[j],sz=qt[i].size(),rr=tr[rt[i]].mx,lr=tr[rt[i]].mn;
            rep(k,0,sz-1)
            {
                int len=qt[i][k].r-qt[i][k].l+1,rl=rr-len+1,nd3=0;
                if(lr+len-1<=n)nd3=sufx(rt[i],lr+len-1);
                if(nd3&&nd3<=rl){tp[qt[i][k].id]=3;continue;}
                if(lr>rl){tp[qt[i][k].id]=1;ans[qt[i][k].id]=-tr[rt[i]].sum[0]*((LL)rl)+tr[rt[i]].sum[1]+c2(lr-rl)+(LL)(lr-rl)*(n-len);}
                else
                {
                    int sec,fst=pref(rt[i],rl);
                    node kk;kk.mx=kk.mn=0;if(fst)ask(rt[i],1,n,fst,lr+len-1,kk);
                    if(kk.mx)ans[qt[i][k].id]=-(LL)rl*kk.sum[0]+kk.sum[1];
                    fst=sec=0;
                    if(lr+len-1<=n)fst=pref(rt[i],lr+len-1),sec=sufx(rt[i],lr+len-1);
                    if(sec&&fst&&sec>rl)ans[qt[i][k].id]+=(LL)(lr-fst+len-1)*(sec-rl);
                    tp[qt[i][k].id]=2;
                }
            }
            rt[fa[i]]=merge(rt[fa[i]],rt[i],1,n);
        } 
        rep(i,1,m){write(c2(n-1)-ans[i]);}
        return 0;
    }

##### 一些感想 #####

写一下调一年，自闭不花一分钱

转载于:https://www.cnblogs.com/xzyf/p/11559743.html