好题记录

我是大鸽子。慢慢更新吧。

CF666E

跑一边后缀数组，转化为区间l,r值域为pl,pr的众数。

由于并不强制在线，考虑莫队。

莫队做完值域分块，支持单点修改区间查询max。

加法是简单的，减法不好做，于是就回滚一下就好了。

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int N=6e5+3;
int n,B,Q,BA,BB,pr[N],col[N],cnt[N],sx[N],sy[N],al[N],ar[N],ap[N];
char ch[N];
bool vis[N];
struct Suffix_Array
{
    int m=200,X[N],Y[N],c[N],sa[N],height[N],rk[N],num[N],lg[N],st[N][23];
    void Sa()
    {
        for(int i=1;i<=n;i++)X[i]=num[i],c[X[i]]++;
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[X[i]]--]=i;
        for(int k=1,p=0;k<=n;k=k<<1,p=0)
        {
            for(int i=n-k+1;i<=n;i++)Y[++p]=i;
            for(int i=1;i<=n;i++)if(sa[i]>k)Y[++p]=sa[i]-k;
            for(int i=1;i<=m;i++)c[i]=0;
            for(int i=1;i<=n;i++)c[X[i]]++;
            for(int i=2;i<=m;i++)c[i]+=c[i-1];
            for(int i=n;i>=1;i--)sa[c[X[Y[i]]]--]=Y[i],Y[i]=0;
            swap(X,Y);p=1;X[sa[1]]=1;
            for(int i=2;i<=n;i++)
            {
                if(Y[sa[i]]==Y[sa[i-1]]&&Y[sa[i]+k]==Y[sa[i-1]+k])X[sa[i]]=p;
                else X[sa[i]]=++p;
            }
            if(n==p)return;m=p;
        }
    }
    void Height()
    {
        int k=0;
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        for(int i=1;i<=n;i++)
        {
            if(rk[i]==1)continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<=n&&j+k<=n&&num[i+k]==num[j+k])k++;
            height[rk[i]]=k;
        }
    }
    void St()
    {
        for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++)st[i][0]=height[i];
        for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
    }
    int Lcp(int l,int r)
    {
        int d=lg[r-l+1];
        return min(st[l][d],st[r-(1<<d)+1][d]);
    }
}SA;
struct Nod{int l,r,ql,qr,id;}a[N];
bool CA(Nod a,Nod b)
{
    return vis[a.id]!=vis[b.id]?vis[a.id]>vis[b.id]:ap[a.l]!=ap[b.l]?a.l<b.l:a.r<b.r;
}
#define mi ((l+r)/2+1)
void Baoli(int p)
{
    for(int i=a[p].l;i<=a[p].r;i++)if(a[p].ql<=col[i]&&col[i]<=a[p].qr)cnt[col[i]]++;
    for(int i=a[p].l;i<=a[p].r;i++)
        if(a[p].ql<=col[i]&&col[i]<=a[p].qr&&(cnt[col[i]]>sx[p]||(cnt[col[i]]==sx[p]&&col[i]<sy[p])))
            sx[p]=cnt[col[i]],sy[p]=col[i];
    for(int i=a[p].l;i<=a[p].r;i++)cnt[col[i]]=0;
}
void Pre()
{
    BA=sqrt(n);int t=n/BA;if(n%BA)t++;
    for(int i=1;i<=t;i++)al[i]=ar[i-1]+1,ar[i]=i*BA;
    ar[t]=n;
    for(int i=1;i<=t;i++)for(int j=al[i];j<=ar[i];j++)ap[j]=i; 
}
struct Block
{
    int val[N],mx[N],my[N],vval[N],mmx[N],mmy[N],bl[N],br[N],bp[N];
    void Clear(){for(int i=0;i<=B;i++)val[i]=mx[i]=my[i]=vval[i]=mmx[i]=mmy[i]=0;}
    void Init()
    {
        BB=sqrt(B);int t=B/BB;if(B%BB)t++;
        for(int i=1;i<=t;i++)bl[i]=br[i-1]+1,br[i]=i*BB;
        br[t]=B;
        for(int i=1;i<=t;i++)for(int j=bl[i];j<=br[i];j++)bp[j]=i; 
    }
    void Add(int x,int op)
    {
        if(!x)return;
        val[x]++;int y=bp[x];
        if(val[x]>mx[y]||(val[x]==mx[y])&&x<my[y])mx[y]=val[x],my[y]=x;
        if(!op)mmx[y]=mx[y],mmy[y]=my[y],vval[x]=val[x];
    }
    void Del(int x)
    {
        if(!x)return;
        val[x]=vval[x];int y=bp[x];mx[y]=mmx[y],my[y]=mmy[y];
    }
    void Chk(int &x,int &y,int px,int py){if(px>x||(px==x&&py<y&&py))x=px,y=py;}
    void Ask(int x,int l,int r)
    {
        int y=a[x].id;
        if(bp[l]==bp[r])
        {
            for(int i=l;i<=r;i++)Chk(sx[y],sy[y],val[i],i);
            return;
        }
        for(int i=l;i<=br[bp[l]];i++)Chk(sx[y],sy[y],val[i],i);
        for(int i=bl[bp[r]];i<=r;i++)Chk(sx[y],sy[y],val[i],i);
        for(int i=bp[l]+1;i<bp[r];i++)Chk(sx[y],sy[y],mx[i],my[i]);
    }
}BL;
int main()
{
    cin>>(ch+1);n=strlen(ch+1);cin>>B;
    for(int i=1;i<=n;i++)SA.num[i]=ch[i]; 
    for(int t=1;t<=B;t++)
    {
        cin>>(ch+1);int z=strlen(ch+1);SA.num[++n]=++SA.m;
        for(int i=1;i<=z;i++)SA.num[++n]=ch[i],pr[n]=t;
    }
    cin>>Q;SA.Sa();SA.Height();SA.St();Pre();
    for(int i=1;i<=n;i++)col[i]=pr[SA.sa[i]]; 
    for(int i=1;i<=Q;i++)
    {
        cin>>a[i].ql>>a[i].qr>>a[i].l>>a[i].r;a[i].id=i;sy[i]=a[i].ql;
        int x=SA.rk[a[i].l],len=a[i].r-a[i].l+1,l=1,r=n-x;
        while(l<r)(SA.Lcp(x+1,x+mi)>=len)?l=mi:r=mi-1;
        a[i].r=(x==n||SA.height[x+l]<len)?x:x+l;l=1,r=x-1;
        while(l<r)(SA.Lcp(x-mi+1,x)>=len)?l=mi:r=mi-1;
        a[i].l=(x==1||SA.height[x-l+1]<len)?x:x-l;
        if(ap[a[i].l]==ap[a[i].r])Baoli(i),vis[i]=1;
    }
    sort(a+1,a+Q+1,CA);BL.Init();
    for(int i=1;i<=Q;i++)if(!vis[a[i].id])
    {
        int x=a[i-1].r+1,y=ap[a[i].l];
        if(i==1||vis[a[i-1].id]||ap[a[i].l]!=ap[a[i-1].l])BL.Clear(),x=al[y+1];
        for(int j=x;j<=a[i].r;j++)BL.Add(col[j],0);
        for(int j=ar[y];j>=a[i].l;j--)BL.Add(col[j],1);
        BL.Ask(i,a[i].ql,a[i].qr);
        for(int j=ar[y];j>=a[i].l;j--)BL.Del(col[j]);
    }
    for(int i=1;i<=Q;i++)cout<<sy[i]<<" "<<sx[i]<<endl;
}