本文主要是介绍Codeforces Contest 1093 problem G Multidimensional Queries —— 枚举+线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
You are given an array a of n points in k-dimensional space. Let the distance between two points ax and ay be ∑i=1k|ax,i−ay,i| (it is also known as Manhattan distance).
You have to process q queries of the following two types:
1 i b1 b2 … bk — set i-th element of a to the point (b1,b2,…,bk);
2 l r — find the maximum distance between two points ai and aj, where l≤i,j≤r.
Input
The first line contains two numbers n and k (1≤n≤2⋅105, 1≤k≤5) — the number of elements in a and the number of dimensions of the space, respectively.
Then n lines follow, each containing k integers ai,1, ai,2, …, ai,k (−106≤ai,j≤106) — the coordinates of i-th point.
The next line contains one integer q (1≤q≤2⋅105) — the number of queries.
Then q lines follow, each denoting a query. There are two types of queries:
1 i b1 b2 … bk (1≤i≤n, −106≤bj≤106) — set i-th element of a to the point (b1,b2,…,bk);
2 l r (1≤l≤r≤n) — find the maximum distance between two points ai and aj, where l≤i,j≤r.
There is at least one query of the second type.
Output
Print the answer for each query of the second type.
Example
inputCopy
5 2
1 2
2 3
3 4
4 5
5 6
7
2 1 5
2 1 3
2 3 5
1 5 -1 -2
2 1 5
1 4 -1 -2
2 1 5
outputCopy
8
4
4
12
10
题意：
给你n个k维的点，两个点之间的距离是曼哈顿距离，给你m个询问
2 l r 表示询问l到r之间距离最长的两个点的距离是多少
1x p1-pk 将x位置的点换成这个
题解：
对于一个点来说，它到另一个点的距离有两种情况：x1-x2,-(x1-x2)，然后k只有5，所以总共只有32种情况，其中最大的那个就是这两个k维点的距离，那么我们只需要开32个线段树，每一个线段树记录不同符号的情况，维护一个最大值和最小值，那么最大距离就是最大值减最小值。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int inf=1e9+7;
int n,k;
int maxn[N*4][32],minn[N*4][32],x[10];
void pushup(int b,int root)
{maxn[root][b]=max(maxn[root<<1][b],maxn[root<<1|1][b]);minn[root][b]=min(minn[root<<1][b],minn[root<<1|1][b]);
}
void update(int b,int l,int r,int root,int pos,int val)
{if(l==r){maxn[root][b]=minn[root][b]=val;return ;}int mid=l+r>>1;if(mid>=pos)update(b,l,mid,root<<1,pos,val);elseupdate(b,mid+1,r,root<<1|1,pos,val);pushup(b,root);
}
int qmax(int b,int l,int r,int root,int ql,int qr)
{if(l>=ql&&r<=qr)return maxn[root][b];int mid=l+r>>1;int ans=-inf;if(mid>=ql)ans=max(ans,qmax(b,l,mid,root<<1,ql,qr));if(mid<qr)ans=max(ans,qmax(b,mid+1,r,root<<1|1,ql,qr));return ans;
}
int qmin(int b,int l,int r,int root,int ql,int qr)
{if(l>=ql&&r<=qr)return minn[root][b];int mid=l+r>>1;int ans=inf;if(mid>=ql)ans=min(ans,qmin(b,l,mid,root<<1,ql,qr));if(mid<qr)ans=min(ans,qmin(b,mid+1,r,root<<1|1,ql,qr));return ans;
}
int main()
{scanf("%d%d",&n,&k);int bitk=(1<<k)-1;for(int i=0;i<=n*4;i++)for(int j=0;j<=bitk;j++)maxn[i][j]=-inf,minn[i][j]=inf;for(int i=1;i<=n;i++){for(int j=0;j<k;j++)scanf("%d",&x[j]);for(int j=0;j<=bitk;j++){int sum=0;for(int l=0;l<k;l++){if((j&(1<<l)))sum+=x[l];elsesum-=x[l];}update(j,1,n,1,i,sum);}}int m;scanf("%d",&m);while(m--){int op;scanf("%d",&op);if(op==2){int l,r;scanf("%d%d",&l,&r);int ans=-inf;for(int i=0;i<=bitk;i++)ans=max(ans,abs(qmax(i,1,n,1,l,r)-qmin(i,1,n,1,l,r)));printf("%d\n",ans);}else{int pos;scanf("%d",&pos);for(int i=0;i<k;i++)scanf("%d",&x[i]);for(int j=0;j<=bitk;j++){int sum=0;for(int l=0;l<k;l++){if((j&(1<<l)))sum+=x[l];elsesum-=x[l];}update(j,1,n,1,pos,sum);}}}return 0;
}这篇关于Codeforces Contest 1093 problem G Multidimensional Queries —— 枚举+线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
