Abracadabra

• 前言

  看到这道题，如果范围稍小一点，可以尝试将两串构造出来，然后连在一起，运用后缀排序求出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;
}