P9747

i_am_not_feyn · 2023-10-17 14:53:55 · 题解

个人认为 CSP 应该并不会考什么复杂的 DS，这道题的难度基本上都在实现上了。

首先观察一个序列合法的条件。

注意到操作并不会使得某一个一开始存在的二进制位消失，并且要求最后的序列全为一个数，那么显然这个数就是整个序列的或。

下文中令四元组 (l1,r1,l2,r2) 表示一次操作。

令这个数为 mx，若序列中没有 mx 则显然是非法的。假定有两个 mx 在序列中的位置分别为 i,i+1，那么可以通过 (i,i+1,i+1,i+2) 或者 (i,i+1,i-1,i) 使得 mx 向两边扩展，最终使得序列全为 mx。

若有一个 mx 的位置为 i，且右边有一区间 [i+1,r] 的或等于 mx，则可以通过 (i,r-1,i+1,r) 使得 i+1 的位置为 mx，转化为上述情况。区间在左边也是同理的。

故而一个序列是合法的当且仅当可以找到一个 mx 和一个不包含这个 mx 的或为 mx 的区间。

对于原序列的每个位置 i 作为某个区间的 mx 时，这个区间 [L_i,R_i] 的或应该为 a_i，L_i R_i 是容易求出的。若要使这个区间合法，那么可以求出 l_i 表示最大的 l 使得 [l,i) 的或包含了 a_i，r_i 同理。令当前询问的区间为 [l',r']，则有以下两种情况 i 会做出 \min(r',R_i)-\max(l',L_i)+1 的贡献。

1. l_i\ge L_i,l_i\ge l'
2. r_i\le R_i,r_i\le r'

只考虑 1 的情况，2 的话倒着再做一遍就是。接下来就是没有脑子的套路了。

显而易见的，将 l_i<L_i 的 i 踢出去不考虑，把 l 后往前扫描线一下，每次扫到一个新的 l 就将 l_i=l 的 i 加进线段树中。现在线段树中的节点均满足 1 的条件，只需要在 i\in[l,r'] 中找到最优解即可。

由于不好处理 \max(l,L_i)，考虑将所有的 i 按照是否小于 l 插入 AB 线段树中。由于 l 是逐渐变小的，那么 A 是要支持删除的。

A 中元素的贡献是 \min(r',R_i)-l'+1，那么只用维护区间中 i 的 R 最大值即可，删除就是单点赋值为 0。

B 中元素的贡献是 \min(r',R_i)-L_i+1，由于不带修，则可以直接维护每个 r' 的答案。在 [i,R_i] 的区间插入 -L_i+1，在 (R_i,n] 的区间插入 R_i-L_i+1，每次就是单点查询两种情况的最大值，标记永久化即可。

时间是 O(n\log n) 的，由于这个解法没啥脑子基本上就是大力分讨，常数颇高，但是 7s 的时限还是稳过的。

code

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+50,M=8e6+50,inf=1e9+7;

namespace IO {
//IO 由于是贺别人的所以不是很能放出来
} // IO
using namespace IO;

int T,Tid,n,q,a[N],m=30,Ans[N];

struct ask
{
    int l,r,id;

    friend bool operator<(ask a,ask b)
    {
        return a.l<b.l;
    }
}Q[N];

#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)

class sukwants
{
    public:
        int mx[M],d,val,L,R,ans;

        void add(int x,int l,int r)
        {
            if(l==r)return void(mx[x]=val);
            if(d<=mid)add(ls,l,mid);
            else add(rs,mid+1,r);
            mx[x]=max(mx[ls],mx[rs]);
        }

        void find(int x,int l,int r)
        {
            if(L<=l&&R>=r)return void(ans=max(ans,mx[x]));
            if(L<=mid)find(ls,l,mid);
            if(R>mid)find(rs,mid+1,r);
        }

        void add(int a,int b){d=a,val=b;add(1,1,n);}
        int find(int l,int r){L=l,R=r;ans=0;find(1,1,n);return ans;}
}sgt;

class sukwats
{
    public:
        int val[M],w[M],L,R,d,ans;

        void Insert(int x,int l,int r)
        {
            if(L<=l&&R>=r)return void(val[x]=max(val[x],d));
            if(L<=mid)Insert(ls,l,mid);
            if(R>mid)Insert(rs,mid+1,r);
        }

        void Add(int x,int l,int r)
        {
            if(L<=l&&R>=r)return void(w[x]=max(w[x],d));
            if(L<=mid)Add(ls,l,mid);
            if(R>mid)Add(rs,mid+1,r);
        }

        void find(int x,int l,int r)
        {
            ans=max(ans,max(val[x],w[x]+d));
            if(l==r)return;
            return (d<=mid)?find(ls,l,mid):find(rs,mid+1,r);
        }

        void insert(int l,int r,int v){L=l,R=r,d=v;Insert(1,1,n);}
        void add(int l,int r,int v){L=l,R=r,d=v;Add(1,1,n);}
        int find(int x){d=x;ans=0;find(1,1,n);return ans;}
}sgc;

void dfs(int x,int l,int r)
{
    sgt.mx[x]=0;sgc.val[x]=sgc.w[x]=-inf;
    if(l!=r)dfs(ls,l,mid),dfs(rs,mid+1,r);
}

int L[N],R[N],rel[N],rer[N],fir[2][32],las[2][32];

class shabi_ds
{
    public:
        int a[N],L[N],R[N],re[N];
        vector<int>in[N],out[N];

        void clear()
        {
            for(int i=1;i<=n;i++)vector<int>().swap(in[i]),vector<int>().swap(out[i]);
        }

        void pre()
        {
            sort(Q+1,Q+1+q);dfs(1,1,n);clear();
            for(int i=1;i<=n;i++)if(re[i]>=L[i])in[re[i]].push_back(i),out[L[i]].push_back(i);
        }

        void solve()
        {
            pre();int pos=q;
            for(int i=n;i>=1;i--)
            {
                for(auto x:in[i])sgt.add(x,R[x]);
                for(auto x:out[i])
                {
                    sgt.add(x,0),sgc.add(x,R[x],-L[x]+1),sgc.insert(R[x],n,R[x]-L[x]+1);
                }
                while(pos&&Q[pos].l==i)
                {
                    int x=min(Q[pos].r,sgt.find(Q[pos].l,Q[pos].r)),y=sgc.find(Q[pos].r);
                    Ans[Q[pos].id]=max(Ans[Q[pos].id],max(x-i+1,y)),pos--;
                }
            }
        }
}A,B;

void init()
{
    for(int i=1;i<=n;i++)L[i]=1,R[i]=n,rel[i]=rer[i]=i;
    for(int i=0;i<=m;i++)fir[1][i]=0,las[1][i]=n+1;
    for(int ty=0,i=1;i<=n;i++,ty^=1)for(int j=0;j<=m;j++)
    if((a[i]>>j)&1)rel[i]=min(rel[i],fir[ty^1][j]),fir[ty][j]=i;
    else fir[ty][j]=fir[ty^1][j],L[i]=max(L[i],fir[ty][j]+1);
    for(int ty=0,i=n;i>=1;i--,ty^=1)for(int j=0;j<=m;j++)
    if((a[i]>>j)&1)rer[i]=max(rer[i],las[ty^1][j]),las[ty][j]=i;
    else las[ty][j]=las[ty^1][j],R[i]=min(R[i],las[ty][j]-1);
    for(int i=1;i<=n;i++)
    {
        A.L[i]=L[i],A.R[i]=R[i],A.re[i]=rel[i];
        B.R[n-i+1]=n-L[i]+1,B.L[n-i+1]=n-R[i]+1,B.re[n-i+1]=n-rer[i]+1;
    }
}

void sol()
{
    read(n);read(q);
    for(int i=1;i<=n;i++)read(a[i]),A.a[i]=B.a[n-i+1]=a[i];
    for(int i=1;i<=q;i++)read(Q[i].l),read(Q[i].r),Q[i].id=i,Ans[i]=1;
    init();A.solve();
    for(int i=1;i<=q;i++)Q[i].l=n-Q[i].l+1,Q[i].r=n-Q[i].r+1,swap(Q[i].l,Q[i].r);
    B.solve();
    for(int i=1;i<=q;i++)write(Ans[i]);
}

main()
{
    read(T),read(Tid);
    while(T--)sol();
}