专栏文章

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

hhighkj
AT_arc207_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minnnb3y
此快照首次捕获于
2025/12/02 05:22
3 个月前
此快照最后确认于
2025/12/02 05:22
3 个月前
查看原文

前言

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

思路

感觉这个 trick 已经烂大街了，对于固定右端点的区间或只有 log⁡V\log{V} 个，那么这个题就考虑定义 fi,jf_{i,j} 表示对于 1∼i1\sim i 最后一个值是 jj 的最大能保留的长度，然后我们发现固定了右端点 ii 所以 jj 只有 3030 个位置有值，考虑转移直接枚举一个 lstlst 然后在枚举一个 kk 即可，这样时间复杂度肯定炸了，考虑优化。
我们发现对于每一个段 l∼rl\sim r 假设这个段中所有点到 ii 的或都是一样的，那么我们就需要求出 l∼rl\sim r 中每一个 ii 的 max⁡(flst,k),k≤(ar+1∣⋯∣ai)\max(f_{lst,k}),k\leq (a_{r+1} \mid \dots \mid a_i)，我们发现这样的段数不会超过 3030 个所以考虑对于每一个段都维护一棵 gjg_j 的线段树其中 gj=max⁡(fi,j)g_j=\max(f_{i,j})，然后每次我们拓展右端点时涉及到合并段直接线段树合并即可，注意这个题要垃圾回收不然空间炸了。

代码

细节见代码，虽然能保证正确性但是被随机化吊起来打。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...