BZOJ P2827 千山鸟飞绝

前言

这题调了我三天啊qwq，基本全靠自己做的（题解看不懂太蒻了\kk），但其实做完感觉并不是很难？

本题解使用 fhq-treap ，splay 党请自行跳过……

解法分析

题目意思是给一个平面直角坐标系和一些有权值的点，每个时间点会动一个点，求每个点在每个时间点中对应位置中除了它以外的最大权值，和每个时间点中对应位置中除了它以外的最大点个数的乘积（注意，是最大值的乘积）。

首先发现需要支持查询最大值和插入删除，很容易想到平衡树。

然后这个坐标实在是太大，肯定不能直接用，所以要离散化。

而在中间操作时，我们肯定不能暴力更新一个位置的所有点（可以被卡成 $O(n^2)$ ），这就需要打懒标记（这也是不用 set 的原因）。

那么，我们只需要先离线离散化一下，然后写一个权值平衡树进行插入删除查询最值，最后输出答案即可。时间复杂度是离散化加上 fhq-treap 复杂度的期望 $O((n+m)log(n+m))$ 。

实现

还是有点细节的……

我采用的方法是平衡树维护一个值和编号的二元组，方便 split 出来（这里因为不会新加入节点，可以直接用数组下标代替编号，减少码量）。

标记开两个，分别表示权值和结点数的标记，下传取 max 即可。

然后开两个答案数组分别存最大权值和最大结点数，这样因为最大值的性质，下传标记时直接对应取 max 就好了。

这里有一些我犯过的 SB 错误：

• 第一，一定要注意算值时不能算自己，所以应该先把原树打上标记再加入结点。
• 第二，split 时一定要先判权值，再判编号。
• 第三，split 和 merge 时都一定要下传标记和向上维护。
• 第四，查找最大值函数一定要判结点存不存在，没有就返回 $0$ 。
• 第五，最后一定要 dfs 一遍，把标记下传完。
• 第六，输出时一定要开 long long ！

可能只有我会犯这些错吧

代码

码风清奇请见谅\kk

#include<bits/stdc++.h>
//#define int long long
using namespace std;
namespace TYX_YNXK{
	#define il inline
	#define bl bool
	#define ll long long
	#define vd void
	#define N 30005
	#define M 300005
	#define pii pair<int,int>
	#define MP make_pair
	#define fi first
	#define se second 
	#define INF 0x3f3f3f3f
	#define DEBUG cout<<"You are right,but you are wrong"<<'\n'
	#define END cout<<"You are right,but you are right now"<<'\n'
	//以上是 气势磅礴 的宏定义，可以不用 
	int rt[N+M],tl,tm,tr;
	int n,QWQ,m,mx[N][2],val[N],zb[N];
	pii b[N+M],s[N];
	struct que{
		int v,x,y;
	}q[M];
	struct node{
		int son[2],sz,v;
		ll rd;
		int mxw,mxs;
		node(int a1=0,int a2=0,int a3=0,int a4=0,ll a5=0,int a6=0,int a7=0){
			son[0]=a1,son[1]=a2,sz=a3,v=a4,rd=a5,mxw=a6,mxs=a7;
		}
	}t[N];
	il vd pushup(int k){
		t[k].sz=t[t[k].son[0]].sz+1+t[t[k].son[1]].sz;
	}
	il vd change(int k,int a1,int a2){
		if(!k) return;
		mx[k][0]=max(mx[k][0],a1);
		t[k].mxw=max(t[k].mxw,a1);
		mx[k][1]=max(mx[k][1],a2);
		t[k].mxs=max(t[k].mxs,a2);
	}
	//change操作即打标记，一定记住要判k不为0！ 
	il vd pushdown(int k){
		if(!k) return;
		change(t[k].son[0],t[k].mxw,t[k].mxs);
		change(t[k].son[1],t[k].mxw,t[k].mxs);
		t[k].mxw=t[k].mxs=0;
	}
	vd split(int k,int &l,int &r,int v,int pos=INF){
		if(!k) return l=r=0,void(0);
		pushdown(k);
		if((t[k].v==v)?(k<=pos):(t[k].v<v)) l=k,split(t[l].son[1],t[l].son[1],r,v,pos);
		else r=k,split(t[r].son[0],l,t[r].son[0],v,pos);
		pushup(k);
	}
	//split操作在模板基础上多维护了编号信息，但也很好理解 
	int merge(int l,int r){
		if((!l)||(!r)) return l|r;
		if(t[l].rd<=t[r].rd){
			pushdown(l);
			t[l].son[1]=merge(t[l].son[1],r);
			pushup(l);
			return l;
		}
		pushdown(r);
		t[r].son[0]=merge(l,t[r].son[0]);
		pushup(r);
		return r;
	}
	il int find(int v,int k){
		if(!k) return 0;
		while(1){
			if(v==t[t[k].son[0]].sz+1) return t[k].v;
			if(v>t[t[k].son[0]].sz+1) v-=t[t[k].son[0]].sz+1,k=t[k].son[1];
			else k=t[k].son[0];
		}
	}
	//find因为懒得写最大值，所以直接第k小了\kk 
	vd dfs(int k){
		if(!k) return;
		pushdown(k);
		dfs(t[k].son[0]),dfs(t[k].son[1]);
	}
	signed main(){
		srand((unsigned ll)time(NULL));
//		srand(0);
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			int w,x,y;
			scanf("%d%d%d",&w,&x,&y);
			val[i]=w;
			s[i]=MP(x,y);
			b[++m]=MP(x,y);
		}
		scanf("%d",&QWQ);
		for(int i=1;i<=QWQ;i++){
			int v,x,y;
			scanf("%d%d%d",&v,&x,&y);
			q[i]=(que){
				v,x,y
			};
			b[++m]=MP(x,y);
		}
		sort(b+1,b+1+m);
		m=unique(b+1,b+1+m)-b-1;
		for(int i=1;i<=n;i++){
			int p=lower_bound(b+1,b+1+m,s[i])-b;
			zb[i]=p;
			int mx_w=find(t[rt[p]].sz,rt[p]),mx_s=t[rt[p]].sz;
			change(rt[p],val[i],mx_s);
			t[i]=node(0,0,1,val[i],rand());
			change(i,mx_w,mx_s);
			split(rt[p],tl,tr,val[i]);
			rt[p]=merge(tl,merge(i,tr));
		}
		for(int i=1;i<=QWQ;i++){
			int v=q[i].v,p=lower_bound(b+1,b+1+m,MP(q[i].x,q[i].y))-b;
			split(rt[zb[v]],tl,tr,val[v],v);
			split(tl,tl,tm,val[v]-1,v-1);
			rt[zb[v]]=merge(tl,tr);
			t[tm]=node(0,0,1,val[tm],t[tm].rd,0,0);
			zb[v]=p;
			int mx_w=find(t[rt[p]].sz,rt[p]),mx_s=t[rt[p]].sz;
			change(rt[p],val[v],mx_s);
			change(tm,mx_w,mx_s);
			split(rt[p],tl,tr,val[v]);
			rt[p]=merge(tl,merge(tm,tr));
		}
		for(int i=1;i<=m;i++){
			dfs(rt[i]);
		}
		for(int i=1;i<=n;i++){
			printf("%lld\n",1ll*mx[i][0]*mx[i][1]);
		}
		return 0;
	}
}
signed main(){
	TYX_YNXK::main();
	return 0;
}