• 前言

    看到这道题,如果范围稍小一点,可以尝试将两串构造出来,然后连在一起,运用后缀排序求出hei数组进行求解,但很可惜的是,l和r太大了。

  • 思考

    我们先手造一下串
    1 a
    2 aba
    3 abacaba
    4 abacabadabacaba
    ...
    会发现中点左右的串是一样的,比如[1,7]=[9,15],[4,6]=[12,14] (下标从一开始),也就是说如果左区间大于了某一个k,我们完全可以将其平移到左区间。如果要求的区间的右端点没有大于某一个中点,直接搜下去就可以了。如果和中点有交叉的话,这个时候就要分左右搜索,取最大值

  • 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
const int N=1e4+10;
inline int dfs(int la,int ra,int lb,int rb,int k)
{//a区间左右端点,b区间左右端点,构造串的长度 
    if(k<0) return 0;
    if(la>ra||lb>rb) return 0;
    if(la>lb) swap(la,lb),swap(ra,rb);
    //不合法 
    if(ra>=rb) return rb-lb+1;
    //区间之间相互包含 
    if(la==lb) return ra-la+1;

    int len=1<<k;
    if(lb>len) return dfs(la,ra,lb-len,rb-len,k);
    //可以直接左移 
    if(ra<len&&rb<len) return dfs(la,ra,lb,rb,k-1);
    //不用改变,接着搜 
    int ans;
    ans=max(dfs(la,ra,lb,len-1,k),dfs(la,ra,1,rb-len,k));
    //有交叉 
    return max(ans,ra-lb+1);
    //交叉部分,即有重叠的部分直接算出长度 
}
int main()
{
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);

    printf("%d\n",dfs(a,b,c,d,30));

    return 0;
}