存一下最近几场比赛的代码

太弱没脸发题解，反正有官方题解对吧

CH弱省胡策

r3:

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define eps 1e-8
using namespace std;

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
} 

const int MAXN=5e5+5;
const int MAXM=3005;

struct edge{
	int t,n;
	edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN];
int head[MAXN];
inline void AddEdge(int s,int t){
	static int o=1;
	e[o]=edge(t,head[s]),head[s]=o++;
}

int par[MAXN][20],dep[MAXN];

int rt;

void prev(int x){
	if(dep[x])return;
	if(~*par[x]){
		prev(*par[x]);
		AddEdge(*par[x],x);
		dep[x]=dep[*par[x]]+1;
		for(int i=0;par[x][i];++i)
			par[x][i+1]=par[par[x][i]][i]; 
	}
	else rt=x,dep[x]=1;
}

int B[MAXN],R[MAXN];

int b[MAXN],r[MAXN],w[MAXN];

bool u[MAXN];

int n,m,k,l;

inline int swim(int x,int h){
	for(int i=0;h;++i,h>>=1)
		if(h&1)x=par[x][i];
	return x;
}

void dp(int x){
	for(int i=head[x],y;i;i=e[i].n){
		dp(y=e[i].t);
		B[x]+=B[y],R[x]+=R[y];
	}
}

typedef double db;
const db pi=acos(-1.);
#define sqr(x) (db(x)*(x))

struct poi{
	int x,y,w;
	poi(int x=0,int y=0,int w=0):
		x(x),y(y),w(w){}
	inline db alpha(){return atan2(y,x);}
}p[MAXM];

inline poi operator-(const poi&a,const poi&b){
	return poi(a.x-b.x,a.y-b.y);
}

inline void Init(){
	Scan(n),Scan(k),Scan(l);
	rep(i,1,n){
		Scan(b[i]),Scan(r[i]);
		Scan(w[i]),Scan(*par[i]),Scan(u[i]);
	}
	rep(i,1,n)prev(i);
	rep(i,1,n){
		B[i]+=b[i],R[i]+=r[i];
		if(dep[i]<=k)continue;
		int y=swim(i,k);
		B[y]-=b[i],R[y]-=r[i];
	}
	dp(rt);
	rep(i,1,n)
		if(u[i])p[++m]=poi(B[i],R[i],w[i]);
}

inline db normalize(db x){
	while(x<-pi)x+=pi*2.;
	while(x>=pi)x-=pi*2.;
	return x;
}

struct event{
	db alpha;
	int w;
	event(db alpha=0,int w=0):alpha(alpha),w(w){}
}eve[MAXM<<2];
int tot;

inline bool cmp(const event&a,const event&b){
	return a.alpha!=b.alpha?a.alpha<b.alpha:a.w>b.w; 
}

inline db dis(const poi&a,const poi&b){
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

inline int calc(int x){
	tot=0;
	rep(i,1,m){
		if(i==x)continue;
		db L=dis(p[x],p[i]);
		if(L-l*2>eps)continue;
		db alpha=(p[i]-p[x]).alpha();
		db delta=acos(L/(l*2));
		db s=normalize(alpha-delta);
		db t=normalize(alpha+delta);
		eve[++tot]=event(s,p[i].w);
		eve[++tot]=event(t,-p[i].w);
		if(s>t){
			eve[++tot]=event(-pi,p[i].w);
			eve[++tot]=event(pi,-p[i].w);
		}
	}
	sort(eve+1,eve+1+tot,cmp);
	int res=0,sum=0;
	rep(i,1,tot){
		sum+=eve[i].w;
		res=max(res,sum);
	}
	return res+p[x].w;
}

inline void Solve(){
	int ans=0;
	rep(i,1,m)ans=max(ans,calc(i));
	printf("%d\n",ans);
}

int main(){
	Init(); Solve(); return 0;
}

#include <map>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define inv(x,P) qpow(x,P-2,P)
#define DFT(a,n,P) fft(a,n,0,P)
#define IDFT(a,n,P) fft(a,n,1,P)
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

const int MAXN=(1<<18)+5;
typedef unsigned long long ll;
const int P1=1004535809;
const int P2=998244353;
const int G=3;
const ll P=(ll)P1*P2;

inline ll qpow(ll x,ll k,ll M){
	ll ans=1;
	for(;k;x=x*x%M,k>>=1)
		if(k&1)ans=ans*x%M;
	return ans;
}

int w[2][MAXN],r[MAXN],rn;

inline void init_fft(int n,int bit,int P){
	rn=inv(n,P);
	int g=qpow(G,(P-1)/n,P);
	w[0][0]=w[0][n]=1;
	rep(i,1,n-1)w[0][i]=(ll)w[0][i-1]*g%P;
	rep(i,0,n)w[1][i]=w[0][n-i];
	rep(i,1,n)r[i]=(r[i>>1]>>1)|((i&1)<<(bit-1));
}

inline void fft(int*a,int n,int t,int P){
	rep(i,1,n)if(i<r[i])swap(a[i],a[r[i]]);
	for(int i=2;i<=n;i<<=1)
		for(int j=0;j<n;j+=i)
			for(int k=0;k<i>>1;++k){
				int re=(ll)a[(i>>1)+j+k]*w[t][n/i*k]%P;
				a[(i>>1)+j+k]=(a[j+k]+P-re)%P;
				a[j+k]=(a[j+k]+re)%P;
			}
	if(t)rep(i,0,n-1)a[i]=(ll)a[i]*rn%P;
}

bool ban[MAXN];

int p[MAXN],phi[MAXN],tot;

inline void get_phi(int n){
	phi[1]=1;
	rep(i,2,n){
		if(!ban[i]){
			p[++tot]=i;
			phi[i]=i-1;	
		}
		rep(j,1,tot){
			if((ll)i*p[j]>n)break;
			int x=i*p[j];
			ban[x]=1;
			if(i%p[j]){
				phi[x]=phi[i]*(p[j]-1);
			}
			else{
				phi[x]=phi[i]*p[j];
				break;
			}
		}
	}
	rep(i,1,n)phi[i]%=23;
}

inline ll qmul(ll a,ll b,ll M){
	ll ans=0;
	for(;b;b>>=1,a=(a<<1)%M)
		if(b&1)ans=(ans+a)%M;
	return ans;
}

const int r_P2=inv(P2,P1);
const int r_P1=inv(P1,P2);

inline ll crt(ll x1,ll x2){
	ll ans=0;
	ans+=qmul(qmul(x1,P2,P),r_P2,P);
	ans+=qmul(qmul(x2,P1,P),r_P1,P);
	return ans%P;
}

int n,len,bit;

int a[MAXN],c[MAXN];

map<int,int>g;

inline void Init(){
	Scan(n);
	get_phi(n);
	len=n<<1,bit=1;
	while(1<<bit<len)++bit;
	len=1<<bit;
	g[1]=0;
	int tmp=1;
	rep(i,1,100000){
		tmp=(ll)tmp*G%P1;
		g[tmp]=i;
	}
	rep(i,0,n-1){
		Scan(a[i]);
		if(i)a[i]=(a[i]+a[i-1])%P1;
	}
	rep(i,0,n-1)a[i]=g[a[i]];
}

int a1[MAXN],a2[MAXN];

int c1[MAXN],c2[MAXN];

inline void calc_C(){
	rep(i,0,n-1){
		a1[i]=a2[i]=a[i];
		c1[i]=c2[i]=phi[i];
	}
	
	init_fft(len,bit,P2);
	DFT(a2,len,P2),DFT(c2,len,P2);
	rep(i,0,len-1)c2[i]=(ll)a2[i]*c2[i]%P2;
	IDFT(c2,len,P2);
	
	init_fft(len,bit,P1);
	DFT(a1,len,P1),DFT(c1,len,P1);
	rep(i,0,len-1)c1[i]=(ll)a1[i]*c1[i]%P1;
	IDFT(c1,len,P1);
	rep(i,0,n-1)c[i]=qpow(G,crt(c1[i],c2[i])%(P1-1),P1);
	for(int i=n;i;--i)c[i]=c[i-1];
	c[0]=0;
}

inline void Solve(){
	calc_C();
	DFT(c,len,P1);
	rep(i,0,len-1)c[i]=(ll)c[i]*c[i]%P1;
	IDFT(c,len,P1);
	int ans=0;
	rep(i,0,n)ans=(ans+c[i])%P1;
	printf("%d\n",ans);
}

int main(){
	Init(); Solve(); return 0;
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i) 
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

const int MAXN=5e6+5;
const int Mod=1e9+7;
typedef long long ll;

bool ban[MAXN];

int p[MAXN],tot;

int fac[MAXN],fib[MAXN];

inline void get_prime(int n){
	fib[1]=fac[1]=1;
	rep(i,2,n){
		fib[i]=(fib[i-1]+fib[i-2])%Mod;
		if(!ban[i])p[++tot]=i,fac[i]=i;
		rep(j,1,tot){
			if(1ll*i*p[j]>n)break;
			ban[i*p[j]]=1;
			fac[i*p[j]]=p[j];
			if(!(i%p[j]))break;
		}
	}
}

int n,f[MAXN];

inline int gcd(int a,int b){
	for(;b;swap(a,b),b%=a);
	return a;
}

int ans,mx;

inline void Init(){
	get_prime(5e6);
	Scan(n);
	rep(i,1,n){
		int tp,x;Scan(tp);
		if(tp){
			int a,b;
			Scan(a),Scan(b);
			x=a+b-gcd(a,b);
		}
		else Scan(x);
		++f[x];
		ans=(ans+fib[x])%Mod;
		mx=max(x,mx);
	}
}

ll d[MAXN];

void div(int x,int cur,int v){
	if(x==1){
		d[cur]+=v;
		return;
	}
	else{
		int res=fac[x],cnt=0,tmp=1;
		for(;!(x%res);++cnt,x/=res);
		rep(i,0,cnt){
			div(x,cur*tmp,v);
			tmp*=res;
		}
	}
}

inline void Solve(){
	rep(i,1,mx)if(f[i])div(i,1,f[i]);
	for(int i=mx;i;--i){
		if(!d[i])continue;
		d[i]=d[i]*(d[i]-1)>>1;
		for(int j=i<<1;j<=mx;j+=i)d[i]-=d[j];
		ans=(ans+d[i]*fib[i]%Mod)%Mod;
	}
	printf("%d\n",ans);
}

int main(){
	Init(); Solve(); return 0;
}

r4

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define eps 1e-6
#define inf 1e20
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define fore(i,x) for(int i=head[x];i;i=e[i].n)if(e[i].c>e[i].f)
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

const int MAXN=2000;
typedef double db;

struct edge{
	int t;db c,f;int n;
	edge(int t=0,db c=0,db n=0):
		t(t),c(c),f(0),n(n){}
}e[MAXN<<2];
int head[MAXN],tot;
inline void AddEdge(int s,int t,db c){
	e[++tot]=edge(t,c,head[s]),head[s]=tot;
	e[++tot]=edge(s,0,head[t]),head[t]=tot;
}

int d[MAXN],p[MAXN],g[MAXN],cur[MAXN];

int q[MAXN];

inline db isap(int s,int t,int n){
	rep(i,1,n)d[i]=n;
	rep(i,0,n)g[i]=0;
	int tail=1;
	q[tail]=t,d[t]=0;
	for(int j=1;j<=tail;++j){
		int x=q[j];
		for(int i=head[x],y;i;i=e[i].n)
			if(!e[i].c&&d[y=e[i].t]==n){
				d[y]=d[x]+1;
				q[++tail]=y;
			}
	}
	rep(i,1,n){
		cur[i]=head[i],++g[d[i]];
	}
	db flow=0,a;int x=s,f;
	while(d[s]<n){
		if(x==t){
			a=inf;
			for(int i=t;i!=s;i=e[p[i]^1].t){
				a=min(a,e[p[i]].c-e[p[i]].f);
			}
			for(int i=t;i!=s;i=e[p[i]^1].t){
				e[p[i]].f+=a,e[p[i]^1].f-=a;
			}
			flow+=a;
			x=s;
		}
		f=1;
		for(int&i=cur[x];i;i=e[i].n)
			if(e[i].c>e[i].f&&d[x]==d[e[i].t]+1){
				f=0,p[x=e[i].t]=i; break;
			}
		if(f){
			if(!(--g[d[x]]))break;
			f=n-1;
			fore(i,x)f=min(f,d[e[i].t]);
			++g[d[x]=f+1];
			cur[x]=head[x];
			if(x!=s)x=e[p[x]^1].t;
		}
	}
	return flow; 
}

inline void clear(){
	memset(head,0,sizeof head);
	tot=1;
}

int n,m;
#define S n+m+1
#define T n+m+2

int c[MAXN];

int u[MAXN],v[MAXN],w[MAXN];

db sum;

inline void Init(){
	Scan(n),Scan(m);
	rep(i,1,n)Scan(c[i]);
	rep(i,1,m){
		Scan(u[i]),Scan(v[i]);
		Scan(w[i]);
	}
}

inline bool check(db x){
	clear();
	sum=0;
	rep(i,1,m){
		AddEdge(S,i+n,w[i]),sum+=w[i];
	}
	rep(i,1,n)AddEdge(i,T,x*c[i]);
	rep(i,1,m){
		AddEdge(i+n,u[i],inf);
		AddEdge(i+n,v[i],inf);
	}
	sum-=isap(S,T,T);
	return sum<eps;
}

inline void Solve(){
	db l=0,r=1e9;
	while(r-l>eps){
		db mid=(l+r)/2.;
		if(check(mid))r=mid;
		else l=mid;
	}
	printf("%.2f\n",l);
}

int main(){
	Init(); Solve(); return 0;
}

留坑QAQ

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define inf 0x7f7f7f7f
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

const int MAXN=50005;

struct edge{
	int t,n;
	edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

int sum[MAXN]={-1},dis[MAXN];

int n,p[MAXN],w[MAXN],mx[MAXN][2];

void dfs(int x){
	sum[x]=w[x];
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x]){
			p[y]=x,dfs(y);
			sum[x]+=sum[y];
			dis[x]+=sum[y]+dis[y];
			if(sum[y]>sum[mx[x][0]]){
				mx[x][1]=mx[x][0];
				mx[x][0]=y;
			}
			else if(sum[y]>sum[mx[x][1]]){
				mx[x][1]=y;
			}
		}
}

int find(int x,int s=0,int c=0){
	int res=dis[x]+s+c;
	if(mx[x][0]){
		int y=mx[x][0];
		int ns=s+c+dis[x]-dis[y]-sum[y];
		int nc=c+sum[x]-sum[y];
		int tmp=dis[y]+ns+nc;
		if(tmp<res){
			return find(y,ns,nc);
		}
	}
	return res;
}

bool flag[MAXN];

void remove(int x){
	int y=p[x]; 
	flag[x]= x==mx[y][0];
	if(flag[x])mx[y][0]=mx[y][1];
	int t=dis[x];
	while(y){
		t+=sum[x];
		dis[y]-=t;
		sum[y]-=sum[x];
		flag[y]= y==mx[p[y]][0];
		if(flag[y]){
			if(sum[mx[p[y]][1]]>sum[y]){
				mx[p[y]][0]=mx[p[y]][1];
			}
		}
		y=p[y];
	}
}

void recover(int x){
	int y=p[x];
	if(flag[x])mx[y][0]=x;
	int t=dis[x];
	while(y){
		t+=sum[x];
		dis[y]+=t;
		sum[y]+=sum[x];
		if(flag[y])mx[p[y]][0]=y;
		y=p[y];
	}
}

int rt,ans=inf;

void dp(int x){
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x]){
			remove(y);
			ans=min(ans,find(y)+find(rt));
			recover(y);
			dp(y);
		}
}

inline void Init(){
	Scan(n);
	for(int i=1,x,y;i<n;++i){
		Scan(x),Scan(y);
		AddEdge(x,y);
	}
	for(int i=1;i<=n;++i)Scan(w[i]);
	dfs(rt=1);
}

inline void Solve(){
	dp(rt);
	printf("%d\n",ans);
}

int main(){
	Init(); Solve(); return 0;
}

r5

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define DFT(a,n) fft(a,n,0)
#define IDFT(a,n) fft(a,n,1) 
#define rep(i,a,b) for(int i=a;i<b;++i)
typedef long long ll;
const int P=998244353;

inline ll qpow(ll x,int k){
	ll ans=1;
	for(;k;x=x*x%P,k>>=1)
		if(k&1)ans=ans*x%P;
	return ans; 
}

const int MAXN=(1<<18)+5;

int r[MAXN],w[2][MAXN],rn;

inline void init_fft(int n,int b){
	rn=qpow(n,P-2);
	int g=qpow(3,(P-1)/n);
	w[0][0]=w[0][n]=1;
	rep(i,1,n)w[0][i]=1ll*w[0][i-1]*g%P;
	rep(i,0,n+1)w[1][i]=w[0][n-i];
	rep(i,1,n){
		r[i]=(r[i>>1]>>1)|((i&1)<<(b-1));
	}
} 

inline void fft(int*a,int n,int t){
	rep(i,1,n)if(i<r[i])swap(a[i],a[r[i]]);
	for(int i=2;i<=n;i<<=1)
		for(int j=0;j<n;j+=i)
			for(int k=0;k<i>>1;++k){
				int v=1ll*a[(i>>1)+j+k]*w[t][n/i*k]%P;
				a[(i>>1)+j+k]=(a[j+k]+P-v)%P;
				a[j+k]=(a[j+k]+v)%P;
			}
	if(t)rep(i,0,n)a[i]=1ll*a[i]*rn%P;
}

int n,l,bit;

int a[MAXN],b[MAXN];

int fac[MAXN],inv[MAXN];

int x[MAXN],y[MAXN];

inline void Init(){
	Scan(n);
	rep(i,0,n+1)Scan(b[i]);
	l=n<<1|1,bit=1;
	while(1<<bit<l)++bit;
	l=1<<bit;
	init_fft(l,bit);
	fac[0]=1;
	rep(i,1,n+1)fac[i]=1ll*fac[i-1]*i%P;
	inv[0]=inv[1]=1;
	rep(i,2,n+1){
		int a=P/i,b=P%i;
		inv[i]=1ll*a*(P-inv[b])%P;
	}	
	rep(i,2,n+1)
		inv[i]=1ll*inv[i]*inv[i-1]%P;
}

inline void Solve(){
	rep(i,0,n+1){
		x[i]=1ll*fac[n-i]*b[n-i]%P;
		if((n-i)&1)if(x[i])x[i]=P-x[i];
	}
	rep(i,0,n+1)y[i]=inv[i];
	DFT(x,l),DFT(y,l);
	rep(i,0,l)x[i]=1ll*x[i]*y[i]%P;
	IDFT(x,l);
	rep(i,0,n+1){
		a[i]=1ll*inv[i]*x[n-i]%P;
		if(i&1)if(a[i])a[i]=P-a[i];
	}
	rep(i,0,n+1)printf("%d ",a[i]);
}

int main(){
	Init(); Solve(); return 0;
}

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=305;

int n,k;

int e[MAXN][MAXN];

int main(){
	Scan(n),Scan(k);
	rep(i,1,n+1)e[i][i]=1; 
	int m=n-k+1;
	rep(i,1,m+1)rep(j,i+1,m+1)
		e[i][j]=e[j][i]=1;
	rep(i,m+1,n+1)e[i][i-1]=e[i-1][i]=1;
	rep(i,1,n+1){
		rep(j,1,n+1)putchar(e[i][j]+48);
		puts("");
	}
	return 0;
}

留坑QAQ

UOJ Round#8

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lch x->l,l,mid
#define rch x->r,mid+1,r 
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

const int MAXN=2e5+5;

typedef struct node*star;

struct data{
	int l_iro,r_iro;
	int iro_cnt;
	data(int l_iro=0,int r_iro=0,int iro_cnt=0):
		l_iro(l_iro),r_iro(r_iro),iro_cnt(iro_cnt){}
};

inline data operator+(const data&a,const data&b){
	data c;
	c.l_iro=a.l_iro,c.r_iro=b.r_iro;
	c.iro_cnt=a.iro_cnt+b.iro_cnt;
	if(a.r_iro==b.l_iro)--c.iro_cnt;
	return c;
}

struct node{
	data d;
	star l,r;
}pool[MAXN<<4];

star tail=pool;

void build(int*a,star&x,int l,int r){
	x=tail++;
	if(l==r){
		x->d=data(a[l],a[l],1);
		return;
	}
	int mid=(l+r)>>1;
	build(a,lch),build(a,rch);
	x->d=x->l->d+x->r->d;
}

inline data query(star x,int l,int r,int ll,int rr){
	if(l==ll&&r==rr)return x->d;
	int mid=(l+r)>>1;
	if(rr<=mid)return query(lch,ll,rr);
	if(ll>mid) return query(rch,ll,rr);
	return query(lch,ll,mid)+query(rch,mid+1,rr); 
}

star rta,rtb;

int n,m,q,a[MAXN],b[MAXN];

int main(){
	Scan(n),Scan(m);
	for(int i=1;i<=n;++i)Scan(a[i]);
	for(int i=1;i<=n;++i)a[i+n]=a[i];
	build(a,rta,1,n<<1);
	for(int i=1;i<=m;++i)Scan(b[i]);
	for(int i=1;i<=m;++i)b[i+m]=b[i];
	build(b,rtb,1,m<<1);
	Scan(q);
	for(int i=1;i<=q;++i){
		int sx,sy,tx,ty;
		Scan(sx),Scan(sy),Scan(tx),Scan(ty);
		if(sx>tx)swap(sx,tx);
		if(sy>ty)swap(sy,ty);
		int t1=query(rta,1,n<<1,sx,tx).iro_cnt;
		t1=min(t1,query(rta,1,n<<1,tx,sx+n).iro_cnt);
		int t2=query(rtb,1,m<<1,sy,ty).iro_cnt;
		t2=min(t2,query(rtb,1,m<<1,ty,sy+m).iro_cnt);
		int ans=t1+t2-2;
		printf("%d\n",ans);
	}
	return 0;
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lch x->l,l,mid
#define rch x->r,mid+1,r 
#define LL long long
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

const int MAXN=2e5+5;

typedef struct node*star;

struct data{
	int min,max;
	data(int min=0,int max=0):
		min(min),max(max){}
};

inline data operator+(const data&a,const data&b){
	return data(min(a.min,b.min),max(a.max,b.max)); 
}

struct node{
	data d;
	bool rev;
	inline void rev_it(){
		d.min=100000-d.min;
		d.max=100000-d.max;
		swap(d.min,d.max);
		rev^=1;
	}
	inline void down(){
		if(!rev)return;
		l->rev_it(),r->rev_it();
		rev=0;
	}
	inline void updt(){
		d=l->d+r->d;
	}
	star l,r;
}pool[MAXN<<4];

star tail=pool;

void build(int*a,star&x,int l,int r){
	x=tail++;
	if(l==r){
		x->d=data(a[l],a[l]);
		return;
	}
	int mid=(l+r)>>1;
	build(a,lch),build(a,rch);
	x->updt();
}

LL ans;

inline LL calc(int a,int b,int c,int x,int y){
	return 1ll*a*x+1ll*b*y+1ll*c*x*y;
}

inline void query(star x,int l,int r,int ll,int rr,int a,int b,int c){
	if(ll>r||rr<l)return;
	if(l==r){
		ans=max(ans,calc(a,b,c,l,x->d.max));
		return;	
	}
	LL g=calc(a,b,c,min(r,rr),x->d.max);
	if(g<=ans)return;
	int mid=(l+r)>>1;
	x->down();
	LL g1=calc(a,b,c,min(mid,rr),x->l->d.max);
	LL g2=calc(a,b,c,min(r,rr),x->r->d.max);
	if(g1>g2)query(lch,ll,rr,a,b,c),query(rch,ll,rr,a,b,c);
	else  query(rch,ll,rr,a,b,c),query(lch,ll,rr,a,b,c);
}

int y[MAXN];

inline void modify(star x,int l,int r,int pos,int y){
	if(l==r){
		x->d=data(y,y);
		return;
	}
	int mid=(l+r)>>1;
	x->down();
	if(pos>mid)modify(rch,pos,y);
	else modify(lch,pos,y);
	x->updt();
}

inline void modify1(star x,int l,int r,int ll,int rr){
	if(ll<=l&&r<=rr)return x->rev_it();
	x->down();
	int mid=(l+r)>>1;
	if(ll<=mid)modify1(lch,ll,rr);
	if(rr>mid) modify1(rch,ll,rr);
	x->updt();
}

int n,m,q,x0;

const int P=998244353;

inline int rand_x(){
	return (x0=((1ll*x0*100000005%P+20150609)%P))/100;
}

star rt;

inline void Solve(){
	build(y,rt,1,n);
	for(int i=1;i<=m;++i){
		char c;while(c=g(),c<'A'||c>'Z');
		if(c=='C'){
			int x=rand_x()%n+1;
			int y1=rand_x()%100001;
			modify(rt,1,n,x,y1);
		}
		else if(c=='R'){
			int l=rand_x()%n+1;
			int r=rand_x()%n+1;
			if(l>r)swap(l,r);
			modify1(rt,1,n,l,r);
		}
		else{
			int l=rand_x()%n+1;
			int r=rand_x()%n+1;
			if(l>r)swap(l,r);
			int a,b,c;
			Scan(a),Scan(b),Scan(c);
			ans=-1ll<<60;
			query(rt,1,n,l,r,a,b,c);
			printf("%lld\n",ans);
		}
	}
}

int main(){
	Scan(n),Scan(m),Scan(x0);
	for(int i=1;i<=n;++i)
		y[i]=rand_x()%100001;
	Solve();
	return 0;
}

留坑QAQ