题目大意：自己看
首先我们可以写个哈希表来存坐标
当我们改变一个点的坐标时，，被加入的集合中的点和这个点之间会产生相互的影响。。。
我们首先考虑集合中的点对这个点的影响
显然ans1是集合中的最大值 ans2是集合的大小
然后就是这个点对集合中的点的影响
首先连小学僧都知道如果一个一个改那么复杂度肯定会炸。。。
那么打个标记不就好了！
当一个点删除的时候把标记下传到节点上 一并带走即可
那么我们需要这样一种数据结构，它需要支持：
插入，删除，查询最大值，维护大小，打标记
随便搞搞咯~反正我写了个Treap，然后发现我终于连Treap都不会写了QAQ
于是VFK的三道互测题就这么都A掉了。。。
#include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 30300using namespace std;int n,m;int a[M],X[M],Y[M];int ans1[M],ans2[M];struct Treap{static vector<Treap*> bin;Treap *ls,*rs;int val,key,size;int mark1,mark2;void* operator new(size_t,int x){Treap *re;if(!bin.empty()){re=bin.back();bin.pop_back();}else{static Treap mempool[M],*C=mempool;re=C++;}re->ls=re->rs=0x0;re->val=x;re->key=rand();re->size=1;re->mark1=re->mark2=0;return re;}void operator delete(void *p){bin.push_back((Treap*)p);}void Get_Mark(int _,int __){ans1[val]=max(ans1[val],_);ans2[val]=max(ans2[val],__);mark1=max(mark1,_);mark2=max(mark2,__);}void Push_Down(){if(!mark1&&!mark2)return ;if(ls) ls->Get_Mark(mark1,mark2);if(rs) rs->Get_Mark(mark1,mark2);mark1=mark2=0;}void Push_Up(){size=1;if(ls) size+=ls->size;if(rs) size+=rs->size;}friend void Zig(Treap *&x){Treap *y=x->ls;x->Push_Down();y->Push_Down();x->ls=y->rs;y->rs=x;x=y;x->rs->Push_Up();x->Push_Up();}friend void Zag(Treap *&x){Treap *y=x->rs;x->Push_Down();y->Push_Down();x->rs=y->ls;y->ls=x;x=y;x->ls->Push_Up();x->Push_Up();}friend void Insert(Treap *&x,int y){if(!x){x=new (y)Treap;return ;}x->Push_Down();if( a[y]<a[x->val] || a[y]==a[x->val]&&y<x->val ){Insert(x->ls,y);if(x->ls->key>x->key)Zig(x);}else{Insert(x->rs,y);if(x->rs->key>x->key)Zag(x);}x->Push_Up();}friend void Delete(Treap *&x,int y){x->Push_Down();if( a[y]<a[x->val] || a[y]==a[x->val]&&y<x->val )Delete(x->ls,y);else if( a[y]>a[x->val] || a[y]==a[x->val]&&y>x->val )Delete(x->rs,y);else if(!x->ls) delete x,x=x->rs;else if(!x->rs) delete x,x=x->ls;else{Zag(x);Delete(x->ls,y);if(x->ls&&x->ls->key>x->key)Zig(x);}if(x) x->Push_Up();}friend int Get_Max(Treap *x){if(!x->rs) return a[x->val];return Get_Max(x->rs);}};vector<Treap*> Treap :: bin;namespace Hash_Set{struct List{int x,y;Treap *pointer;List *next;List(int _,int __,List *___):x(_),y(__),pointer(0x0),next(___) {}}*head[349][353];Treap*& Hash(int x,int y){int pos1=((x%349)+349)%349,pos2=((y%353)+353)%353;List *temp;for(temp=head[pos1][pos2];temp;temp=temp->next)if(temp->x==x&&temp->y==y)return temp->pointer;return (head[pos1][pos2]=new List(x,y,head[pos1][pos2]))->pointer;}}int main(){using namespace Hash_Set;int i,p,x,y;cin>>n;for(i=1;i<=n;i++){scanf("%d%d%d",&a[i],&X[i],&Y[i]);Treap *&root=Hash(X[i],Y[i]);if(root) {ans1[i]=max(ans1[i],Get_Max(root));root->Get_Mark(a[i],0);}Insert(root,i);root->Get_Mark(0,root->size-1);}cin>>m;for(i=1;i<=m;i++){scanf("%d%d%d",&p,&x,&y);Delete(Hash(X[p],Y[p]),p);X[p]=x;Y[p]=y;Treap *&root=Hash(X[p],Y[p]);if(root) {ans1[p]=max(ans1[p],Get_Max(root));root->Get_Mark(a[p],0);}Insert(root,p);root->Get_Mark(0,root->size-1);}for(i=1;i<=n;i++)Delete(Hash(X[i],Y[i]),i);for(i=1;i<=n;i++)#ifdef ONLINE_JUDGEprintf("%lld\n",(long long)ans1[i]*ans2[i]);#elseprintf("%I64d\n",(long long)ans1[i]*ans2[i]);#endifreturn 0;}
有的旅行是为了体验生活，感悟人生。
