# ouuan 的博客

### 题解 CF1093G 【Multidimensional Queries】

posted on 2018-12-17 12:00:31 | under 题解 |

\begin{aligned}&\text{两个二维点之间的曼哈顿距离}\\=&|x_1-y_1|+|x_2-y_2|\\=&\max(x_1-y_1,y_1-x_1)+\max(x_2-y_2,y_2-x_2)\\=&\max(x_1-y_1+x_2-y_2,x_1-y_1+y_2-x_2,y_1-x_1+x_2-y_2,y_1-x_1+y_2-x_2)\end{aligned}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int INF=0x3f3f3f3f;

{
char c;int out=0,f=1;
for (c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());if (c=='-'){f=-1;c=getchar();}
for (;c>='0'&&c<='9';c=getchar()){out=(out<<3)+(out<<1)+c-'0';}return out*f;
}
void write(int x)
{
if (x<0){putchar('-');write(-x);return;}
if (x>9){write(x/10);}putchar(x%10+'0');
}

#define now t[cur]
#define ls t[cur<<1]
#define rs t[cur<<1|1]

const int N=200010;

int n,k,q,a[N][5];

struct Val
{
int maxx[32],minn[32];
Val()
{
int i;
for (i=0;i<(1<<k);++i)
{
maxx[i]=-INF;
minn[i]=INF;
}
}
};

struct Node
{
int left,right;
Val val;
} t[N<<2];

void build(int cur,int l,int r);
void mnode(int cur);
void modify(int cur,int p);
Val query(int cur,int l,int r);
Val merge(Val x,Val y);

int main()
{
int i,j,pos,l,r,ans;
Val v;

for (i=1;i<=n;++i)
{
for (j=0;j<k;++j)
{
}
}

build(1,1,n+1);

while (q--)
{
{
for (i=0;i<k;++i)
{
}
modify(1,pos);
}
else
{
ans=0;
v=query(1,l,r+1);
for (i=0;i<(1<<k);++i)
{
ans=max(ans,v.maxx[i]-v.minn[i]);
}
write(ans);
putchar('\n');
}
}

return 0;
}

void mnode(int cur)
{
int i,j;
for (i=0;i<(1<<k);++i)
{
now.val.maxx[i]=0;
for (j=0;j<k;++j)
{
now.val.maxx[i]+=((i&(1<<j))?1:-1)*a[now.left][j];
}
now.val.minn[i]=now.val.maxx[i];
}
}

void build(int cur,int l,int r)
{
now.left=l;
now.right=r;
if (l==r-1)
{
mnode(cur);
}
else
{
build(cur<<1,l,(l+r)>>1);
build(cur<<1|1,(l+r)>>1,r);
now.val=merge(ls.val,rs.val);
}
}

void modify(int cur,int p)
{
if (now.left==p&&now.right==p+1)
{
mnode(cur);
}
else
{
if (p<ls.right)
{
modify(cur<<1,p);
}
else
{
modify(cur<<1|1,p);
}
now.val=merge(ls.val,rs.val);
}
}

Val query(int cur,int l,int r)
{
if (l>=now.right||r<=now.left)
{
return Val();
}
if (l<=now.left&&r>=now.right)
{
return now.val;
}
else
{
return merge(query(cur<<1,l,r),query(cur<<1|1,l,r));
}
}

Val merge(Val x,Val y)
{
Val out;
int i;
for (i=0;i<(1<<k);++i)
{
out.minn[i]=min(x.minn[i],y.minn[i]);
out.maxx[i]=max(x.maxx[i],y.maxx[i]);
}
return out;
}

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

{
char c;int out=0,f=1;
for (c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());if (c=='-'){f=-1;c=getchar();}
for (;c>='0'&&c<='9';c=getchar()){out=(out<<3)+(out<<1)+c-'0';}return out*f;
}
void write(int x)
{
if (x<0){putchar('-');write(-x);return;}
if (x>9){write(x/10);}putchar(x%10+'0');
}

#define now t[cur]
#define ls t[cur<<1]
#define rs t[cur<<1|1]

const int N=200010;

struct Node
{
int left,right,maxx,minn;
};

int n,k,q,a[N][5];

struct segTree
{
int b[N];
Node t[N<<2];
void build(int cur,int l,int r)
{
now.left=l;
now.right=r;
if (l==r-1)
{
now.maxx=now.minn=b[l];
}
else
{
build(cur<<1,l,(l+r)>>1);
build(cur<<1|1,(l+r)>>1,r);
pushup(cur);
}
}
void modify(int cur,int p,int x)
{
if (p==now.left&&p==now.right-1)
{
now.minn=now.maxx=x;
}
else
{
if (p<ls.right)
{
modify(cur<<1,p,x);
}
else
{
modify(cur<<1|1,p,x);
}
pushup(cur);
}
}
int qmax(int cur,int l,int r)
{
if (l>=now.right||r<=now.left)
{
return -INF;
}
if (l<=now.left&&r>=now.right)
{
return now.maxx;
}
else
{
return max(qmax(cur<<1,l,r),qmax(cur<<1|1,l,r));
}
}
int qmin(int cur,int l,int r)
{
if (l>=now.right||r<=now.left)
{
return INF;
}
if (l<=now.left&&r>=now.right)
{
return now.minn;
}
else
{
return min(qmin(cur<<1,l,r),qmin(cur<<1|1,l,r));
}
}
void pushup(int cur)
{
now.minn=min(ls.minn,rs.minn);
now.maxx=max(ls.maxx,rs.maxx);
}
} s[32];

int main()
{
int i,j,l,r,ans;

for (i=1;i<=n;++i)
{
for (j=0;j<k;++j)
{
}
for (j=0;j<(1<<k);++j)
{
for (l=0;l<k;++l)
{
if (j&(1<<l))
{
s[j].b[i]+=a[i][l];
}
else
{
s[j].b[i]-=a[i][l];
}
}
}
}

for (i=0;i<(1<<k);++i)
{
s[i].build(1,1,n+1);
}

while (q--)
{
{
for (j=0;j<k;++j)
{
}
for (j=0;j<(1<<k);++j)
{
s[j].b[i]=0;
for (l=0;l<k;++l)
{
if (j&(1<<l))
{
s[j].b[i]+=a[i][l];
}
else
{
s[j].b[i]-=a[i][l];
}
}
s[j].modify(1,i,s[j].b[i]);
}
}
else
{
}