时间复杂度的均衡。
先考虑暴力的想法：显然这是一棵基环树，那么我们每次修改时暴力 \(O(nm)\) 重构基环树，然后询问的时候就能 \(O(1)\) 查询。时间复杂度 \(O(nmq)\)。
考虑均衡时间复杂度，我们考虑只记录第一列的每个点 \(i\) 走 \(m\) 步之后会绕回第一列的哪个点，设为 \(F_i\)。那么这棵基环树的大小就是 \(n\) 了。然后询问的时候只需要先 \(O(m)\) 暴力走到第一列再直接 \(O(1)\) 在基环树上走然后再 \(O(m)\) 走完剩下的步数。
思考修改也能不能同样降复杂度。
答案是可行的。假设修改了点 \((x,y)\) 的值，假设 \((x,y)\) 往后走会走到第一列的第 \(t\) 个位置。我们可以从第 \(x\) 列往前推当前列的哪些位置往后走所到达的第一列的位置被更改了（显然若被更改只会被更改为 \(t\)），发现这始终是一个区间：假设第 \(i+1\) 列是区间 \([l,r]\) 的位置被改为了 \(t\)，那么当前第 \(i\) 列的 \([l+1,r-1]\) 的位置肯定也被更改为 \(t\)，而位置 \(l-1,l,r,r+1\) 都有可能被更改为 \(t\)，这四个位置直接暴力讨论即可。而且不可能存在 \(l-1\) 被改为了 \(t\) 而 \(l\) 不会改的情况，于是这始终是一个区间。最后推到第一列即为要更改的 \(F_i\)。然后我们再暴力 \(O(n)\) 重构基环树。
修改时间复杂度 \(O(n+m)\)，询问时间复杂度 \(O(m)\)。
修改降复杂度的做法有点难看出来，下面有一个更加暴力的做法：
审视修改时我们要解决的问题：修改某一个位置 \((x,y)\) 的值，然后更新 \(F_i\)，即求第一列每个点走完一圈后会回到第一列的哪个点。
直接上线段树。用线段树维护每一列每个点往后走一步会走到下一列哪个点，即线段树每个节点存一个大小为 \(n\) 的数组，然后合并的时候暴力 \(O(n)\) 合并。
那么在线段树中修改第 \(x-1\) 列，然后再更新 \(F_i\) 即可。
修改时间复杂度 \(O(n\log m)\)，询问时间复杂度 \(O(m)\)。
然后你不想写基环树的话可以直接用倍增，修改时间复杂度 \(O(n(\log m+\log k))\)，询问时间复杂度 \(O(m+\log k)\)。
写的是最后一种码量最小但时间复杂度最大做法：
#include<bits/stdc++.h>
#define N 2010
#define LN 31
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int n,m,q,a[N][N],f[N][3];
int bit[LN],F[N][LN];
int nxt[N<<2][N];
int nxtx(int x,int y)
{
int nxty=y%m+1;
int maxn=0,maxx;
for(int i=0;i<3;i++)
{
if(a[f[x][i]][nxty]>maxn)
{
maxn=a[f[x][i]][nxty];
maxx=f[x][i];
}
}
return maxx;
}
void up(int k)
{
for(int i=1;i<=n;i++)
nxt[k][i]=nxt[k<<1|1][nxt[k<<1][i]];
}
void build(int k,int l,int r)
{
if(l==r)
{
for(int i=1;i<=n;i++)
nxt[k][i]=nxtx(i,l);
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
up(k);
}
void update(int k,int l,int r,int x)
{
if(l==r)
{
for(int i=1;i<=n;i++)
nxt[k][i]=nxtx(i,l);
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(k<<1,l,mid,x);
else update(k<<1|1,mid+1,r,x);
up(k);
}
void getF()
{
for(int i=1;i<=n;i++)
F[i][0]=nxt[1][i];
for(int j=1;j<=30;j++)
for(int i=1;i<=n;i++)
F[i][j]=F[F[i][j-1]][j-1];
}
int main()
{
bit[0]=1;
for(int i=1;i<=30;i++) bit[i]=bit[i-1]<<1;
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read();
for(int i=1;i<=n;i++)
f[i][0]=(i-2+n)%n+1,f[i][1]=i,f[i][2]=i%n+1;
build(1,1,m);
getF();
q=read();
int nx=1,ny=1;
while(q--)
{
char opt[10];
scanf("%s",opt);
if(opt[0]=='m')
{
int k=read();
while(k>0&&ny!=1)
{
nx=nxtx(nx,ny);
k--,ny=ny%m+1;
}
if(!k)
{
printf("%d %d\n",nx,ny);
continue;
}
int div=k/m;
k-=m*div;
for(int i=30;i>=0;i--)
{
if(div-bit[i]>=0)
{
nx=F[nx][i];
div-=bit[i];
}
}
while(k>0)
{
nx=nxtx(nx,ny);
k--,ny=ny%m+1;
}
printf("%d %d\n",nx,ny);
}
else
{
int x=read(),y=read();
a[x][y]=read();
update(1,1,m,(y-2+m)%m+1);
getF();
}
}
return 0;
}
/*
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
*/
/*
3 4
10 20 30 40
50 60 70 80
90 93 95 99
3
move 4
change 2 1 100
move 4
*/