题目链接:
题意：两种操作：（1）增加一个点到序列中；（2）删除序列中的某个点。在每次操作之后，输出序列中曼哈顿距离最远的两个点之间的距离。点最大为5维。
思路：我们先看二维空间的点，设两个点为(x1,y1),(x2,y2)，那么曼哈顿距离为|x1-x2|+|y1-y2|，现在我们去掉绝对值，那么有四种情况：
(x1-x2)+(y1-y2) (x2-x1)+(y1-y2) (x1-x2)+(y2-y1) (x2-x1)+(y2-y1)
由于这四个式子中绝对值均小于等于|x1-x2|+|y1-y2|，而最大的等于|x1-x2|+|y1-y2|，因此我们只要求这四个式子的绝对值的最大值即可。这四个式子进一步变形得到：(x1+y1)-(x2+y2),(-x1+y1)-(-x2+y2),(x1-y1)-(x2-y2),(-x1-y1)-(-x2-y2)。也就是我们我们可以保存四种情况的下每个点的最大值最小值，每种情况的最大最小值之差就是这种情况下的答案，四种情况下的最大值就是答案。
对于这道题，最大5维，也就是最多2^5种情况，用2^5*2（最大值最小值）个堆保存即可。
struct node{ int p[N],q[N],a[N],size; void init() { size=0; } void pushUp(int t) { while(1) { if(t/2>=1&&a[t/2]<a[t]) { swap(a[t],a[t/2]); swap(q[t],q[t/2]); p[q[t]]=t; p[q[t/2]]=t/2; t=t/2; } else break; } } void pushDown(int t) { int x; while(1) { if(t*2<=size&&a[t*2]>a[t]) x=t*2; else x=t; if(t*2+1<=size&&a[t*2+1]>a[x]) x=t*2+1; if(x==t) break; swap(a[t],a[x]); swap(q[t],q[x]); p[q[t]]=t; p[q[x]]=x; t=x; } } void insert(int k,int id) { a[++size]=k; q[size]=id; p[id]=size; pushUp(size); } void del(int id) { if(size==1) { size=0; return; } int x=p[id]; a[x]=a[size]; q[x]=q[size--]; p[q[x]]=x; pushUp(x); pushDown(x); } int top() { if(size==0) return 0; return a[1]; }};node a[32][2];int n,m;void insert(int p[],int id){ int sum,i,j; FOR0(i,(1<<m)) { sum=0; FOR0(j,m) { if(i&(1<<j)) sum+=p[j]; else sum-=p[j]; } a[i][0].insert(sum,id); a[i][1].insert(-sum,id); }}void del(int id){ int i; FOR0(i,(1<<m)) { a[i][0].del(id); a[i][1].del(id); }}int query(){ int ans=0,i; FOR0(i,(1<<m)) upMax(ans,a[i][0].top()+a[i][1].top()); return ans;}int main(){ Rush(n) { RD(m); int i,j; FOR0(i,(1<<m)) a[i][0].init(),a[i][1].init(); int op,p[5]; FOR1(i,n) { RD(op); if(op==0) { FOR0(j,m) RD(p[j]); insert(p,i); } else { RD(p[0]); del(p[0]); } PR(query()); } }}