暑假牛客2024第1场

队名：智力不太好

瞎取个名字早早埋下了伏笔，，好久没打这么正式的比赛了，这一次真和队名呼应上了，两个签到都不是很顺利，第一签差点抬上树状数组，第二签wa了3发60min才通过 :(((((( 。然后150min推出了$A$ 的式子，写一手代码发现这玩意儿居然卡常（也有可能是我们的式子取模太多），最后全部预处理后一发wa，查了查发现没特判，第二发才过。后两人猛猛写 $I$ ，我在一边推 $B$，但是最后还是四题结束了，，有点可惜，赛后不久 $I$ 就出来了，$B$ 也推了出来。

A

题意：给出 $n,m,mod$ ，求符合以下要求的序列有多少个：一共有 $n$ 个数，每个数不超过 $2^m$ ，存在一个子序列所有数 $and$ 为1。

排除法。一共的序列种数为 $2^{nm}$ ，考虑不符合要求的排列：

若每个数的最后一位都是0，那么一定是不满足的。若存在某些数最后一位为1，那么：

这些数都不止一个1，否则本身就是1了；
这些数在相同的位上均含有1，否则全部 $and$ 起来前面的位就是0。

因此两重循环枚举：第一重枚举有 $i$ 个数结尾为1，第二重枚举这些数除了最后一位有 $x$ 位均为1。那么有：
$$
ans=2^{nm}-\sum_iC_n^i2^{(n-i)(m-1)}\sum_x C_{m-1}^x(2^{i}-1)^{m-i-x}
$$

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define fuck puts("fuck");
#define fi first
#define se second
#define int long long
template <typename T>inline void rd(T &x){
	T c=getchar(),tx=1;x=0;
	while(c<'0'||c>'9')	tx=c=='-'?-1:tx,c=getchar();
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=tx;
}
int n,m,mod;
int f[5010][5010],qp[25000010],g[5010][5010];
int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)	ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return ret;
}

void solve(){
	int ans=0;
	rd(n),rd(m),rd(mod);
	for(register int i=0;i<=max(n,m);++i){
		for(int j=0;j<=i;++j){
			if(!j)	f[i][j]=1;
			else	f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
		}
	}
	qp[0]=1;
	for(register int i=1;i<=n*m;++i)	qp[i]=1ll*qp[i-1]*2%mod;
	if(m==1){
		printf("%lld",(qp[n]+mod-1)%mod);
		return ;
	}
//	for(int i=0;i<=m;++i)	g[0][i]=1;	
	for(register int i=0;i<=n;++i){
		g[i][0]=1;
		for(register int j=1;j<=m;++j){
			g[i][j]=1ll*g[i][j-1]*(qp[i]-1+mod)%mod;
		}
	}
	for(register int i=0;i<=n;++i){
//		cout<<i<<endl;
		int tmp=0;
		for(register int j=1;j<=m-1;++j){
			tmp=1ll*(tmp+1ll*f[m-1][j]*g[i][m-1-j]%mod*qp[(n-i)*(m-1)]%mod)%mod;
		}
		tmp=1ll*tmp*f[n][i]%mod;
		ans=(ans+tmp)%mod;
	}
	ans=(qp[n*m]-ans+mod)%mod;
	printf("%lld",ans);
}
signed main(){
	solve();
}

B

题意：同 $A$ ，只不过合法序列的要求改为了至少有两个 $and$ 为1的子序列。

同样用排除法。通过 $A$ 题可得到全部排列数，再排除只有一个合法序列的排列数即可。

注意到若某个排列只有一个合法排列数，那么一定是所有末尾为1的数 $and$ 起来为1，且不存在任一个子集 $and$ 也为1。

那么必须满足：对于 $i$ 个末尾为1的数，至少 $i$ 位上有 $i-1$ 个1，且这 $i$ 位上每个数都至少出现一个0。

那么可以考虑枚举有多少位有 $i-1$ 个1，枚举范围是 $[i,m]$ 。对于其他位，只要满足少于 $i-1$ 个1即可。

公式即为：
$$
ans=ans_A-\sum_iC_n^i2^{(m-1)(n-i)}i!\sum_xC_{m-1}^xdp[x][i]\times (2^i-1-i)^{m-1-x}
$$
关于卡常，，，火车头狠狠冲！

PS：在计算多少位有 $i-1$ 个1时，相当于转化为把 $x$ 个不同小球放在 $i$ 个不同盒子里，且每个盒子至少放一个球。用递推实现。$dp[i][j]=dp[i-1][j]\times j+dp[i-1][j-1],\ ans[i][j]=dp[i][j]\times j!$ 。

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

using namespace std;
#define LL long long
#define fuck puts("fuck");
#define fi first
#define se second

template <typename T>inline void rd(T &x){
	T c=getchar(),tx=1;x=0;
	while(c<'0'||c>'9')	tx=c=='-'?-1:tx,c=getchar();
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=tx;
}
int n,m,mod;
int f[5010][5010],qp[25000010],g[5010][5010],h[5010][5010],s[5010][5010],w[5010][5010],fac[5010];
int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)	ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return ret;
}

void solve(){
	int ans=0,ans2=0;
	rd(n),rd(m),rd(mod);
	for(register int i=0;i<=max(n,m);++i){
		for(int j=0;j<=i;++j){
			if(!j)	f[i][j]=1;
			else	f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
		}
	}
	qp[0]=1;
	for(register int i=1;i<=n*m;++i)	qp[i]=1ll*qp[i-1]*2%mod;
	if(m==1){
		printf("%lld",(qp[n]-n-1+mod)%mod);
		return ;
	}
	for(register int i=0;i<=n;++i){
		g[i][0]=1;
		for(register int j=1;j<=m;++j){
			g[i][j]=1ll*g[i][j-1]*(qp[i]-1+mod)%mod;
		}
	}
	fac[0]=1;
	for(int i=1;i<=n;++i)	fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=1;i<=m;++i){
		h[i][1]=s[i][1]=1;
		for(int j=2;j<=i;++j){
			h[i][j]=(h[i-1][j-1]+1ll*j*h[i-1][j]%mod)%mod;
		}
	}
	for(int i=1;i<=n;++i){
		w[i][0]=1;
		for(int j=1;j<=m;++j){
			w[i][j]=1ll*w[i][j-1]*(qp[i]-1-i+mod)%mod;
		}
	}
	for(int i=0;i<=n;++i){
		int tmp=0;
		for(int j=1;j<=m-1;++j){
			tmp=1ll*(tmp+1ll*f[m-1][j]*g[i][m-1-j]%mod*qp[(n-i)*(m-1)]%mod)%mod;
		}
		tmp=1ll*tmp*f[n][i]%mod;
		ans=(ans+tmp)%mod;
	}
	ans=(qp[n*m]-ans+mod)%mod;
	for(int x=1;x<=n;++x){
		int tmp=0;
		for(int i=x;i<=m-1;++i){
			tmp=(tmp+1ll*f[m-1][i]%mod*h[i][x]%mod*w[x][m-1-i]%mod)%mod;
		}
		tmp=1ll*tmp*fac[x]%mod*f[n][x]%mod*qp[(m-1)*(n-x)]%mod;
		ans2=(ans2+tmp)%mod;
	}
	printf("%d",(ans-ans2+mod)%mod);
}
signed main(){
	solve();
}

C

题意：给定长为 $n$ 的数组 $a$ ，每次操作：先从后往前删除 $t$ 个数，然后在末尾加上数 $v$ 。每次操作后求所有后缀和之和。

把后缀转化为前缀，计算贡献即可。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define fuck puts("fuck");
#define fi first
#define se second
#define int long long
template <typename T>inline void rd(T &x){
	T c=getchar(),tx=1;x=0;
	while(c<'0'||c>'9')	tx=c=='-'?-1:tx,c=getchar();
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=tx;
}
const int N=5e5+10,mod=1e9+7;
LL s[N],g[N];
int q,cnt;
void solve(){
	rd(q);
	while(q--){
		LL t,v;
		rd(t),rd(v);
		cnt-=t-1;
		s[cnt]=(s[cnt-1]+v)%mod;
		g[cnt]=(g[cnt-1]+s[cnt])%mod;
		printf("%lld\n",(cnt*s[cnt]%mod+mod-g[cnt-1])%mod);
	}
}
signed main(){
	solve();
}

D

题意：同 $C$ ，只不过每次操作后求后缀和后21位的异或值。

转化一下即求 $\oplus_{i}\ pre[n]-pre[i]$ 。因为是异或运算，因此分别考虑每一位。若第 $b$ 位是1，那么有：
$$
2^b\leq (pre[n]-pre[i])%2^{b+1}\leq 2^{b+1}
$$
移项可得：
$$
2^b-pre[n]\leq-pre[i]\leq 2^{b+1}-pre[n]
$$
或者
$$
0\leq-pre[i]\leq 2^{b+1}-pre[n]\ \ ,\ \ 2^b-pre[n]\leq-pre[i]\leq 2^{b+1}
$$
那么考虑对每一位开一个树状数组，当统计到某一位的异或值时，只需要计算查询区间内元素的数量是奇还是偶。

# include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 22, M = 500010, mod = 2097152;

int tr[N][1 << N], s[M];
int n, ed;

int lowbit(int x)
{
	return x & -x;
}

void add(int x, int d)
{
	for(int i = 0; i < 21; i ++)
	{
		int p = 1 << i + 1;
		for(int j = (p - x % p) % p + 1; j <= 1 << i + 1; j += lowbit(j))
			tr[i][j] += d;
	}
}

int sum(int k, int x)
{
	int ret = 0;
	for(int i = ++x; i; i -= lowbit(i))
		ret += tr[k][i];
	return ret;
}

int main()
{
	scanf("%d", &n);
	while(n --)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		while(x --) add(s[ed - 1], -1), -- ed;
		s[ed + 1] = (s[ed] + y) % mod, ++ ed;
		add(s[ed - 1], 1);

		int ret = 0;

		for(int i = 0; i < 21; i ++)
		{
			int p = 1 << i + 1;
			int l = 1 << i, r = p - 1;
			l = (l - s[ed] % p + p) % p;
			r = (r - s[ed] % p + p) % p;
			int res = 0; 
			if(l <= r) res = sum(i, r) - sum(i, l - 1);
			else res = sum(i, p - 1) - sum(i, l - 1) + sum(i, r);
			ret |= (res&1) << i;
		}
	
		printf("%d\n", ret);
	}
	return 0;
}

H

题意：不知道欸，队友写的，铁签，但是我们智力不太好

# include<bits/stdc++.h>

using namespace std;
typedef pair<int,int>PII;
const int N = 100010;
int n, m;
unordered_set<string>S, T;

map<string, PII>mp;
set<PII>W, M, D;
vector<PII>Q1, Q2;
PII Q, P;

bool cmp(PII x, PII y)
{
	if(x.first > y.first) return true;
	else if(x.first < y.first) return false;
	
	return x.second < y.second;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	
	int cnt1 = n, cnt2 = m;
	for(int i = 1; i <= n; i ++)
	{
		string s;
		int x, y;
		cin >> s >> x >> y;
		if(s == "lzr010506") P = {x, y};
		S.insert(s);	
		W.insert({x, y});
		mp[s] = {x, y};
	}
	
	cin >> m;
	for(int i = 1; i <= m; i ++)
	{
		string s;
		int x, y;
		cin >> s >> x >> y;
		
		if(s == "lzr010506") Q = {x, y};
		
		if(S.count(s))
		{
			D.insert({x, y});
			W.erase(W.find({mp[s].first, mp[s].second}));
		}
		else M.insert({x, y});
	}
	
	for(auto c : W) Q1.push_back(c);
	for(auto c : M) Q2.push_back(c);
	Q1.push_back(P), Q2.push_back(Q);
	sort(Q1.begin(), Q1.end(), cmp), sort(Q2.begin(), Q2.end(), cmp);
	
	
	int rank1, rank2;
	for(int i = 0; i < Q1.size(); i ++)
		if(Q1[i] == P)
		{
			rank1 = i + 1;
			break;
		}
	for(int i = 0; i < Q2.size(); i ++)
		if(Q2[i] == Q)
		{
			rank2 = i + 1;
			break;
		}		

	cout << min(rank1, rank2) << endl;
}

I

题意：有一个 $n\times m$ 的镜子阵，镜子有 /—|四种，符合光学反射规律，问从某一点开始发射一束光线，这束光会经过多少不同的镜子。

根据光路可逆，一束从外部射进去的光一定会从某一个口射出去，外部光没经过的地方射一束光一定会死循环，也就是所有的光路是很多条链和很多个环，彼此不相交。但是代码太难写了。

# include <bits/stdc++.h>

using namespace std;
pair<int,int>PII;
const int N = 1010;
unordered_set<int>S;
int n, m, q, cnt;
char g[N][N];
int f[N][N][4];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(int row, int col, int dir, int num, bool flag)
{
	int nrow = row + dx[dir];
	int ncol = col + dy[dir];
	if(nrow < 1 || nrow > n || ncol < 1 || ncol > m) return;
	//if(nrow == 1 && ncol == 2 && dir == 0)
	//cout << row << ' ' << col << ' ' << num << ' ' << nrow <<' ' << ncol << ' ' << g[nrow][ncol] << endl;

	if(dir == 0)
	{
		int drow = nrow , dcol = ncol;
		f[drow][dcol][1] = num;
	}
	else if(dir == 1)
	{
		int drow = nrow, dcol = ncol;
		f[drow][dcol][0] = num;
	}
	else if(dir == 2)		
	{
		int drow = nrow, dcol = ncol;
		f[drow][dcol][3] = num;
	}
	else
	{
		int drow = nrow, dcol = ncol;
		f[drow][dcol][2] = num;
	}
	
	
	if(g[nrow][ncol] == '\\')
	{
		if(!flag)
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				num ++;
				S.insert(hash);
			}
		}
		
		if(dir == 0)
			dfs(nrow, ncol, 2, num, flag);
		else if(dir == 1)
			dfs(nrow, ncol, 3, num, flag);
		else if(dir == 2)
			dfs(nrow, ncol, 0, num, flag);
		else dfs(nrow, ncol, 1, num, flag);	
	}
	else if(g[nrow][ncol] == '/')
	{
		if(!flag)
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				num ++;
				S.insert(hash);
			}
		}
		if(dir == 0)
			dfs(nrow, ncol, 3, num, flag);
		else if(dir == 1)
			dfs(nrow, ncol, 2, num, flag);
		else if(dir == 2)
			dfs(nrow, ncol, 1, num, flag);
		else dfs(nrow, ncol, 0, num, flag);	
	}
	else if(g[nrow][ncol] == '|')
	{
		if(dir == 0)
			dfs(nrow, ncol, 0, num, flag);
		else if(dir == 1)
			dfs(nrow, ncol, 1, num, flag);
		else if(dir == 2)
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				num ++;
				S.insert(hash);
			}
			dfs(nrow, ncol, 3, num, 1);
		}
		else 
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				num ++;
				S.insert(hash);
			}
			dfs(nrow, ncol, 2, num, 1);	
		}
	}
	else
	{
		if(dir == 0)
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				num ++;
				S.insert(hash);
			}
			dfs(nrow, ncol, 1, num, 1);
		}
		else if(dir == 1)
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				num ++;
				S.insert(hash);
			}
			dfs(nrow, ncol, 0, num, 1);
		}
		else if(dir == 2)
			dfs(nrow, ncol, 2, num, flag);
		else dfs(nrow, ncol, 3, num, flag);	
	}	
}

void dfs1(int x, int y, int tx, int ty, int dir, int ddir)
{
	int nrow = x + dx[dir];
	int ncol = y + dy[dir];
	//cout << nrow << ' ' << ncol << ' ' << cnt << endl;
	if(x == tx && y == ty && dir == ddir && cnt) 
	{
		f[x][y][dir] = cnt ;
		return;
	}
	
	
	if(g[nrow][ncol] == '\\')
	{
		int hash = nrow * N + ncol;
		if(!S.count(hash))
		{
			cnt ++;
			S.insert(hash);
		}
		if(dir == 0)
			dfs1(nrow, ncol, tx, ty, 2, ddir);
		else if(dir == 1)
			dfs1(nrow, ncol, tx, ty, 3, ddir);
		else if(dir == 2)
			dfs1(nrow, ncol, tx, ty, 0, ddir);
		else dfs1(nrow, ncol, tx, ty, 1, ddir);	
	}
	else if(g[nrow][ncol] == '/')
	{
		int hash = nrow * N + ncol;
		if(!S.count(hash))
		{
			cnt ++;
			S.insert(hash);
		}
		if(dir == 0)
			dfs1(nrow, ncol, tx, ty, 3, ddir);
		else if(dir == 1)
			dfs1(nrow, ncol, tx, ty, 2, ddir);
		else if(dir == 2)
			dfs1(nrow, ncol, tx, ty, 1, ddir);
		else dfs1(nrow, ncol, tx, ty, 0, ddir);	
	}
	else if(g[nrow][ncol] == '|')
	{
		if(dir == 0)
			dfs1(nrow, ncol, tx, ty, 0, ddir);
		else if(dir == 1)
			dfs1(nrow, ncol, tx, ty, 1, ddir);
		else if(dir == 2)
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				cnt ++;
				S.insert(hash);
			}
			dfs1(nrow, ncol, tx, ty, 3, ddir);
		}
		else 
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				cnt ++;
				S.insert(hash);
			}
			dfs1(nrow, ncol, tx, ty, 2, ddir);	
		}
	}
	else
	{
		if(dir == 0)
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				cnt ++;
				S.insert(hash);
			}
			dfs1(nrow, ncol, tx, ty, 1, ddir);
		}
		else if(dir == 1)
		{
			int hash = nrow * N + ncol;
			if(!S.count(hash))
			{
				cnt ++;
				S.insert(hash);
			}
			dfs1(nrow, ncol, tx, ty, 0, ddir);
		}
		else if(dir == 2)
			dfs1(nrow, ncol, tx, ty, 2, ddir);
		else dfs1(nrow, ncol, tx, ty, 3, ddir);	
	}
	
    if(dir == 0) f[nrow][ncol][1] = cnt;
    else if(dir == 1) f[nrow][ncol][0] = cnt;
    else if(dir == 2) f[nrow][ncol][3] = cnt;
    else f[nrow][ncol][2] = cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	
	cin >> n >> m;
	memset(f, -1, sizeof f);
	for(int i = 1; i <= n; i ++)
		cin >> g[i] + 1;

	for(int i = 1; i <= m; i ++) 
	{
		S.clear();
		dfs(n + 1, i, 0, 0, 0);
	}
	for(int i = 1; i <= m; i ++) 
	{
		S.clear();
		dfs(0, i, 1, 0, 0);
	}
	
	for(int i = 1; i <= n; i ++) 
	{
		S.clear();
		dfs(i, 0, 3, 0, 0);
	}
	for(int i = 1; i <= n; i ++) 
	{
		S.clear();
		dfs(i, m + 1, 2, 0, 0);
	}

	cin >> q;
	while(q --)
	{
		string s;
		int x, y;
		cin >> x >> y >> s;
		cnt = 0;
		S.clear();
		if(s == "above") 
		{
			if(~f[x][y][0])
				cout << f[x][y][0] << endl;
			else 
			{
				dfs1(x, y, x, y, 0, 0);
				cout << cnt << endl;
			}
		}
		else if(s == "below") 
		{
			if(~f[x][y][1])
				cout << f[x][y][1] << endl;
			else 
			{
				dfs1(x, y, x, y, 1, 1);
				cout << cnt << endl;
			}
		}
		else if(s == "left") 
		{
			if(~f[x][y][2])
				cout << f[x][y][2] << endl;
			else 
			{
				dfs1(x, y, x, y, 2, 2);
				cout << cnt << endl;
			}
		}
		else
		{
			if(~f[x][y][3])
				cout << f[x][y][3] << endl;
			else 
			{
				dfs1(x, y, x, y, 3, 3);
				cout << cnt << endl;
			}
		}
	}
	return 0;
	
}

J

题意：给一个 $n\times m$ 的二维矩形区域和一个长为k的指令序列，每条指令由 $LRUD$ 中的一个字符 $c$ 和一个整数 $t$ 构成，表示沿着 $c$ 方向走 $t$ 步，其中 $LRUD$ 分别表示向左/右/上/下走一步，如果要走出矩形区域就停着不动。有 $q$ 个询问，每个询问给定 $x,y,l,r$，表示从 $(x,y)$ 出发，依次按照第$l,l+1,l+2,…,r$ 条指令移动，问最后会停在哪个位置以及实际走了多少步。

可以将两个维度分开处理。以 $x$ 坐标为例。

需要倍增预处理出从每条指令出发，撞 $2^i$ 次墙时是在哪条指令，即 $f[i][j]=f[f[i][j-1]][j-1]$ 。当然首先需要预处理出每一个 $f[i][0]$ ，可通过 $st$ 表结合二分查找。

在对每一条查询时，首先找到第一次撞墙的位置，然后倍增找到最后一次撞墙位置，再用前缀和找到停下的位置。

细节很多，码量挺大，但是队友是万能的:)

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define fuck puts("fuck");
#define fi first
#define se second
#define int long long
template <typename T>inline void rd(T &x){
	T c=getchar(),tx=1;x=0;
	while(c<'0'||c>'9')	tx=c=='-'?-1:tx,c=getchar();
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=tx;
}

const int N=1e5+10;
int k,q,t;
int lg[N];
array<int,2> n,d[128],rt[N],a[N],sum[N],smn[N][20],smx[N][20],f[N][20],fr[N][20];

void st_pre(){
	for(int h=0;h<2;++h){
		for(int i=1;i<=k;++i)	smx[i][0][h]=smn[i][0][h]=sum[i][h];
		for(int j=1;j<t;++j)
			for(int i=1;i<=k-(1<<j)+1;++i){
				smx[i][j][h]=max(smx[i][j-1][h],smx[i+(1<<(j-1))][j-1][h]);	
				smn[i][j][h]=min(smn[i][j-1][h],smn[i+(1<<(j-1))][j-1][h]);	
			}
	}
	
}

int query(int l,int r,int op,int h){
	int j=lg[r-l+1];
	if(op)	return max(smx[l][j][h],smx[r-(1<<j)+1][j][h]); 
	return min(smn[l][j][h],smn[r-(1<<j)+1][j][h]); 
}

bool pd(int pos,int x,int cc,int op,int h){
	if(op)	return (query(pos,x,1,h)>cc);
	return (query(pos,x,0,h)<cc);
}

int wall(int pos,int cc,int op,int h){
	int l=pos,r=k+1;
	while(l<r){
		int mid=l+r>>1;
		if(pd(pos,mid,cc,op,h))	r=mid;
		else l=mid+1;
	}
	return l;
}
void solve(){
	d['L']={-1,0},d['R']={1,0},d['U']={0,1},d['D']={0,-1};
	rd(n[0]),rd(n[1]),rd(k),rd(q);
	for(int i=2;i<=k;++i)	lg[i]=lg[i>>1]+1;
	t=lg[k]+1;
	for(int i=1;i<=k;++i){
		char s;	int x;
		cin>>s;rd(x);
		for(int h=0;h<2;++h){
			a[i][h]=x*d[s][h];
			sum[i][h]=sum[i-1][h]+a[i][h];
			rt[i][h]=rt[i-1][h]+abs(a[i][h]);
		}
	}
	st_pre();
	for(int h=0;h<2;++h){
		for(int j=0;j<=t;++j)	f[k+1][j][h]=k+1;
		for(int i=1;i<=k;++i){
			if(a[i][h]==0)			f[i][0][h]=k+1;
			else if(a[i][h]>0){
				int rp,lp;
				rp=wall(i,sum[i][h],1,h);
				lp=wall(i,sum[i][h]-n[h],0,h);
				if(rp<lp){
					f[i][0][h]=rp;
					fr[i][0][h]=rt[rp][h]-rt[i][h]-(sum[rp][h]-sum[i][h]);
				}
				else{
					f[i][0][h]=lp;
					fr[i][0][h]=rt[lp][h]-rt[i][h]+(sum[lp][h]-sum[i][h]+n[h]);
				}
			}
			else{
				int rp,lp;
				rp=wall(i,sum[i][h]+n[h],1,h);
				lp=wall(i,sum[i][h],0,h);
				if(rp<lp){
					f[i][0][h]=rp;
					fr[i][0][h]=rt[rp][h]-rt[i][h]-(sum[rp][h]-sum[i][h]-n[h]);
				}
				else{
					f[i][0][h]=lp;
					fr[i][0][h]=rt[lp][h]-rt[i][h]+(sum[lp][h]-sum[i][h]);
				}
			}
		}
		for(int j=1;j<=t;++j){
			for(int i=1;i<=k;++i){
				f[i][j][h]=f[f[i][j-1][h]][j-1][h];
				fr[i][j][h]=fr[i][j-1][h]+fr[f[i][j-1][h]][j-1][h];
			}
		}
	}
	while(q--){
		array<int,2> p,ep;
		int l,r,ans=0;
		rd(p[0]),rd(p[1]),rd(l),rd(r);
		for(int h=0;h<2;++h){
			int x,tmp=0,lp,rp;
			rp=wall(l,sum[l-1][h]+n[h]-p[h],1,h);
			lp=wall(l,sum[l-1][h]-p[h],0,h);
			x=min(rp,lp);
			if(x>r){
				ans+=rt[r][h]-rt[l-1][h];
				ep[h]=p[h]+sum[r][h]-sum[l-1][h];
				continue;
			}
			if(rp<lp)	tmp+=rt[x][h]-rt[l-1][h]-(sum[x][h]-sum[l-1][h]-n[h]+p[h]);
			else tmp+=rt[x][h]-rt[l-1][h]+(sum[x][h]-sum[l-1][h]+p[h]);
			for(int j=t;j>=0;--j){
				if(f[x][j][h]<=r){
					tmp+=fr[x][j][h];
					x=f[x][j][h];
				}
			}	
			ep[h]=(a[x][h]>0?n[h]:0)+sum[r][h]-sum[x][h];
			tmp+=rt[r][h]-rt[x][h];
			ans+=tmp;
		}
		printf("%lld %lld %lld\n",ep[0],ep[1],ans);
	}
}

signed main(){
	solve();
}