PA2020 Tekstówka

do_while_true · 2024-02-20 14:13:56 · 题解

像一棵海草海草海草海草，浪花里舞蹈。

差不多是抄来的题解/wq。

首先对 S 作猫树分治，把询问挂在第一次分割出它的那个节点处。现在需要做的问题就是需要快速处理这样的询问 f(i,j,k)=LCS(X[i,j],Y[1,k])，询问 T[l,r] 时利用其处理出 T[l,r] 每个前缀和 S 左半区间后缀的 LCS，每个后缀和 S 右半区间前缀的 LCS，再选最优的拼接方案即可。不考虑处理 LCS，这部分的时间复杂度是 \mathcal{O}(qm) 的。

考虑这样的性质：

①：f(i-1,j,k)>f(i-1,j-1,k)\Rightarrow f(i,j,k)>f(i,j-1,k)

②：f(i,j,k)>f(i,j,k-1)\Rightarrow f(i-1,j,k)>f(i-1,j,k-1)

这里照抄一下证明。考虑一张网格图，如果 X_i=Y_j 则 (i,j)\to (i+1,j+1) 有一条斜向上的路径，将 LCS 视作一条斜向上次数最多的路径。

对于 ①，考虑 (i-1,1) 到 (j+1,k+1) 的路径 C_1，与 (i,1) 到 (j,k+1) 的路径 C_2，它们代表了 f(i-1,j,k),f(i,j-1,k)。它们必有一交点，假设为 A。将 C_2 在 A 之前的路径替换为 C_1 在 A 之前的路径，得到一条 \leq f(i-1,j-1,k) 的路径，根据假设有 A 后面的路径满足 C_1>C_2。

同样地将 C_2 在 A 之后的路径替换为 C_1 在 A 之后的路径，得到一条路径 P 满足 P\leq f(i,j,k) 的路径 P，而 C_2 替换了一个更大的路径得到 P，于是有 f(i,j-1,k)=C_2<P\leq f(i,j,k)，得证。

对于 ② 也是同理的。

这两条性质表明：

①：j\gets j+1 时，会 +1 的是个后缀，记为 p(k,j)（j 是 +1 后的，\geq p(k,j) 的 +1）。

②：k\gets k+1 时，会 +1 的是个前缀，记为 q(k,j)（k 是 +1 后的，<q(k,j) 的 +1）。

我们令 F=f(i,j-1,k-1),P=p(k-1,j),Q=q(k,j-1)。

当 X_j\neq Y_k 时，若 P<Q：

对比 (1) 和 (3) 得 p(k,j)=Q，对比 (2) 和 (3) 得 q(k,j)=P。

当 X_j\neq Y_k 且 P\geq Q 时：

对比 (1) 和 (3)，(2) 和 (3) 得到：p(k,j)=P,q(k,j)=Q.

类似地，X_j=Y_k 时，f(i,j,k) 一定为 F+1，此时 p(k,j)=Q,q(k,j)=P。综上，我们得到了：

初始 p(0,i)=i+1，将 p,q 都递推出来后再处理原问题只需用差分得到 f。

对于挂着询问的线段树节点都要 \mathcal{O}(len\times m) 跑出来 p,q，所以总的时间复杂度是 \mathcal{O}((q+n\log n)m)。

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
#include<assert.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
template<typename T>T cmin(T &x, T y){return x=x<y?x:y;}
template<typename T>
T &read(T &r){
    r=0;bool w=0;char ch=getchar();
    while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
    return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int N=3010;
struct DS{
    int n,m;
    char s[N],t[N];
    int p[N][N],q[N][N],o[N][N];
    //LCS(s[i,j], t[1,k])
    void solve(){
        for(int i=0;i<=n;i++)p[i][0]=i+1;
        for(int i=0;i<=m;i++)q[0][i]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                const int P=p[i][j-1],Q=q[i-1][j];
                if(s[i]!=t[j]&&P>=Q)p[i][j]=P,q[i][j]=Q;
                else p[i][j]=Q,q[i][j]=P;
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                o[j][i]=p[i][j];
    }
}ds1,ds2;
int n,m,q;
char s[N],t[N];
struct Node{
    int a,b,c,d,id;
};
vector<Node>vec[N*4];
void modify(int x,int tl,int tr,Node &o){
    int mid=(tl+tr)>>1;
    if(o.b<=mid)modify(x<<1,tl,mid,o);
    else if(o.a>mid)modify((x<<1)|1,mid+1,tr,o);
    else vec[x].push_back(o);
}
int s1[N],s2[N],ans[100010];
void dfs(int x,int tl,int tr){
    if(tl==tr)return ;
    int mid=(tl+tr)>>1;
    if(!vec[x].empty()){
        ds1.m=0;
        for(int i=mid;i>=tl;i--)ds1.t[++ds1.m]=s[i];
        ds1.solve();

        ds2.m=0;
        for(int i=mid+1;i<=tr;i++)ds2.t[++ds2.m]=s[i];
        ds2.solve();
        for(auto o:vec[x]){
            int a=o.a,b=o.b,c=o.c,d=o.d,id=o.id;
            for(int i=c-1;i<=d+1;i++)s1[i]=s2[i]=0;
            for(int i=m-d+1;i<=m-c+1;i++){
                int l=m-i+1,r=m-ds1.o[mid-a+1][i]+1;
                s1[l]++,s1[r+1]--;
            }
            for(int i=c;i<=d+1;i++)s1[i]+=s1[i-1];
            for(int i=c;i<=d;i++){
                int l=max(c,ds2.o[b-mid][i]),r=i;
                if(l<=r)
                    s2[l]++,s2[r+1]--;
            }
            for(int i=c;i<=d+1;i++)s2[i]+=s2[i-1];
            int mx=0;
            for(int i=c;i<=d+1;i++)
                mx=max(mx,s1[i-1]+s2[i]);
            ans[id]=mx;
        }
    }
    dfs(x<<1,tl,mid);
    dfs((x<<1)|1,mid+1,tr);
}
signed main(){
    read(n);read(m);read(q);
    scanf("%s%s",s+1,t+1);
    ds1.n=0;
    for(int i=m;i>=1;i--)ds1.s[++ds1.n]=t[i];
    ds2.n=0;
    for(int i=1;i<=m;i++)ds2.s[++ds2.n]=t[i];
    for(int i=1;i<=q;i++){
        int a,b,c,d;read(a);read(b);read(c);read(d);
        Node o={a,b,c,d,i};
        if(a!=b)modify(1,1,n,o);
        else{
            for(int j=c;j<=d;j++)
                if(t[j]==s[a]){
                    ans[i]=1;
                    break;
                }
        }
    }
    dfs(1,1,n);
    for(int i=1;i<=q;i++)cout << ans[i] << '\n';
    return 0;
}