题解：CF2121H Ice Baby

题解区怎么只有离散化线段树，这里给个动态开点线段树做法，复杂度是

\mathcal O(n\log w)

的。

Problem

题目很简单，

a_i

可以从

[l_i,r_i]

中选择，问你最后最大的最长不降子序列。

Solution

设状态

f_i

表示当前最后一个数字（最大的数字）为

i

，转移有两种：

能取最小肯定贪心地取最小的 $l_i$ 更优 $f_{l_i}$ 可以从小于 $l_i$ 的地方转移过来，即：

$f_{l_i}\gets \max_{j\in [1,l_i-1]}{f_j}+1$ 。
从同样的数字转移肯定不增加更优所以：

$f_j\gets f_j+1 ,{j\in [l_i,r_i]}$

于是，就可以~~暴力地~~愉快地线段树了。

我们需要一个区间

+1

操作和一个单点修改操作。

因为懒得离散化，所以直接动态开点了。

注意：使用线段树询问

1\sim l_i-1

最大值时可能会越界，需要特判一下，否则会 RE。

Code

CPP

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define all(x) x.begin(),x.end()
using namespace std;
template<typename T_>void Max(T_&x,const T_&y){if(y>x)x=y;}
template<typename T_>void Min(T_&x,const T_&y){if(y<x)x=y;}
template<typename T_>void operator+=(vector<T_>&x,const T_&y){x.push_back(y);}
template<typename T_>void operator--(vector<T_>&x){x.pop_back();}
const int N=2e5+7,_=1e9;
int T,n,mx[N*64],lzy[N*64],ls[N*64],rs[N*64],cnt,rot;//开大点准没错
void f(int rt,int x){mx[rt]+=x,lzy[rt]+=x;}
void push_down(int rt){
	if(!lzy[rt])return;
	if(!ls[rt])ls[rt]=++cnt;//这里要开点，否则信息会丢失
	if(!rs[rt])rs[rt]=++cnt;
	f(ls[rt],lzy[rt]),f(rs[rt],lzy[rt]);
	lzy[rt]=0;
}
void push_up(int rt){mx[rt]=max(mx[ls[rt]],mx[rs[rt]]);}
void update(int x,int l,int r,int k,int&rt){
	if(!rt)rt=++cnt;
	if(l==r)return Max(mx[rt],k);
	int mid=(l+r)>>1;push_down(rt);
	if(x<=mid)update(x,l,mid,k,ls[rt]);
	else update(x,mid+1,r,k,rs[rt]);
	push_up(rt);
}
void add(int L,int R,int l,int r,int k,int&rt){
	if(!rt)rt=++cnt;
	if(L<=l&&r<=R)return f(rt,k);
	int mid=(l+r)>>1;push_down(rt);
	if(L<=mid)add(L,R,l,mid,k,ls[rt]);
	if(R>mid)add(L,R,mid+1,r,k,rs[rt]);
	push_up(rt);
}
int query(int L,int R,int l,int r,int rt){
	if(L>R||!rt)return 0;//特判
	if(L<=l&&r<=R)return mx[rt];
	int mid=(l+r)>>1,res=0;push_down(rt);
	if(L<=mid)Max(res,query(L,R,l,mid,ls[rt]));
	if(R>mid)Max(res,query(L,R,mid+1,r,rs[rt]));
	return res;
}
void work(){
	cin>>n;
	for(int i=1,l,r,x;i<=n;i++){
		cin>>l>>r;
		x=query(1,l-1,1,_,rot);
		add(l,r,1,_,1,rot);//区间加
		update(l,1,_,x+1,rot);//单点修改
		cout<<query(1,_,1,_,rot)<<' ';//询问 max
	}
	cout<<'\n';
	for(int i=0;i<=cnt;i++)ls[i]=rs[i]=lzy[i]=mx[i]=0;
	cnt=rot=0;//清空用过的就行
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)work();
	return 0;
}

题解：CF2121H Ice Baby

文章操作

Problem

Solution

Code

相关推荐

评论

题解：CF2121H Ice Baby