数据范围：(r,c<=2000,m<=5000,1<=M_{ij},c)(操作中的)(,k<=10^9)
Solution
形式化一下这个移动的过程，考虑如果没有修改，那么对于第(x)列的第(i)行，我们可以预处理出它(move)一步之后会在第(nxt(x))列哪一行，具体一点就是我们可以对于每一列预处理出一个长度为(r)的数组，记为(change[x][i])，有了这个数组之后，我们从(change[1])合并到(change[c])就可以得到一个新的数组(change1)，其中(change1[i])表示从第(1)列的第(i)行(move)到第(c)列之后在哪一行
记当前所在位置为((nowx,nowy))，考虑询问，因为列数(c)比较小，所以对于一次(move k)操作，我们可以先暴力将当前的列跳到第(1)列（如果有那么多次的话），这需要(c-nowy+1)步，然后剩下(k-(c-nowy+1))步我们可以先利用(change1)数组一圈一圈地跳（也就是(c)步(c)步跳），具体的话就是可以实现一个类似快速幂一样的东西，计算数组({1,2,3,4,...,r})在连续被(change1)作用了(x)次之后会变成什么（记为。。(change1^{x})好了），然后跳完那么多圈之后还是在第(1)列，所以这个时候的位置是((change1^x[nowx'],nowy))，这里的(nowx')是暴力跳到第(1)列之后的所在行数，然后剩下((k-(c-nowy+1))\%c)步也是直接暴力跳就好了
现在考虑有修改，瓶颈在于要重新计算(change1)，但是考虑一次修改对于(change)数组的影响，如果说修改的地方是((x,y))，那么只会影响到(change[nxt(x)])这一个数组的值
所以我们可以考虑将所有的(change[i])丢进线段树作为线段树的底层节点维护的信息，这样(change1)就是线段树根节点处的值了，对于一次修改直接重新算一遍(change[nxt(x)])，然后将线段树中(nxt(x))这个位置的值更新一下即可
mark：想清楚一次修改的影响
Code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2010;
int a[N][N];
int n,m,q,nowx,nowy;
struct Data{
int p[N];
void init(){for (int i=1;i<=n;++i) p[i]=i;}
friend Data operator + (Data x,Data y){
for (int i=1;i<=n;++i) x.p[i]=y.p[x.p[i]];
return x;
}
}change[N];
namespace Seg{/*{{{*/
const int N=::N*4;
int ch[N][2];
Data info[N];
int n,tot;
void pushup(int x){info[x]=info[ch[x][0]]+info[ch[x][1]];}
void _build(int x,int l,int r){
if (l==r){info[x]=change[l];return;}
int mid=l+r>>1;
ch[x][0]=++tot; _build(ch[x][0],l,mid);
ch[x][1]=++tot; _build(ch[x][1],mid+1,r);
pushup(x);
}
void build(int _n){n=_n; tot=1;_build(1,1,n);}
void _update(int x,int d,int lx,int rx){
if (lx==rx){
info[x]=change[lx]; return;
}
int mid=lx+rx>>1;
if (d<=mid) _update(ch[x][0],d,lx,mid);
else _update(ch[x][1],d,mid+1,rx);
pushup(x);
}
void update(int d){_update(1,d,1,n);}
}/*}}}*/
int X(int x){x=(x+n)%n;return x==0?n:x;}
int Y(int y){y=(y+m)%m;return y==0?m:y;}
int work(int x,int y){
int nwy=Y(y+1),pre=X(x-1),nxt=X(x+1);
int ret=x;
if (a[pre][nwy]>a[ret][nwy]) ret=pre;
if (a[nxt][nwy]>a[ret][nwy]) ret=nxt;
return ret;
}
void prework(){
int pre,nxt,tmp,nwy;
for (int x=1;x<=n;++x)
for (int y=1;y<=m;++y)
change[y].p[x]=work(x,y);
Seg::build(m);
}
void modify(int y){
for (int i=1;i<=n;++i)
change[y].p[i]=work(i,y);
Seg::update(y);
}
void force_move(int &x,int &y,int tm){
for (int i=1;i<=tm;++i)
x=change[y].p[x],y=Y(y+1);
}
Data ksm(Data &x,int y){
Data ret,base=x;
ret.init();
for (;y;y>>=1,base=base+base)
if (y&1) ret=ret+base;
return ret;
}
void solve(int tm){
int tm1=min(tm,m-nowy+1);
Data tmp;
force_move(nowx,nowy,tm1);
tmp=ksm(Seg::info[1],(tm-tm1)/m);
nowx=tmp.p[nowx];
force_move(nowx,nowy,(tm-tm1)%m);
printf("%d %d
",nowx,nowy);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
char op[10];
int x,y,z;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
scanf("%d",&a[i][j]);
prework();
nowx=1; nowy=1;
scanf("%d",&q);
for (int i=1;i<=q;++i){
scanf("%s",op);
if (op[0]=='m'){
scanf("%d",&x);
solve(x);
}
else{
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
modify(Y(y-1));
}
}
}