题目
题目链接
好长。。。。。 但是我觉得这个题目的名字特别好。
分析
尽管感觉是个很弱的题目，好歹是最为数据结构以及 treap的练手题目嘛 首先看起来我们就是需要数据结构去维护个什么东西 坐标比较散，所以我们可以先离散，排个序就可以了,但是要去重！？其实不去也是对的，因为每次都会选择同一个位置 然后就是修改操作 要支持查找最大值、统计元素个数、打上标记（而且是两个），还要分离合并 那么treap真是太好不过了。 时间复杂度O(t(logn+logt)) 呵呵，排序+查找的时间复杂度 还有就是最后的答案可能是LL
话说这里维护的对树的形态有关的那个权值我用的是鸟标号，但是正好也就是数组下标
然后
记得之前我说这个题目很弱，对不起我错啦。。。。 作为一个从来没有写个数据结构的家伙。。。。写了一上午才写出来呀。。。。 无限RE。。。。少主家题库是可以看数据的嘛。。。然后刷BZOJ真的好累啊。。。但是要练习，必须刷的。。 最后我是通过自己生成数据来找出了错误，也为查错找了一个方法嘛。。。 还有就是找到错误之后，不要改对了就算了，要看错误的根本原因，而不是掩耳盗铃地改个表面的东西额。
不过为什么其他人的代码这么短啊啊啊啊！！！
关于treap
真的是个很灵活的东西。 我感觉这次用的非常灵活啊。。 在按值分裂的时候，注意等于的情况是挂在哪个集合里面，看看代码就知道， v
代码
using namespace std;
const
int maxn=
3e4+
100,maxt=
3e5+
1000;
struct XY{
int x,
y;
friend bool operator<(XY a,XY b)
{
return a.
x!=b.
x?a.
x<b.
x:a.
y<b.
y;
}
friend bool operator==(XY a,XY b)
{
return a.
x==b.
x&&a.
y==b.
y;
}
}p[maxn+maxt];
int cnt;
struct data{
int w,
x,
y;
void ins()
{
scanf(
"%d%d%d",&w,&
x,&
y);
}
}a[maxn],
q[maxt];
struct Treap
{
int rt[maxt+maxn],ch[maxn][
2],fix[maxn],w[maxn],sz[maxn],mx[maxn],mx_sz[maxn],mx_w[maxn],add_w[maxn],add_sz[maxn];
void Initial()
{
memset(w,
0,sizeof(w));
memset(rt,
0,sizeof(rt));
memset(ch,
0,sizeof(ch));
memset(sz,
0,sizeof(sz));
memset(mx,
0,sizeof(mx));
memset(fix,
0,sizeof(fix));
memset(mx_w,
0,sizeof(mx_w));
memset(mx_sz,
0,sizeof(mx_sz));
memset(add_w,
0,sizeof(add_w));
memset(add_sz,
0,sizeof(add_sz));
}
int NewNode(
int np,
int v)
{
w[np]=mx[np]=v,sz[np]=
1;
fix[np]=
rand();
return np;
}
void pushup(
int now)
{
sz[now]=
1;
if(
lc)sz[now]+=sz[
lc];
if(rc)sz[now]+=sz[rc];
mx[now]=w[now];
if(
lc)mx[now]=max(mx[now],mx[
lc]);
if(rc)mx[now]=max(mx[now],mx[rc]);
}
void pushdown(
int now)
{
mx_sz[
lc]=max(mx_sz[
lc],add_sz[now]);
mx_sz[rc]=max(mx_sz[rc],add_sz[now]);
add_sz[
lc]=max(add_sz[
lc],add_sz[now]);
add_sz[rc]=max(add_sz[rc],add_sz[now]);
add_sz[now]=
0;
mx_w[
lc]=max(mx_w[
lc],add_w[now]);
mx_w[rc]=max(mx_w[rc],add_w[now]);
add_w[
lc]=max(add_w[
lc],add_w[now]);
add_w[rc]=max(add_w[rc],add_w[now]);
add_w[now]=
0;
}
int Merge(
int A,
int B)
{
pushdown(A);pushdown(B);
if(A
*B==
0)
return A+B;
if(fix[A]<fix[B])
{
ch[A][
1]=Merge(ch[A][
1],B);
pushup(A);
return A;
}
else
{
ch[B][
0]=Merge(A,ch[B][
0]);
pushup(B);
return B;
}
}
void Split(
int now,
int v,
int &A,
int &B)
{
pushdown(now);
if(!now)
{
A=B=
0;
return;
}
if(v<now)
{
B=now;
Split(
lc,v,A,
lc);
}
else
{
A=now;
Split(rc,v,rc,B);
}
pushup(now);
}
int Find(
int now,
int v)
{
while(now)
{
pushdown(now);
if(now==v)
break;
now=ch[now][v>now];
}
return now;
}
void outs()
{
for(
int i=
1;i<=
2;i++)
{
cout<<i<<
" "<<sz[i]<<endl;
}
cout<<endl;
}
}tp;
int n,
m,
sub[maxn];
void Init()
{
tp.Initial();
scanf(
"%d",&n);
for(
int i=
1;i<=n;i++)a[i].ins(),p[i].
x=a[i].
x,p[i].
y=a[i].
y;
scanf(
"%d",&
m);
for(
int i=
1;i<=
m;i++)
q[i].ins(),p[i+n].
x=
q[i].
x,p[i+n].
y=
q[i].
y;
cnt=n+
m;
sort(p+
1,p+cnt+
1);
cnt=unique(p+
1,p+cnt+
1)-p-
1;
}
void add1(
int i,
int t)
{
int A,B,C;
C=tp.NewNode(i,a[i].w);
if(tp.rt[t])
{
tp.mx_w[tp.rt[t]]=max(tp.mx_w[tp.rt[t]] , a[i].w);
tp.add_w[tp.rt[t]]=max(tp.add_w[tp.rt[t]], a[i].w);
tp.mx_sz[tp.rt[t]]=max(tp.mx_sz[tp.rt[t]] , tp.sz[tp.rt[t]]);
tp.add_sz[tp.rt[t]]=max(tp.add_sz[tp.rt[t]], tp.sz[tp.rt[t]]);
tp.mx_w[i]=max(tp.mx_w[i] , tp.mx[tp.rt[t]]);
tp.mx_sz[i]=max(tp.mx_sz[i] , tp.sz[tp.rt[t]]);
}
tp.Split(tp.rt[t],i,A,B);
tp.rt[t]=tp.Merge(tp.Merge(A,C),B);
sub[i]=t;
}
void add2(
int i,
int t)
{
// if(
sub[i]==t)return;
int A,B,C;
tp.Split(tp.rt[
sub[i]],i-1,A,B);
tp.Split(B,i,C,B);
tp.rt[
sub[i]]=tp.Merge(A,B);
if(tp.rt[t])
{
tp.mx_w[tp.rt[t]]=max(tp.mx_w[tp.rt[t]] , a[i].w);
tp.add_w[tp.rt[t]]=max(tp.add_w[tp.rt[t]], a[i].w);
tp.mx_sz[tp.rt[t]]=max(tp.mx_sz[tp.rt[t]] , tp.sz[tp.rt[t]]);
tp.add_sz[tp.rt[t]]=max(tp.add_sz[tp.rt[t]], tp.sz[tp.rt[t]]);
tp.mx_w[i]=max(tp.mx_w[i] , tp.mx[tp.rt[t]]);
tp.mx_sz[i]=max(tp.mx_sz[i] , tp.sz[tp.rt[t]]);
}
tp.Split(tp.rt[t],i,A,B);
tp.rt[t]=tp.Merge(tp.Merge(A,i),B);
sub[i]=t;
}
void solve()
{
int t;
for(
int i=
1;i<=n;i++)
{
t=lower_bound(p+
1,p+cnt+
1,(XY){a[i].
x,a[i].
y})-p;
add1(i,t);
}
//tp.outs();
for(
int i=
1;i<=
m;i++)
{
t=lower_bound(p+
1,p+cnt+
1,(XY){
q[i].
x,
q[i].
y})-p;
add2(
q[i].w,t);
//tp.outs();
}
}
void outs()
{
for(
int i=
1;i<=n;i++)
{
tp.Find(tp.rt[
sub[i]],i);
cout<<
1ll
*tp.mx_w[i]
*tp.mx_sz[i]<<
'\n';
}
}
int main()
{
//freopen(
"in.txt",
"r",stdin);
//freopen(
"out.txt",
"w",stdout);
Init();
solve();
outs();
return 0;
}
