【CERC2017】Donut Drone

Description:


一个矩形方块,有\(n\)行\(m\)列个格子,水平和垂直方向上都可以将它视为首尾相连的(也即从最右边向右移会回到最左边,从最下边向下移会回来最上边,以此类推)。每个格子上有一个数。每一次移动会往相邻的右边、右上、右下的三个格子中选最大数的格子移动(保证存在唯一最大值)。初始位置在左上角 (1, 1)。\(q\)次操作,操作分为两种:

  1. move k移动\(k\)步,输出新位置;
  2. change x y z 修改\((x,y)\)格子中的数为\(z\)。

\(3\leq n, m \leq 2000 , 1 \leq q \leq 5000\)

Examples:


input1output1
4 4
1 2 9 3
3 5 4 8
4 3 2 7
5 8 1 6
4
move 1
move 1
change 1 4 100
move 1
4 2
1 3
1 4
input2output2
3 4
10 20 30 40
50 60 70 80
90 93 95 99
3
move 4
change 2 1 100
move 4
3 1
2 1

Solution:


预处理出 jump数组 jump[i]表示从第一列的第 i行出发,移动 m步回到第一列的第 jump[i]行。这样就可以\(\mathcal{O}(1)\)移动 m步,显然从当前行一直沿着 jump走最后会形成\(\rho\)的结构,即最后进入一个环,因此如果已知 jump数组对于每个询问 move k可以\(\mathcal{O}(m)\)完成。

于是考虑 change x y z后维护 jump数组,首先更改 (x, y)只会对能走到该块左上角,正左,左下角块的第一列的 jump有影响。而第一列能走到某一块的,可以发现是一段连续的区间。因此,在不停的往回走时维护区间的上下端点,就可以找出所求的区间。于是可以在\(\mathcal{O}(m)\)内维护 jump

大功告成,细节见代码。复杂度\(\mathcal{O}((n+m)q)\)

Code:


1 评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注