将所有点按横坐标排序，那么最长上升子序列和最长下降子序列里必有一个长度不小于$\sqrt{n}$。
因为如果最长上升子序列很短，那么根据Dilworth定理，它的反链长度与它成反比。
因此可以将$n$个点划分为不超过$\sqrt{n}$条链或者反链，每一个部分里都相当于只有一维坐标。
对于每一个部分，建立线段树，支持合并、分裂以及打标记即可。
时间复杂度$O(q\sqrt{n}\log n)$。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=50010,M=100010,E=5000000;
const ll inf=1LL<<60;
int n,m,cnt,cset,mx,i,j,b[N],d[N],q[M][4],rem,dir,del[N],f[N],bit[N];ll ans[M][3];
struct P{int x,y,w,p;}a[N],c[N];
inline bool cmp(const P&a,const P&b){return a.x<b.x;}
inline int lower(int x){
int l=1,r=n,mid,t;
while(l<=r)if(b[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;
return t;
}
inline void ins(int x,int p){for(;x<=n;x+=x&-x)if(bit[x]<p)bit[x]=p;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)if(t<bit[x])t=bit[x];return t;}
int T[M*2+N],tot,l[E],r[E],v[E];ll mi[E],ma[E],sum[E],tag[E];
inline void tag1(int x,ll p){if(x)mi[x]+=p,ma[x]+=p,sum[x]+=p*v[x],tag[x]+=p;}
inline void pb(int x){if(tag[x])tag1(l[x],tag[x]),tag1(r[x],tag[x]),tag[x]=0;}
inline void up(int x){
v[x]=v[l[x]]+v[r[x]];
mi[x]=min(mi[l[x]],mi[r[x]]);
ma[x]=max(ma[l[x]],ma[r[x]]);
sum[x]=sum[l[x]]+sum[r[x]];
}
int build(int a,int b,int c,int p){
int x=++tot;
v[x]=1,mi[x]=ma[x]=sum[x]=p;
if(a==b)return x;
int mid=(a+b)>>1;
if(c<=mid)l[x]=build(a,mid,c,p);else r[x]=build(mid+1,b,c,p);
return x;
}
int merge(int x,int y,int a,int b){
if(!x||!y)return x+y;
if(a==b){
v[x]+=v[y];
sum[x]+=sum[y];
mi[x]=min(mi[x],mi[y]);
ma[x]=max(ma[x],ma[y]);
return x;
}
int mid=(a+b)>>1;
pb(x),pb(y);
l[x]=merge(l[x],l[y],a,mid);
r[x]=merge(r[x],r[y],mid+1,b);
up(x);
return x;
}
int split(int x,int a,int b,int c,int d){
if(!x)return 0;
if(c<=a&&b<=d)return x;
pb(x);
int y=++tot,mid=(a+b)>>1;
if(c<=mid)l[y]=split(l[x],a,mid,c,d);
if(d>mid)r[y]=split(r[x],mid+1,b,c,d);
up(x),up(y);
return y;
}
inline int findx(int x){
int l=1,r=cnt,mid,t=0;
while(l<=r)if(c[mid=(l+r)>>1].x<=x)l=(t=mid)+1;else r=mid-1;
return t;
}
inline int findy0(int x){
int l=1,r=cnt,mid,t=0;
while(l<=r)if(c[mid=(l+r)>>1].y<=x)l=(t=mid)+1;else r=mid-1;
return t;
}
inline int findy1(int x){
int l=1,r=cnt,mid,t=cnt+1;
while(l<=r)if(c[mid=(l+r)>>1].y<=x)r=(t=mid)-1;else l=mid+1;
return t;
}
inline void solve(){
int i;
for(cset=n,i=1;i<=n;i++)T[i]=0;
for(i=1;i<=cnt;i++)T[c[i].p]=build(1,cnt,i,c[i].w);
for(i=0;i<m;i++){
int x=q[i][1],y=q[i][2],z=q[i][3];
if(!q[i][0]){
T[x]=merge(T[x],T[y],1,cnt);
T[y]=0;
}
if(q[i][0]==1){
cset+=2;
T[cset-1]=T[cset]=0;
if(!y){
int o=findx(z);
if(o)T[cset-1]=split(T[x],1,cnt,1,o);
if(o<cnt)T[cset]=split(T[x],1,cnt,o+1,cnt);
}else if(!dir){
int o=findy0(z);
if(o)T[cset-1]=split(T[x],1,cnt,1,o);
if(o<cnt)T[cset]=split(T[x],1,cnt,o+1,cnt);
}else{
int o=findy1(z);
if(o<=cnt)T[cset-1]=split(T[x],1,cnt,o,cnt);
if(o>1)T[cset]=split(T[x],1,cnt,1,o-1);
}
T[x]=0;
}
if(q[i][0]==2){
ans[i][0]=max(ans[i][0],ma[T[x]]);
ans[i][1]=min(ans[i][1],mi[T[x]]);
ans[i][2]+=sum[T[x]];
}
if(q[i][0]==3)tag1(T[x],y);
}
for(i=1;i<=tot;i++)l[i]=r[i]=v[i]=mi[i]=ma[i]=sum[i]=tag[i]=0;
tot=0;
}
int main(){
mi[0]=inf,ma[0]=-inf;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w),a[i].p=i;
scanf("%d",&m);
for(i=0;i<m;i++){
char op[9];
scanf("%s",op);
if(op[0]=='M')scanf("%d%d",&q[i][1],&q[i][2]);
if(op[0]=='S')q[i][0]=1,scanf("%d%d%d",&q[i][1],&q[i][2],&q[i][3]);
if(op[0]=='Q'){
q[i][0]=2,scanf("%d",&q[i][1]);
ans[i][0]=-inf,ans[i][1]=inf;
}
if(op[0]=='A')q[i][0]=3,scanf("%d%d",&q[i][1],&q[i][2]);
}
rem=n;
for(i=1;i<=n;i++)b[i]=a[i].y;
sort(b+1,b+n+1);
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++)d[i]=lower(a[i].y);
while(rem){
for(i=1;i<=n;i++)bit[i]=0;
for(i=1;i<=n;i++)if(!del[i])ins(d[i],f[i]=ask(d[i])+1);
mx=ask(n);
if(mx>=rem/mx){
rem-=mx;
dir=0;
for(i=n;i;i--)if(!del[i]&&f[i]==mx)break;
j=i;
c[cnt=mx]=a[j],del[j]=1;
for(i=j-1;i;i--)if(!del[i]&&f[i]+1==f[j]&&d[i]<d[j])c[--mx]=a[i],del[j=i]=1;
solve();
continue;
}
for(i=1;i<=n;i++)bit[i]=0;
for(i=1;i<=n;i++)if(!del[i])ins(n-d[i]+1,f[i]=ask(n-d[i]+1)+1);
mx=ask(n);
rem-=mx;
dir=1;
for(i=n;i;i--)if(!del[i]&&f[i]==mx)break;
j=i;
c[cnt=mx]=a[j],del[j]=1;
for(i=j-1;i;i--)if(!del[i]&&f[i]+1==f[j]&&d[i]>d[j])c[--mx]=a[i],del[j=i]=1;
solve();
}
for(i=0;i<m;i++)if(q[i][0]==2)printf("%lld %lld %lld\n",ans[i][0],ans[i][1],ans[i][2]);
return 0;
}