! JOISC2020DAY3星座3

并查集妙用

发现自己太菜，无法定义DP状态，只好用贪心

我们先从纵坐标小的开始贪（所在最大矩形宽度相对较小的）

题意是每个极大矩形只能留一个点，删除的最小，也就是留下的最大

我们选一个点一定是选其余点加起来都没有这个点优秀，选了这个点后，将这个点所在的极大矩形（找到左右第一个(A_i)大于此点的）的列上的点的值全减当前的收益

这样下次选到那个点是就相当于自动把这个点不选了

对列减可以将减去的内容用树状数组维护，找左右最大可以把(A_i)从小到大加入，然后用并查集依次更新

找点不用二分，直接让横坐标从小到大即可

时间复杂度(O(nlog_n))

DP也可以，但不是很懂

比如红色点指的状态是在红色线下方的最大权独立集，转移枚举橙色矩形内选了哪个点

(f_i)表示L=左侧第一个(A)比(A_i)大的位置+1，(R)=右侧第一个(A)比(A_i)大的位置 - 1，(U = min{A_{L - 1}, A_{R+1}}) 矩形区域内的最大权独立集，暴力转移(O(n^2))

绿色点的状态是绿色线下绿色区域的最大权独立集，转移枚举紫色区域内的点

考虑优化，发现选择一个点((x, y))的贡献是在笛卡尔树上(x)的左右子树的(f)之和加上不断向上走，如果向右走加上左子树状态值，向左走加上右子树状态值，树状数组维护

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=2e5+4;
struct dsu{
	int fa[N];
	inline void init(int n){
		for(int i=1;i<=n+1;i++)fa[i]=i;
	}
	int find(int x){
		return x==fa[x]?x:fa[x]=find(fa[x]);
	}
	inline void merge(int x,int y){
		x=find(x);y=find(y);
		if(x!=y)fa[x]=y;
	}
}f1,f2;
#define ll long long
#define fi first
#define se second
int n,m;
ll a[N],t[N];
vector<int>v[N];
vector<pair<int,int>>s[N];
inline void add(int x,ll v){
	for(;x<=n+1;x+=x&-x)t[x]+=v;
}
inline ll ask(int x){
	ll ret=0;
	for(;x;x-=x&-x)ret+=t[x];
	return ret;
}
int main(){
	n=read();
	f1.init(n);f2.init(n);
	for(int i=1;i<=n;i++){
		a[i]=read();
		v[a[i]].push_back(i);
	}
	m=read();
	for(int i=1,u,v,w;i<=m;i++){
		u=read();v=read();w=read();
		s[v].push_back(make_pair(u,w));
	}
	ll ans=0,tmp;
	for(int i=1;i<=n;i++){
		for(auto r:s[i]){
			tmp=ask(r.fi);
			if(r.se>=tmp){
				ans+=tmp;
				add(f1.find(r.fi)+1,r.se-tmp);
				add(f2.find(r.fi),-r.se+tmp);
			}
			else ans+=r.se;
		}
		for(auto r:v[i]){
			f1.merge(r,r-1);
			f2.merge(r,r+1);
		}
	}
	cout<<ans;
	return (0-0);
}