Brief question:

For an n × mn\times mn × M matrix, the weight of the third row and j j j column is (I − 1) ⋅ m+j (i-1) ⋅ cdot m+j (I − 1) ⋅ m+j. you need to support the following three operations:

1. R. Exchange two lines
2. C. Exchange two columns
3. Q. Ask to find the sum of the elements in the two-dimensional prefix and post matrix of kkk degree for a submatrix.

Data range: n,m,Q ≤ 1e5,k ≤ 10n,m,Q\leq 1e5,k\leq 10n,m,Q ≤ 1e5,k ≤ 10

Explanation:

It's easy to find that the weight of a point is only related to the row number and column number, and it's easy to think of maintaining the row and column separately.

The subrectangle of inquiry is represented by (lx,ly) - (rx,ry)(lx,ly)-(rx,ry)(lx,ly) - (rx,ry).

Simply consider the sum of prefixes and how many times each position has been calculated, which can be expressed as:

Ans=∑i=lxrx∑j=lyry(k+rx−ik)(k+ry−jk)(ai+bj) Ans=\sum_{i=lx}^{rx}\sum_{j=ly}^{ry}{k+rx-i\choose k}{k+ry-j\choose k}(a_i+b_j) Ans=i=lx∑rx​j=ly∑ry​(kk+rx−i​)(kk+ry−j​)(ai​+bj​)

AIA and BJB represent the contribution of rows and columns to the lattice weight respectively.

It is obvious that there are two forms of splitting:

Ans=(k+ry−ly+1k+1)∑i=lxrx(k+rx−ik)ai+(k+rx−lx+1k+1)∑i=lyry(k+ry−ik)bi \begin{aligned} Ans&={k+ry-ly+1\choose k+1}\sum_{i=lx}^{rx}{k+rx-i\choose k}a_i\\ &+{k+rx-lx+1\choose k+1}\sum_{i=ly}^{ry}{k+ry-i\choose k}b_i \end{aligned} Ans​=(k+1k+ry−ly+1​)i=lx∑rx​(kk+rx−i​)ai​+(k+1k+rx−lx+1​)i=ly∑ry​(kk+ry−i​)bi​​

Consider maintaining AIA, bib and IBI in the same way.

In fact, it's quite obvious that the combination number with the same bottom standard is converted to the lower power by force, and then it is converted to the natural power by Stirling number of the first type with sign, and then it can be expanded by binomial.

First, turn it to the lower power, that is, consider to find:

1k!∑i=lxrx(k+rx−i)k‾ai \frac{1}{k!}\sum_{i=lx}^{rx}(k+rx-i)^{\underline k}a_i k!1​i=lx∑rx​(k+rx−i)k​ai​

To convert a signed Stirling number of the first type to a natural power:

Ans=∑i=lxrxai∑t=0ksk,t(k+rx−i)t=∑i=lxrxai∑t=0ksk,t∑l=0t(−i)l(rx+k)t−l(tl)=∑l=0k(∑i=lxrxai(−i)l)∑t=lksk,t(tl)(rx+k)t−l \begin{aligned} Ans=&\sum_{i=lx}^{rx}a_i\sum_{t=0}^ks_{k,t}(k+rx-i)^t\\ =&\sum_{i=lx}^{rx}a_i\sum_{t=0}^k s_{k,t}\sum_{l=0}^t(-i)^l(rx+k)^{t-l}{t\choose l}\\ =&\sum_{l=0}^k\left(\sum_{i=lx}^{rx}a_i(-i)^l\right)\sum_{t=l}^ks_{k,t}{t\choose l}(rx+k)^{t-l} \end{aligned} Ans===​i=lx∑rx​ai​t=0∑k​sk,t​(k+rx−i)ti=lx∑rx​ai​t=0∑k​sk,t​l=0∑t​(−i)l(rx+k)t−l(lt​)l=0∑k​(i=lx∑rx​ai​(−i)l)t=l∑k​sk,t​(lt​)(rx+k)t−l​

Thus, any data structure can be used to maintain Σ I = LX rx ai (− i)l \ sum \ limits {I = LX} {rx} a I (- I) ^ Li = LX Σ rx ai (− i)l for each lll.

The latter one can query O(k2)O(k^2)O(k2) preprocessing every time, and then enumerate lll to query in the data structure

In this way, the complexity of single modification is O (k log ⁡ n)O(k\log n)O(klogn), and the complexity of single query is O(k2+klog ⁡ n)O(k^2+k\log n)O(k2+klogn)

Code:

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

namespace IO{
	inline char gc(){
		static cs int Rlen=1<<22|1;static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}template<typename T>T get_integer(){
		char c;while(!isdigit(c=gc()));T x=c^48;
		while(isdigit(c=gc()))x=x*10+(c^48);return x;
	}inline int gi(){return get_integer<int>();}
	inline char ga(){char c;while(!isalpha(c=gc()));return c;}
	char obuf[3000006],*oh=obuf;
	template<typename T>void print(T a,char c=' '){
		static char ch[23];int tl=0;
		do ch[++tl]=a%10; while(a/=10);
		while(tl)*oh++=ch[tl--]^48;*oh++=c;
	}struct obuf_flusher{~obuf_flusher(){fwrite(obuf,1,oh-obuf,stdout);}}Flusher;
}using namespace IO;

using std::cerr;
using std::cout;

cs int mod=1e9+7;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(int a,int b){return a-b<0?a-b+mod:a-b;}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}
inline void Inc(int &a,int b){a+=b-mod;a+=a>>31&mod;}
inline void Dec(int &a,int b){a-=b;a+=a>>31&mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline int po(int a,int b){int r=1;for(;b;b>>=1,Mul(a,a))if(b&1)Mul(r,a);return r;}
inline void ex_gcd(int a,int b,int &x,int &y){
	if(!b){x=1,y=0;return;}ex_gcd(b,a%b,y,x);y-=a/b*x;
}inline int inv(int a){int y,x;ex_gcd(mod,a,y,x);return x+(x>>31&mod);}

cs int N=1e5+17;

int n,m,Q;

int Vx[N],Vy[N];
struct BIT{
	int tr[N],n;
	inline void init(int *a,int n){
		this->n=n;memcpy(tr,a,sizeof(int)*(n+1));
		for(int re i=1;i<=n;++i)if(i+(i&-i)<=n)Inc(tr[i+(i&-i)],tr[i]);
	}
	inline void modify(int p,int vl){for(;p<=n;p+=p&-p)Inc(tr[p],vl);}
	inline int qy(int p)cs{int r=0;for(;p;p^=p&-p)Inc(r,tr[p]);return r;}
	inline int qy(int l,int r)cs{assert(1<=l&&l<=r&&r<=n);return dec(qy(r),qy(l-1));}
}Px[11],Py[11];

int fac[N],ifc[N];
int c[11][11],s[11][11];
inline int C(int n,int m){return n>=m&&m>=0?mul(fac[n],mul(ifc[n-m],ifc[m])):0;}
void init_math(){
	fac[0]=1;
	for(int re i=1;i<N;++i)fac[i]=mul(fac[i-1],i);
	ifc[N-1]=inv(fac[N-1]);
	for(int re i=N-1;i;--i)ifc[i-1]=mul(ifc[i],i);
	s[0][0]=c[0][0]=1;
	for(int re i=1;i<=10;++i){c[i][0]=1;
		for(int re j=1;j<=i;++j){
			c[i][j]=add(c[i-1][j],c[i-1][j-1]);
			s[i][j]=dec(s[i-1][j-1],mul(s[i-1][j],i-1));
		}
	}
}

int coef_x[11],coef_y[11];
void Qry(){
	int lx=gi(),ly=gi(),rx=gi(),ry=gi(),k=gi();
	assert(lx<=rx&&rx<=1e5&&ly<=ry&&ry<=1e5);
	for(int re l=0;l<=k;++l){
		int px=1,py=1;
		coef_x[l]=coef_y[l]=0;
		for(int re t=l;t<=k;++t){
			int coef=mul(s[k][t],c[t][l]);
			Inc(coef_x[l],mul(coef,px));
			Inc(coef_y[l],mul(coef,py));
			Mul(px,rx+k),Mul(py,ry+k);
		}
	}int vl_x=0,vl_y=0;
	for(int re l=0;l<=k;++l){
		Inc(vl_x,mul(Px[l].qy(lx,rx),coef_x[l]));
		Inc(vl_y,mul(Py[l].qy(ly,ry),coef_y[l]));
	}
	print(add(mul(mul(vl_x,ifc[k]),C(k+ry-ly+1,k+1))
			,mul(mul(vl_y,ifc[k]),C(k+rx-lx+1,k+1))),'\n');
}

void modify_x(){
	int u=gi(),v=gi();
	assert(u<=1e5&&v<=1e5);
	std::swap(Vx[u],Vx[v]);
	int vl_u=1,vl_v=1;
	for(int re i=0;i<=10;++i){
		Px[i].modify(u,mul(vl_u,dec(Vx[u],Vx[v])));
		Px[i].modify(v,mul(vl_v,dec(Vx[v],Vx[u])));
		Mul(vl_u,mod-u),Mul(vl_v,mod-v);
	}
}

void modify_y(){
	int u=gi(),v=gi();
	std::swap(Vy[u],Vy[v]);
	int vl_u=1,vl_v=1;
	for(int re i=0;i<=10;++i){
		Py[i].modify(u,mul(vl_u,dec(Vy[u],Vy[v])));
		Py[i].modify(v,mul(vl_v,dec(Vy[v],Vy[u])));
		Mul(vl_u,mod-u),Mul(vl_v,mod-v);
	}
}

void Main(){
	init_math();
	n=gi(),m=gi(),Q=gi();
	for(int re i=1;i<=n;++i)Vx[i]=mul(i-1,m);
	for(int re i=1;i<=m;++i)Vy[i]=i;
	for(int re k=0;k<=10;++k){
		Px[k].init(Vx,n);Py[k].init(Vy,m);
		for(int re i=1;i<=n;++i)Mul(Vx[i],mod-i);
		for(int re i=1;i<=m;++i)Mul(Vy[i],mod-i);
	}
	for(int re i=1;i<=n;++i)Vx[i]=mul(i-1,m);
	for(int re i=1;i<=m;++i)Vy[i]=i;
	while(Q--)switch(ga()){
		case 'R':modify_x();break;
		case 'C':modify_y();break;
		case 'Q':Qry();break;
	}
}

inline void file(){
#ifdef zxyoi
	freopen("matrix.in","r",stdin);
#endif
}
signed main(){file();Main();return 0;}