离散化坐标，每个坐标开一棵以鸟的编号为关键字的平衡树。每次插入时打2个标记，同时更新自身。这个方法比较显然，而且好写。正解好像用很迷的方法乱搞了一波，然后用线段树不打标记就做出来了，并不会。
treap旋转没传引用，调了好久。
#include<bits/stdc++.h>
#define N 30005
#define M 330005
#define x first
#define y second
#define IF else if
using namespace std;
int n,m,i,v[M];
typedef int ds[N];
ds f,l,r,z;
typedef pair<int,int>vec;
vec a[M],s[M];
struct node{
int v,a,i,j,s,q;
node*r,*l;
}*t[M],e[M];
node*back=e+1;
node*null=e;
node*create(int v){
return&(*back++=(node){v,z[v],0,0,1,rand(),e,e});
}
void update(node*t){
t->s=t->l->s+t->r->s+1;
t->a=max(max(t->l->a,t->r->a),z[t->v]);
}
void lturn(node*&t){
node*s=t->r;
t->r=s->l;
update(s->l=t);
update(t=s);
}
void rturn(node*&t){
node*s=t->l;
t->l=s->r;
update(s->r=t);
update(t=s);
}
void eq2(int&a,int b){
a=a<b?b:a;
}
void devolve(node*s){
eq2(s->l->i,s->i);
eq2(s->l->j,s->j);
eq2(s->r->i,s->i);
eq2(s->r->j,s->j);
eq2(l[s->v],s->i);
eq2(r[s->v],s->j);
s->i=s->j=0;
}
void insert(int v,node*&s){
if(s==null)
s=create(v);
devolve(s);
if(v<s->v){
insert(v,s->l);
if(s->l->q>s->q)
rturn(s);
}
IF(s->v<v){
insert(v,s->r);
if(s->r->q>s->q)
lturn(s);
}
update(s);
}
void erase(int v,node*&s){
devolve(s);
if(v<s->v)
erase(v,s->l);
IF(s->v<v)erase(v,s->r);
IF(s->l==null){
s=s->r;
return;
}
IF(s->r==null){
s=s->l;
return;
}
IF(s->l->q>s->r->q){
devolve(s->l);
rturn(s);
erase(v,s->r);
}
else{
devolve(s->r);
lturn(s);
erase(v,s->l);
}
update(s);
}
void come(int v,node*&s){
eq2(s->i,z[v]);
eq2(s->j,s->s);
eq2(l[v],s->a);
eq2(r[v],s->s);
insert(v,s);
}
void dfs(node*t){
if(t!=null){
devolve(t);
dfs(t->l);
dfs(t->r);
}
}
int main(){
srand(20000327);
scanf("%d",&n);
for(i=1;i<=n;++i){
scanf("%d%d%d",z+i,&a[i].x,&a[i].y);
s[i]=a[i];
}
scanf("%d",&m);
for(i=n+1;i<=n+m;++i){
scanf("%d%d%d",v+i,&a[i].x,&a[i].y);
s[i]=a[i];
}
sort(s+1,s+n+m+1);
for(i=1;i<=n+m;++i)
t[i]=null;
for(i=1;i<=n;++i)
come(i,t[f[i]=lower_bound(s+1,s+n+m+1,a[i])-s]);
for(i=n+1;i<=n+m;++i){
erase(v[i],t[f[v[i]]]);
come(v[i],t[f[v[i]]=lower_bound(s+1,s+n+m+1,a[i])-s]);
}
for(i=1;i<=n;++i){
dfs(t[f[i]]);
t[f[i]]=null;
printf("%lld\n",1ll*l[i]*r[i]);
}
}