题目大意
在一个(n*m)的矩阵上，一个格子((x,y))跳一步，将会到达((x-1,y+1),(x,y+1),(x+1,y+1))中权值最大的格子（保证没有相同权值）。矩阵是循环的，例如从第(m)列往右边跳会到第(1)列，从第(1)行往上跳会到第(n)行，从第(n)行往下跳会到第(1)行。
一个棋子放在((1,1))，现有两种操作：
- 询问棋子从当前位置跳(k)步后到了哪
- 修改某个格子的权值
你需要回答所有询问
(n,mleq 2000,kleq 10^9)，操作数(qleq 5000)，权值(eleq 10^9)。
分析
这题最关键的是要发现循环节。
一个点((x,y))最多跳(n*m)遍就会跑进一个环里面。对于每个询问，我们用(O(nm))的时间就能把这个环找出来，就不用暴力跳(k)步了。
现在的问题是，(O(nm))找环还是太慢了，是否有更快的方法？
假设棋子从第一列出发，如果能一次跳(m)步，我们找环的时间就是(O(n))了。所以，若棋子不在第一列，我们就暴力跳到第一列，时间复杂度是(O(m))。
那么如何维护第一列各行跳(m)步所到达行？DoggyZheng大爷提供了一种神奇的方法：
用一棵下标([1,m])的线段树，节点([l,r])开一个大小为(n)的数组，表示第(l)列各行跳(r-l+1)步后到达了第(r+1)列的哪一行
线段树的根代表区间是([1,m])，你要查询第一列某一行跳(m)步所到达行，直接用根的信息(O(1))查询就行了。
线段树信息复杂度是(O(n))，每次修改更改节点数是(O(logm))，修改复杂度就是(O(nlogm))，由于此题时限(4s)，很轻松就过掉了。
总而言之，这题的关键点就两个：
- 想到每次跳(m)步来更快找循环节
- 用线段树维护
emmmm，很有价值的一道题。
Code
#include <cstdio>
#include <cstring>
#define F(i, l, r) for (int i = l; i <= r; ++i)
#define lson rt << 1
#define rson rt << 1 | 1
const int N = 2007;
inline int read()
{
int x = 0, f = 0;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = 1;
for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ '0');
return f ? -x : x;
}
int n, m, q, tx, ty, a[N][N], vis[N];
char opt;
int getnext(int x, int y)
{
int x1 = x > 1 ? x - 1 : n, x2 = x < n ? x + 1 : 1, y1 = y < m ? y + 1 : 1;
if (a[x1][y1] > a[x][y1] && a[x1][y1] > a[x2][y1]) return x1;
if (a[x][y1] > a[x1][y1] && a[x][y1] > a[x2][y1]) return x;
if (a[x2][y1] > a[x][y1] && a[x2][y1] > a[x1][y1]) return x2;
}
int go[N << 2][N];
void ins(int rt, int l, int r, int po, int c)
{
if (l == r) { go[rt][c] = getnext(c, po); return; }
int mid = l + r >> 1;
if (po <= mid) ins(lson, l, mid, po, c);
else ins(rson, mid + 1, r, po, c);
F(i, 1, n) go[rt][i] = go[rson][go[lson][i]];
}
void build(int rt, int l, int r)
{
if (l == r) { F(i, 1, n) go[rt][i] = getnext(i, l); return; }
int mid = l + r >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
F(i, 1, n) go[rt][i] = go[rson][go[lson][i]];
}
int main()
{
freopen("jump.in", "r", stdin);
freopen("jump.out", "w", stdout);
n = read(), m = read();
F(i, 1, n) F(j, 1, m) a[i][j] = read();
build(1, 1, m);
q = read(), tx = 1, ty = 1;
while (q--)
{
scanf(" %c", &opt);
if (opt == 'm')
{
int k = read(), nx, cnt = 0;
while (k > 0 && ty != 1) tx = getnext(tx, ty), ty = ty < m ? ty + 1 : 1, k--;
if (!k) { printf("%d %d
", tx, ty); continue; }
memset(vis, 0, sizeof(vis));
nx = tx;
while (!vis[nx]) vis[nx] = 1, nx = go[1][nx], cnt += m;
while (k >= m && tx != nx) tx = go[1][tx], k -= m, cnt -= m;
if (tx != nx) while (k > 0) tx = getnext(tx, ty), ty = ty < m ? ty + 1 : 1, k--;
else
{
k %= cnt;
while (k >= m) tx = go[1][tx], k -= m;
while (k > 0) tx = getnext(tx, ty), ty = ty < m ? ty + 1 : 1, k--;
}
printf("%d %d
", tx, ty);
}
else
{
int x = read(), y = read(), e = read(), x1 = x > 1 ? x - 1 : n, x2 = x < n ? x + 1 : 1, y1 = y > 1 ? y - 1 : m;
a[x][y] = e, ins(1, 1, m, y1, x1), ins(1, 1, m, y1, x), ins(1, 1, m, y1, x2);
}
}
return 0;
}