ouuan 的博客

ouuan 的博客

题解 CF1093G 【Multidimensional Queries】

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

为了便于扩展到高维,本文中点的坐标统一用 $(x_1,x_2,\cdots,x_k)$ 表示,即使二维也一样。

$\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}$

用 $s[x][0]$ 表示 $-x_1-x_2$, $s[x][1]$ 表示 $-x_1+x_2$, $s[x][2]$ 表示 $x_1-x_2$, $s[x][3]$ 表示 $x_1+x_2$,那么 $\text{两个二维点之间的曼哈顿距离}=\max\{s[x][j]-s[y][j]\}(j\in[0,3])$ 。

转换成这样之后,二维平面上一些点之间的最大曼哈顿距离就可以求了: $\max\{\max\{s[a_i][j]\}-\min\{s[a_i][j]\}\}$

上面这个公式的意思是,对于每个 $j$ 把 $s[a_{1..n}][j]$ 求出来,并取最大值和最小值相减,把不同的 $j$ 的“最大值和最小值相减”取 $\max$ 。

至于高维,二进制枚举 $x_i$ 的正负,也就是说 $s[x][j]=\sum_{i=1}^kx_i\times(j\text{ and } 2^{i-1}?1:-1)$,然后按一样的做法就可以了。

如果到这里为止你看懂了,你就可以 AC P1648 看守 了。

至于本题,需要支持区间查询、单点修改,套上任何一种支持修改的 RMQ(比如线段树)即可。

但是套有不同的套法,直接放在一棵线段树里,每个节点存 $2^k$ 个最大/最小值,修改/询问时就只用在线段树上查找一次;如果拆成 $32$ 棵线段树,常数就会非常大。

一棵线段树的 $1.1s$ 解法:

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

using namespace std;

const int INF=0x3f3f3f3f;

inline int read()
{
    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;

    n=read();
    k=read();

    for (i=1;i<=n;++i)
    {
        for (j=0;j<k;++j)
        {
            a[i][j]=read();
        }
    }

    build(1,1,n+1);

    q=read();

    while (q--)
    {
        if (read()==1)
        {
            pos=read();
            for (i=0;i<k;++i)
            {
                a[pos][i]=read();
            }
            modify(1,pos);
        }
        else
        {
            ans=0;
            l=read();
            r=read();
            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;
}

拆成 $32$ 棵线段树的 $4.2s$ 解法:

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

using namespace std;

const int INF=0x3f3f3f3f;

inline int read()
{
    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;

    n=read();
    k=read();

    for (i=1;i<=n;++i)
    {
        for (j=0;j<k;++j)
        {
            a[i][j]=read();
        }
        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);
    }

    q=read();

    while (q--)
    {
        if (read()==1)
        {
            i=read();
            for (j=0;j<k;++j)
            {
                a[i][j]=read();
            }
            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
        {
            l=read();
            r=read()+1;
            ans=0;
            for (i=0;i<(1<<k);++i)
            {
                ans=max(ans,s[i].qmax(1,l,r)-s[i].qmin(1,l,r));
            }
            write(ans);
            putchar('\n');
        }
    }

    return 0;
}