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

· · 题解

前言

这勾史学校停课，直接快把我送走了，赛后看了下这场好像不是很难。

思路

感觉这个 trick 已经烂大街了，对于固定右端点的区间或只有 \log{V} 个，那么这个题就考虑定义 f_{i,j} 表示对于 1\sim i 最后一个值是 j 的最大能保留的长度，然后我们发现固定了右端点 i 所以 j 只有 30 个位置有值，考虑转移直接枚举一个 lst 然后在枚举一个 k 即可，这样时间复杂度肯定炸了，考虑优化。

我们发现对于每一个段 l\sim r 假设这个段中所有点到 i 的或都是一样的，那么我们就需要求出 l\sim r 中每一个 i 的 \max(f_{lst,k}),k\leq (a_{r+1} \mid \dots \mid a_i)，我们发现这样的段数不会超过 30 个所以考虑对于每一个段都维护一棵 g_j 的线段树其中 g_j=\max(f_{i,j})，然后每次我们拓展右端点时涉及到合并段直接线段树合并即可，注意这个题要垃圾回收不然空间炸了。

代码

细节见代码，虽然能保证正确性但是被随机化吊起来打。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define fire signed
#define il inline
template<class T> il void print(T x) {
    if(x<0) printf("-"),x=-x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
const int N=2e5+10,M=(1<<30);
struct node{
    int l,r;
    int mx;
}tr[N*30*10];
vector<int>rb;
int rt[N],fa[N],l[N],r[N],a[N],idx;
void up(int x) {
    tr[x].mx=max(tr[tr[x].l].mx,tr[tr[x].r].mx);
}
const int inf=1e9;
void modify(int &u,int l,int r,int x,int k) {
    if(!u) {
        if(rb.size()) {
            u=rb.back();
            tr[u].l=tr[u].r=false;
            rb.pop_back();
        }else u=++idx;
        tr[u].mx=-inf;
    }
    if(l==r) {
        tr[u].mx=max(tr[u].mx,k);
        return;
    }
    int mid=l+r>>1;
    if(mid>=x) modify(tr[u].l,l,mid,x,k);
    else modify(tr[u].r,mid+1,r,x,k);
    up(u);
}
int Ans(int u,int l,int r,int x) {
    if(!u) return -inf;
    if(l==r) return tr[u].mx;
    int mid=l+r>>1;
    if(mid>=x) return Ans(tr[u].l,l,mid,x);
    return max(Ans(tr[u].r,mid+1,r,x),tr[tr[u].l].mx);
}
int merge(int x,int y,int l,int r) {
    if(!x||!y) return x+y;
    if(l==r) {
        tr[x].mx=max(tr[x].mx,tr[y].mx);
        rb.pb(y);
        return x;
    }
    int mid=l+r>>1;
    rb.pb(y);
    tr[x].l=merge(tr[x].l,tr[y].l,l,mid);
    tr[x].r=merge(tr[x].r,tr[y].r,mid+1,r);
    up(x);
    return x;
}
int f[N][20],lg[N];
int Ans(int l,int r) {
    int len=lg[r-l+1];
    return (f[l][len]|f[r-(1<<len)+1][len]);
}
int find(int x) {
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int n;
void solve() {
    in(n);
    tr[0].mx=-inf;
    rep(i,1,n) in(a[i]),f[i][0]=a[i];
    rep(i,2,n) lg[i]=lg[i>>1]+1;
    rep(j,1,lg[n]) {
        rep(i,1,n-(1<<j)+1) {
            f[i][j]=(f[i][j-1]|f[i+(1<<j-1)][j-1]);
        }
    }
    rep(i,1,n) {
        fa[i]=i,l[i]=r[i]=i;
    }
    modify(rt[1],1,M,a[1],1);
    rep(i,2,n) {
        int lst=find(i-1);
        vector<pair<int,int>>ve;
        while(true) {
            lst=find(lst);
            int now=Ans(r[lst]+1,i);
            int dis=Ans(rt[lst],1,M,now);
            modify(rt[i],1,M,now,dis+1);
            if(!lst) break;
            ve.pb({lst,now});
            lst=l[lst]-1;
        }
        int sum=Ans(1,i);
        modify(rt[i],1,M,sum,1);
        reverse(ve.begin(),ve.end());
        int len=ve.size();
        len--;
        rep(j,0,len-1) {
            if(ve[j].second==ve[j+1].second) {
                int itx=ve[j].first,ity=ve[j+1].first;
                rt[ity]=merge(rt[find(ve[j].first)],rt[find(ve[j+1].first)],1,M);
                fa[itx]=ity;
                l[ity]=l[itx];
            }
        }
    }
    printf("%d\n",Ans(rt[find(n)],1,M,M));
}
fire main() {
    while(T--) {
        solve();
    }
    return false;
}