一、题目

点此看题

二、解法

0x01 暴力dp

观察数据范围发现，本题允许$O(n^2)$O(n2)的算法，考虑$dp$dp。我们做$n$n次$dp$dp，每次固定左端点，移动右端点并记录，每次更新左端点。最后更新包含其的询问，详见代码。

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1000005;
int read()
{
    int x=0,flag=1;char c;
    while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*flag;
}
int n,m,s[N],a[N],f[N],l[N],r[N],ans[N];
int main()
{
    n=read();m=read();
    for(int i=1;i<N;i++)
        s[i]=s[i-1]^i;
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=m;i++)
        l[i]=read(),r[i]=read();
    for(int i=1;i<=n;i++)
    {
        f[i]=a[i];
        for(int j=i+1;j<=n;j++)
            f[j]=max(f[j-1],s[min(a[i],a[j])-1]^s[max(a[i],a[j])]);
        for(int j=1;j<=m;j++)
            if(i>=l[j] && i<=r[j])
                ans[j]=max(ans[j],f[r[j]]);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
}

0x02 tire树和回滚莫队

由于本题求最大值，加入容易删除难，我们使用回滚莫队。

建出两个$tire$tire，分别表示$a_i$ai​作为大数（右端点）和小数（左端点）的情况。大树用$f(0,a_i)$f(0,ai​)插入，小树用$f(0,a_i-1)$f(0,ai​−1)插入，由于本题要求 $a_x\leq a_y$ax​≤ay​，所以小树的每个节点维护最小值，大树维护最大值。

每次加入时查找异或起来最大的，然后更改$tire$tire，时间复杂度$O(n\sqrt n\log a)$O(nn​loga)。

咕咕咕

• 点赞
• 收藏
• 分享
• • 文章举报

C202044zxy 发布了211 篇原创文章 · 获赞 12 · 访问量 4790 私信 关注