題目：http://codeforces.com/contest/1093/problem/G

只好看看題解：https://codeforces.com/blog/entry/63877

主要是把絕對值符號消掉，變成枚舉正負。因為答案不會變差，所以不用管符號應該是什么，直接對應地取 max 、 min 即可。

#include<cstdio> #include<cstring> #include<algorithm> #define ls Ls[cr] #define rs Rs[cr] using namespace std; const int N=2e5+5,M=N<<1,K=10,tK=35,INF=5e6+5; int n,k,lm,bin[K],Q,a[N][K],tot,Ls[M],Rs[M]; int Mx(int a,int b){return a>b?a:b;} int Mn(int a,int b){return a<b?a:b;} struct Node{int mx[tK],mn[tK];Node operator+ (const Node &b)const{Node c;for(int i=0;i<lm;i++){c.mx[i]=Mx(mx[i],b.mx[i]);c.mn[i]=Mn(mn[i],b.mn[i]);}return c;} }sm[M]; int rdn() {int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret; } void dfs(int cr,int lj,int s,int id,int bh) {if(cr>k){sm[bh].mn[s]=sm[bh].mx[s]=lj;return;}dfs(cr+1,lj+a[id][cr],s|bin[cr],id,bh);dfs(cr+1,lj-a[id][cr],s,id,bh); } void build(int l,int r,int cr) {if(l==r){dfs(1,0,0,l,cr);return;}int mid=l+r>>1;ls=++tot;build(l,mid,ls);rs=++tot;build(mid+1,r,rs);sm[cr]=sm[ls]+sm[rs]; } void updt(int l,int r,int cr,int p) {if(l==r){dfs(1,0,0,l,cr);return;}int mid=l+r>>1;if(p<=mid)updt(l,mid,ls,p);else updt(mid+1,r,rs,p);sm[cr]=sm[ls]+sm[rs]; } Node query(int l,int r,int cr,int L,int R) {if(l>=L&&r<=R)return sm[cr];int mid=l+r>>1;if(L>mid)return query(mid+1,r,rs,L,R);if(R<=mid)return query(l,mid,ls,L,R);return query(l,mid,ls,L,R)+query(mid+1,r,rs,L,R); } int main() {n=rdn();k=rdn();lm=(1<<k);bin[1]=1;for(int i=2;i<=k;i++)bin[i]=bin[i-1]<<1;for(int i=1;i<=n;i++)for(int j=1;j<=k;j++)a[i][j]=rdn();tot=1;build(1,n,1);Q=rdn();for(int i=1,op,id,l,r;i<=Q;i++){op=rdn();if(op==1){id=rdn();for(int j=1;j<=k;j++)a[id][j]=rdn();updt(1,n,1,id);}else{l=rdn();r=rdn();Node d=query(1,n,1,l,r);int ans=-INF;for(int i=0;i<lm;i++)ans=Mx(ans,d.mx[i]-d.mn[i]);printf("%d\n",ans);}}return 0; }

?

轉載于:https://www.cnblogs.com/Narh/p/10153472.html

總結

以上是生活随笔為你收集整理的CF 1093G Multidimensional Queries——线段树（消去绝对值符号）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。