[数据结构与算法]【牛客多校 2021 第10场 E】More Fantastic Chess Problem （分析与数据结构）

【题目链接】

【题意】

? 定义 $k$ 维度国际象棋是一个在 $a_1\times a_2\times ?\times a_k$ 的棋盘上进行的游戏，其中规定棋盘的对角位置分别为 $(1,1,\dots ,1)$ 和 $(a_1,a_2,\dots ,a_k)$ 。

? 定义国际象棋中的棋子 $\text{King?(国王)?,?Queen?(王后)?,?Rook?(车)?,?Bishop?(象)?,?Knight?(马)?}$ 的走法如下：

• $\text{King:}$

  每次行动可以从 $k$ 个维度中任意选一些维度，让棋子在这些维度上所处的位置都 $+1$ ，同时任选另一些维度，让棋子在这些维度上所处的位置都 $?1$ 。其余维度上位置保持不变。行动后不能留在原位，也不能走出棋盘外。

• $\text{Queen:}$

  每次行动可以选一个正整数 $x$ ，接下来从 $k$ 个维度中任意选一些维度，让棋子在这些维度上所处的位置都 $+x$ ，同时任选另一些维度，让棋子在这些维度上所处的位置都 $?x$ 。其余维度上位置保持不变。行动后不能留在原位，也不能走出棋盘外。

• $\text{Rook:}$

  每次行动可以选一个正整数 $x$ ，接下来从 $k$ 个维度中选择某一个维度，让棋子在这个维度上的位置 $+x$ 或者 $?x$ 。行动后不能走出棋盘外。

• $\text{Bishop:}$

  每次行动可以选一个正整数 $x$ ，接下来从 $k$ 个维度中选择两个不同的维度，让棋子在这两个维度上的位置各自 $+x$ 或者 $?x$ （注意：不必同加同减）。行动后不能走出棋盘外。

• $\text{Knight:}$

  每次行动，从 $k$ 个维度中选择两个不同的维度，让棋子在其中一个维度上的位置 $+1$ 或者 $?1$ ，在另一个维度上的位置 $+2$ 或者 $?2$ 。行动后不能走出棋盘外。

? 现在棋盘上只有一颗棋子，给出这个棋子的类型和初始位置 $(b_1,b_2,\dots b_k)$ ，询问其一次行动后能到达的位置一共有多少个。接下来棋子还有 $q$ 次移动，每次移动会变化 $d$ 个维度，每个维度的变化会用 $(x,\delta )$ 的形式给出，表示这次移动将 $x$ 维度上的位置变化了 $\delta$ 。保证每次移动是棋子的合法走法。每次移动后你仍然需要输出棋子在当前位置上，一次行动后能到达的位置一共有多少个。答案对大质数取模。

【数据范围】

? $k,q\le 3\times 10^5,\sum d\le 3\times 10^5,a_i\le 10^6$

【思路】

? 本题是一道分析好题，其实现算法不难，在比赛中，其本身具有一定的分析深度。

? 我们按照不同的棋子，给出其走法方案数的分析，以及维护方法。

? 注意一点，在维护棋子的移动中，移动的维度的总数量是同 $O(k)$ 的，所以我们只需要思考某个维度移动之后如何维护答案即可。

【$\text{King}$】

? 我们发现各个维度之间的走法互不干扰，都有 $+1,0,?1$ 三种选择，于是通常情况下有 $3^k$ 种走法，减去不动的一种走法是 $3^k?1$ 种。但是有的时候，当我们处于边界了，有些走法就不能被采用了。如果第 $i$ 个维度的位置 $b_i=1$ ，则不能再 $?1$ ，如果 $b_i=a_i$ 则不能再 $+1$ 。

? 于是我们可以维护一下，当前位置下，能有两种选择的维度的数量 $c_2$ ，和能有三种选择的维度的数量 $c_3$ ，那么当前的合法走法就有 $2^{c_2}\times 3^{c_3}?1$ 种。

? 当某个维度发生移动时，我们先删掉它，根据他当前的位置更新 $c_2,c_3$ 的值，然后改变他的位置，再根据他新的位置更新 $c_2,c_3$ 的值即可。每次移动可以 $O(1)$ 维护，每次询问时可以写个快速幂构造答案，总复杂度 $O(k\log k)$ 。

struct King{
    int cnt[4];
    inline int cnti(int x)
    {
        return 1+(b[x]<a[x])+(b[x]>1);
    }
    inline int ans()
    {
        return (1ll*qpow(2,cnt[2])*qpow(3,cnt[3])-1+MOD)%MOD;
    }
    void opt(int x,int dlt)
    {
        cnt[cnti(x)]--;b[x]+=dlt;cnt[cnti(x)]++;
    }
    void work()
    {
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)cnt[cnti(i)]++;
        printf("%d\n",ans());
        for(int i=1;i<=m;i++)
        {
            int num,x,dlt;
            scanf("%d",&num);
            for(int j=1;j<=num;j++)
            {
                scanf("%d%d",&x,&dlt);
                opt(x,dlt);
            }
            printf("%d\n",ans());
        }
    }
}king;

【$\text{Queen}$】

? 我们发现 $\text{Queen}$ 和 $\text{King}$ 的走法几乎一致，只是需要对移动距离 $x\in [1,n]$ 全部做考虑。于是我们对每个移动距离 $x$ 都维护一下 $2^{c_{x2}}\times 3^{c_{x3}}$ 的值，那么答案就是 $（{\sum }_{x=1}^v{2}^{c_{x2}}\times 3^{c_{x3}}）?v$ ，其中 $v=10^6$ 。

? 当某个维度发生移动时，我们先删掉它：

? 根据他当前的位置 $b_i$ ，我们令 $u=a_i?b_i,v=b_i?1$ ，对于 $x>\max (u,v)$ 的移动距离，其贡献不受影响；对于 $x\le \min (u,v)$ 的移动距离，都少掉了一个 $3$ 选择的维度，因此把他们都除以 $3$ ；对于 $\min (u,v)<x\le \max (u,v)$ 的移动距离，都少掉了一个 $2$ 选择的维度，因此把他们都除以 $2$ 。也就是说，对移动距离分三个区间，对其中两个做区间除法（乘法，乘以逆元）。

? 然后我们改变这个维度，再考虑加入它：

? 根据他新的位置 $b_i$ ，我们令 $u=a_i?b_i,v=b_i?1$ ，和上面同理，正好相反，对于 $x\le \min (u,v)$ 的移动距离，把他们的贡献都乘以 $3$ ；对于 $\min (u,v)<x\le \max (u,v)$ 的移动距离，把他们都乘以 $2$ 。也是用两个区间乘法维护。

? 于是可以用一个初始化每个位置都为 $1$ 的线段树，维护区间乘法和 区间求和 线段树总和即可，总复杂度 $O(k\log v)$ 。

struct Queen{
    const static int VL = 1;
    const static int VR = 1000000;
    Segment_Tree seg;
    inline int ans()
    {
        return (seg.tr[1].sum-VR+MOD)%MOD;;
    }
    inline void add(int x)
    {
        int _b1 = min(a[x]-b[x],b[x]-1);
        int _b2 = max(a[x]-b[x],b[x]-1);
        if(_b1>0)seg.Multiply(1,VL,VR,1,_b1,3);
        if(_b2>_b1)seg.Multiply(1,VL,VR,_b1+1,_b2,2);
    }
    inline void del(int x)
    {
        int _b1 = min(a[x]-b[x],b[x]-1);
        int _b2 = max(a[x]-b[x],b[x]-1);
        if(_b1>0)seg.Multiply(1,VL,VR,1,_b1,inv[3]);
        if(_b2>_b1)seg.Multiply(1,VL,VR,_b1+1,_b2,inv[2]);
    }
    void opt(int x,int dlt)
    {
        del(x);b[x]+=dlt;add(x);
    }
    void work()
    {
        seg.Build(1,VL,VR);
        for(int i=1;i<=n;i++)add(i);
        printf("%d\n",ans());
        for(int i=1;i<=m;i++)
        {
            int num,x,dlt;
            scanf("%d",&num);
            for(int j=1;j<=num;j++)
            {
                scanf("%d%d",&x,&dlt);
                opt(x,dlt);
            }
            printf("%d\n",ans());
        }
    }
}queen;

【$\text{Rook}$】

? 唯一没用的棋子，无论走到哪里，下一步始终都有 $({\sum }_{i=1}^k{a}_i)?k$ 种走法。

? 于是直接输出 $q$ 次答案就可以了，总复杂度 $O(q)$ 。

struct Rook{
    void work()
    {
        int ans=0;for(int i=1;i<=n;i++)ans=(ans+a[i]-1)%MOD;
        for(int i=1;i<=m+1;i++)printf("%d\n",ans);
    }
}rook;

【$\text{Bishop}$】

? 之前的维护给了我们一个类似于差分的启示：只要我们能够动态维护一个维度出现/消失带来的贡献变化，我们就可以动态维护答案。

? 所以同理，我们可以这样来思考 $\text{Bishop}$ 。

? 该棋子有这个特点，如果棋子移动的两个维度以及其方向都选定了，那么走法是两个方向上能走的最大距离中较小的那一个。

? 如果加入一个维度，根据棋子目前的位置，这个维度在正方向上最多可以走 $u$ 的距离，在负方向上最多可以走 $v$ 的距离，那么这个维度会带来多少贡献呢？选中这个维度后，在这个维度上的走法无非就是 $u+v$ 种，如果选走正方向：

? 那么考虑其他所有维度的所有方向：如果其能走的长度 $x\le v$ ，那么能带来 $x$ 的贡献，如果 $x\ge v$ 那么就能带来 $v$ 的贡献。 所以只需要统计其他方向距边界距离小于等于 $v$ 的这些距离的总和，以及距边界距离大于 $v$ 的方向个数 $\times v$ 的值即可。

? 如果选走负方向，把 $v$ 换成 $u$ ，计算方式完全一致。

? 同样，如果是删除一个维度，计算其失去的贡献也是一样的。

? 可以发现，要这样计算贡献，需要对现有的方向的距边界距离做一个权值上的维护，支持单点修改和区间查询。

? 于是可以用两个权值树状数组，一个维护权值的数量，一个维护权值的和。总复杂度 $O(k\log v)$ 。

struct Bishop{
    const static int VL = 1;
    const static int VR = 1000000;
    BIT bnum,bsum;
    int ANS;
    inline int add(int x)
    {
        int ret=0;
        ret=(1ll*ret+bsum.getsum(a[x]-b[x])+1ll*(a[x]-b[x])*(bnum.getsum(VR)-bnum.getsum(a[x]-b[x])))%MOD;
        ret=(1ll*ret+bsum.getsum(b[x] - 1 )+1ll*(b[x] - 1 )*(bnum.getsum(VR)-bnum.getsum(b[x] - 1 )))%MOD;
        bnum.add(a[x]-b[x],1);bnum.add(b[x]-1,1);
        bsum.add(a[x]-b[x],a[x]-b[x]);bsum.add(b[x]-1,b[x]-1);
        return ret;
    }
    inline int del(int x)
    {
        int ret=0;
        bnum.add(a[x]-b[x],-1);bnum.add(b[x]-1,-1);
        bsum.add(a[x]-b[x],b[x]-a[x]+MOD);bsum.add(b[x]-1,1-b[x]+MOD);
        ret=(1ll*ret+bsum.getsum(a[x]-b[x])+1ll*(a[x]-b[x])*(bnum.getsum(VR)-bnum.getsum(a[x]-b[x])))%MOD;
        ret=(1ll*ret+bsum.getsum(b[x] - 1 )+1ll*(b[x] - 1 )*(bnum.getsum(VR)-bnum.getsum(b[x] - 1 )))%MOD;
        return ret;
    }
    inline int ans()
    {
        return ANS;
    }
    void opt(int x,int dlt)
    {
        ANS=(ANS-del(x)+MOD)%MOD;b[x]+=dlt;ANS=(ANS+add(x))%MOD;
    }
    void work()
    {
        ANS=0;
        for(int i=1;i<=n;i++)ANS=(ANS+add(i))%MOD;
        printf("%d\n",ans());
        for(int i=1;i<=m;i++)
        {
            int num,x,dlt;
            scanf("%d",&num);
            for(int j=1;j<=num;j++)
            {
                scanf("%d%d",&x,&dlt);
                opt(x,dlt);
            }
            printf("%d\n",ans());
        }
    }
}bishop;

【$\text{Knight}$】

? 同上，我们发现 $\text{Knight}$ 的移动也是选中两个维度，但是其在一个维度上走的方式很有限，可以类似 $\text{Bishop}$ 的方式来维护加入一个维度和删除一个维度带来的贡献变化，同时维护现有方向的各种走法的数量。

? 该棋子的特点是，如果棋子移动的两个维度以及其方向都选定了，一个维度走 $1$ 的距离，另一个维度走 $2$ 步。

? 我们直接用两个变量，分别维护当前考虑的维度中，有 $c_1$ 个方向可以走 $1$ 的距离，有 $c_2$ 个方向可以走 $2$ 的距离。

? 如果加入一个维度，根据棋子目前的位置，这个维度在正方向上最多可以走 $u$ 的距离，在负方向上最多可以走 $v$ 的距离。根据 $u,v$ 和 $1,2$ 的大小关系，就可以维护其带来的贡献。

? 删除一个维度同理。维护是 $O(1)$ 的。

? 总复杂度 $O(k)$ 。

struct Knight{
    int cnt[4];
    int ANS;
    inline int add(int x)
    {
        int ret=0;
        int u=a[x]-b[x],v=b[x]-1;
        if(u>=1)ret=(ret+cnt[2])%MOD;
        if(u>=2)ret=(ret+cnt[1])%MOD;
        if(v>=1)ret=(ret+cnt[2])%MOD;
        if(v>=2)ret=(ret+cnt[1])%MOD;
        if(u>=1)cnt[1]++;
        if(u>=2)cnt[2]++;
        if(v>=1)cnt[1]++;
        if(v>=2)cnt[2]++;
        return ret;
    }
    inline int del(int x)
    {
        int ret=0;
        int u=a[x]-b[x],v=b[x]-1;
        if(u>=1)cnt[1]--;
        if(u>=2)cnt[2]--;
        if(v>=1)cnt[1]--;
        if(v>=2)cnt[2]--;
        if(u>=1)ret=(ret+cnt[2])%MOD;
        if(u>=2)ret=(ret+cnt[1])%MOD;
        if(v>=1)ret=(ret+cnt[2])%MOD;
        if(v>=2)ret=(ret+cnt[1])%MOD;
        return ret;
    }
    inline int ans()
    {
        return ANS;
    }
    void opt(int x,int dlt)
    {
        ANS=(ANS-del(x)+MOD)%MOD;b[x]+=dlt;ANS=(ANS+add(x))%MOD;
    }
    void work()
    {
        ANS=0;
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)ANS=(ANS+add(i))%MOD;
        printf("%d\n",ans());
        for(int i=1;i<=m;i++)
        {
            int num,x,dlt;
            scanf("%d",&num);
            for(int j=1;j<=num;j++)
            {
                scanf("%d%d",&x,&dlt);
                opt(x,dlt);
            }
            printf("%d\n",ans());
        }
    }
}knight;

【其余部分的代码】

（树状数组、线段树、主函数，拼上上面那几个结构体就可以跑了）

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 310000
#define MAXM 1100000
#define MOD 998244353
using namespace std;
int n,m;
int a[MAXN],b[MAXN];
int inv[MAXM];
string str;
inline int qpow(int x,int y){int ret=1;while(y){if(y&1)ret=1ll*ret*x%MOD;x=1ll*x*x%MOD;y>>=1;}return ret;}
void init_inv()
{
    inv[0]=1;
    for(int i=1;i<MAXN;i++)inv[i]=1ll*inv[i-1]*i%MOD;
    inv[MAXN-1]=qpow(inv[MAXN-1],MOD-2);
    for(int i=MAXN-1;i>=1;i--)
    {
        int tmp = 1ll * inv[i-1] * inv[i] % MOD; 
        inv[i-1] = 1ll * inv[i] * i % MOD; 
        inv[i] = tmp;
    }
}

struct BIT{
    int q[MAXM];
    BIT(){memset(q,0,sizeof(q));}
    void add(int x,int v){x++;for(int i=x;i<MAXM;i+=i&-i)q[i]=(q[i]+v)%MOD;}
    int getsum(int x){x++;int ret=0;for(int i=x;i;i-=i&-i)ret=(ret+q[i])%MOD;return ret;}
};

struct Segment_Tree{
    struct node{
        int l,r,mul,sum;
        node(){l=r=sum=mul=0;}
    }tr[MAXM*4];
    int num;
    Segment_Tree(){num=1;}
    void pushup(int x)
    {
        tr[x].sum=(tr[tr[x].l].sum+tr[tr[x].r].sum)%MOD;
    }
    void Build(int x,int L,int R)
    {
        tr[x].mul=1;
        if(L==R)
        {
            tr[x].sum=1;return;
        }
        int mid=(L+R)/2;
        tr[x].l=++num;Build(num,L,mid);
        tr[x].r=++num;Build(num,mid+1,R);
        pushup(x);
    }
    inline void mul_node(int x,int v)
    {
        tr[x].mul=1ll*tr[x].mul*v%MOD;
        tr[x].sum=1ll*tr[x].sum*v%MOD;
    }
    void pushdown(int x)
    {
        if(tr[x].mul!=1)
        {
            int L=tr[x].l,R=tr[x].r;
            mul_node(L,tr[x].mul);mul_node(R,tr[x].mul);
            tr[x].mul=1;
        }
    }
    void Multiply(int x,int L,int R,int al,int ar,int v)
    {
        if(R<al||ar<L)return;
        if(al<=L&&R<=ar){mul_node(x,v);return;}
        int mid=(L+R)/2;pushdown(x);
        Multiply(tr[x].l,L,mid,al,ar,v);Multiply(tr[x].r,mid+1,R,al,ar,v);
        pushup(x);
    }
};

int main()
{
    init_inv();
    scanf("%d%d",&n,&m);
    cin>>str;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    if(str=="King")king.work();
    if(str=="Queen")queen.work();
    if(str=="Rook")rook.work();
    if(str=="Bishop")bishop.work();
    if(str=="Knight")knight.work();
    return 0;
}