题解：AT_arc207_c [ARC207C] Combine to Make Non-decreasing

FS_NEO · 2025-11-15 22:57:10 · 题解

第一次切 AT *2400，纪念。你说的对但是多一只 log 过题不算过题。

设 f_{i,j} 表示操作到第 i 位，目前最后一个数是 j 的最大答案，容易得到转移。注意到对于同一个 i 的所有 [i,j] 区间异或起来答案数量只有 \log V 种，我们将这些区间大力二分找出来，差分维护转移，枚举到 i 的时候还原出 f_i 数组就行。

时间复杂度 O(n \log^2 V)，细节见代码。

/*

        2025.11.14

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
const int MAXN=200005,inf=0x3f3f3f3f;
int n,ans=1,cnt;
int f[MAXN][55],a[MAXN],lg2[MAXN];
int st[MAXN][25];
vector<int>fr[MAXN],to[MAXN];
vector<PP>g[MAXN];
unordered_map<int,multiset<int,greater<int> > >orz;
inline int gt(int l,int r){int t=lg2[r-l+1];return st[l][t]|st[r-(1<<t)+1][t];}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin>>n;memset(f,-0x3f,sizeof(f));
    lg2[1]=0;
    for(int i=2;i<MAXN;i++)lg2[i]=lg2[i/2]+1;
    for(int i=1;i<=n;i++)cin>>a[i],st[i][0]=a[i];
    for(int i=1;i<=20;i++)for(int j=1;j+(1<<i)-1<=n;j++)st[j][i]=st[j][i-1]|st[j+(1<<i-1)][i-1];
    for(int i=1;i<=n;i++){
        int x=i-1;to[i].pb(i-1);
        while(x<n){
            int l=x+1,r=n;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(gt(i,mid)==gt(i,x+1))l=mid;
                else r=mid-1;
            }
            x=l;to[i].pb(x);
        }
        x=i+1;fr[i].pb(0);
        while(x>1){
            int l=1,r=x-1;
            while(l<r){
                int mid=(l+r)>>1;
                if(gt(mid,i)==gt(x-1,i))r=mid;
                else l=mid+1;
            }
            fr[i].pb(gt(x-1,i));x=l;
        }
    }
    f[0][0]=0;fr[0].pb(0);
    for(int i=0;i<=n;i++){
        for(auto j:g[i]){
            if(j.fi==1)orz[j.se.fi].insert(j.se.se);
            else orz[j.se.fi].erase(orz[j.se.fi].find(j.se.se));
        }
        for(int j=1;j<fr[i].size();j++)if(orz[fr[i][j]].size())f[i][j]=(*(orz[fr[i][j]].begin()));
        if(i==n)break;
        for(int j=1;j<to[i+1].size();j++){
            int tf=-inf,tmp=gt(i+1,to[i+1][j]);
            for(int _=0;_<fr[i].size();_++)if(fr[i][_]<=tmp)tf=max(tf,f[i][_]);
            if(tf>=0)g[to[i+1][j-1]+1].pb({1,{tmp,tf+1}}),g[to[i+1][j]+1].pb({0,{tmp,tf+1}});
        }
    }
    for(int i=1;i<=40;i++)ans=max(ans,f[n][i]);
    cout<<ans;
    return 0;
}