洛谷P4200 千山鸟飞绝
题意
有(n)只鸟在一个二维平面上，每只鸟都有一个威武值，每只鸟的士气值为处在和它同一坐标的鸟中的最大威武值，团结值为处在和它同一坐标的鸟的个数，计算士气值和团结值时不能算上自己。
每只鸟的初始威武值和坐标为(w,x,y)。
一共有(t)秒，鸟王每秒会发出一个指令(v,x,y)，表示命令编号为(v)的鸟移动到坐标((x,y))。
每只鸟的战斗力为这(t)秒中它的最大士气值乘上它的最大团结值，计算每只鸟的战斗力。
分析
把鸟看做点。
对坐标离散化后对每个坐标开一个splay，维护在这个坐标的所有点的集合，对每个点维护他的最大士气值和最大团结值，在splay中加入一个点(x)时，用splay中的最大威武值和size来更新(x)的最大士气值和最大团结值，然后在splay的根节点上打上两个标记来更新这个集合中所有点，一个标记是(x)的威武值，另一个是集合的size，在splay操作和插入操作中下传标记即可。
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=3e5+10;
const int inf=1e9;
int ch[N][2],fa[N],val[N],tag1[N],tag2[N],sz[N],rt[N],tot=0;
int ans1[N],ans2[N];
int w[N],q[N],a[N];
struct Splay{
void maintain(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
val[x]=max(max(val[ch[x][0]],val[ch[x][1]]),w[x]);
}
bool get(int x){return x==ch[fa[x]][1];}
void clear(int x){ch[x][0]=ch[x][1]=fa[x]=val[x]=tag1[x]=tag2[x]=sz[x]=0;}
void rotate(int x){
int y=fa[x],z=fa[y];
int p=get(x);
ch[y][p]=ch[x][p^1];
fa[ch[x][p^1]]=y;
ch[x][p^1]=y;
fa[y]=x;
fa[x]=z;
if(z) ch[z][y==ch[z][1]]=x;
maintain(y);maintain(x);
}
void pd(int x){
int k1=tag1[x],k2=tag2[x];
for(int i=0;i<2;i++) if(ch[x][i]){
int j=ch[x][i];
ans1[j]=max(ans1[j],k1);
ans2[j]=max(ans2[j],k2);
tag1[j]=max(tag1[j],k1);
tag2[j]=max(tag2[j],k2);
}
tag1[x]=tag2[x]=0;
}
void splay(int x,int &p){
int top=0;
for(int f=x;f;f=fa[f]) q[++top]=f;
while(top) pd(q[top--]);
for(int f=fa[x];f=fa[x],f;rotate(x)){
if(fa[f]) rotate(get(x)==get(f)?f:x);
}
p=x;
}
int pre(int p) {
int cnr = ch[rt[p]][0];
while (ch[cnr][1]) cnr = ch[cnr][1];
splay(cnr,rt[p]);
return cnr;
}
void del(int p,int x){
splay(x,rt[p]);
int cnr=rt[p];
if(!ch[cnr][0]&&!ch[cnr][1]){
clear(cnr);
rt[p]=0;
return;
}
for(int i=0;i<2;i++) if(!ch[cnr][i]){
rt[p]=ch[cnr][i^1];
fa[rt[p]]=0;
clear(cnr);
return;
}
x=pre(p);
fa[ch[cnr][1]]=x;
ch[x][1]=ch[cnr][1];
clear(cnr);
maintain(rt[p]);
}
void ins(int &p,int x,int f){
if(!p){
p=x,fa[p]=f,val[p]=w[p],sz[p]=1;
return;
}
pd(p);
if(!ch[p][0]) ins(ch[p][0],x,p);
else ins(ch[p][1],x,p);
}
}S;
map<pii,int>vis;
int num;
int main(){
//ios::sync_with_stdio(false);
//freopen("in","r",stdin);
int n;
scanf("%d",&n);
rep(i,1,n){
int x,y;
scanf("%d%d%d",&w[i],&x,&y);
if(!vis.count(mp(x,y))){
vis[mp(x,y)]=++num;
}
int k=vis[mp(x,y)];
a[i]=k;
ans1[i]=max(ans1[i],val[rt[k]]);
ans2[i]=max(ans2[i],sz[rt[k]]);
S.ins(rt[k],i,0);
S.splay(i,rt[k]);
tag1[rt[k]]=max(tag1[rt[k]],w[i]);
tag2[rt[k]]=max(tag2[rt[k]],sz[rt[k]]-1);
}
int t;
scanf("%d",&t);
while(t--){
int i,x,y;
scanf("%d%d%d",&i,&x,&y);
if(!vis.count(mp(x,y))){
vis[mp(x,y)]=++num;
}
int k=vis[mp(x,y)],pre=a[i];
a[i]=k;
S.del(pre,i);
ans1[i]=max(ans1[i],val[rt[k]]);
ans2[i]=max(ans2[i],sz[rt[k]]);
S.ins(rt[k],i,0);
S.splay(i,rt[k]);
tag1[rt[k]]=max(tag1[rt[k]],w[i]);
tag2[rt[k]]=max(tag2[rt[k]],sz[rt[k]]-1);
}
rep(i,1,n){
S.splay(i,rt[a[i]]);
printf("%lld
",1ll*ans1[i]*ans2[i]);
}
return 0;
}