2024牛客暑期多校训练营1

难度梯度 CH A BDI FJ EG K

A A Bit Common

题意

有一个长度为 \(n\) 的序列，元素均在 \([0,2^m)\)。

问有多少个这样的序列满足条件：存在一个非空子序列的按位与为 \(1\)。

答案对 \(q\) 取模。

解题思路

考虑到条件中是子序列的按位与为 \(1\)，

我们可以枚举存在长度为 \(i\) \((1\le i\le n)\) 的子序列，按位与为 \(1\)，

那么首先需要在 \(n\) 个位置选 \(i\) 个出来放这个子序列，然后剩下 \(n-i\) 个位置则放其他数，

并且要满足这 \(n-i\) 个数的按位与不为 \(1\)，若要按位与不为 \(1\)，则二进制最低位全为 \(0\) 即可满足。

这样的数有 \(2^{m-1}\) 种，因为有 \(n-i\) 个数，所以一共有 \(2^{(m-1)*(n-i)}\) 种放置方案。

接下来要考虑长度 \(i\) 的子序列的按位与为 \(1\)，则二进制最低位一定要为 \(1\)。

其次就是按位与之后的其他位要为 \(0\)，即至少有 \(1\) 位数字该二进制为 \(0\)。

如果二进制除了最低位只有 \(1\) 位，那么方案数是 \(C_i^1+C_i^2+…+C_i^i=2^i-1\)

因为二进制除了最低位有 \(m\) 位，所以方案数为 \((2^i-1)^{m-1}\)

最终答案为 \(\sum_{i=1}^nC_n^i*(2^i-1)^{m-1}*2^{(m-1)*(n-i)} \mod q\)

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 c[5005][5005];
int p;
i64 qpow(i64 a, i64 b, i64 res = 1) {
    res %= p;
    while (b) {
        if (b & 1) {
            res = res * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m >> p;
    c[0][0] = 1 % p;
    for (int i = 1 ; i <= 5000 ; i++) {
        c[i][0] = 1 % p;
        for (int j = 0 ; j <= i ; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;
        }
    }
    i64 ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        i64 res = qpow((qpow(2, i) - 1 + p) % p, m - 1) * c[n][i] % p * qpow(2, (m - 1) * (n - i)) % p;
        ans = (ans + res) % p;
    }
    cout << ans << "\n";
    return 0;
}

B A Bit More Common

题意

有一个长度为 \(n\) 的序列，元素均在 \([0,2^m)\)。

问有多少个这样的序列满足条件：存在两个非空子序列的按位与为 \(1\)。

答案对 \(q\) 取模。

解题思路

这是 \(A\) 题的加强版，\(A\) 题的答案是 \(\ge1\) 的子序列，然而这道题的答案是 \(\ge2\) 的子序列。

那么我们是不是可以得出结论 \((\ge2)=(\ge1)-(=1)\)。

所以我们只需要求出 \((=1)\) 就好了。

我们可以想到我们选择长度为 \(i\) 的子序列按位与为 \(1\)，当这 \(i\) 个数少了任意一个数，都可以使按位与不为 \(1\)，那么有且仅有存在一个长度为 \(i\) 的子序列满足按位与为 \(1\)。可以反证法证明，如果去掉一个数还能使按位与为 \(1\)，那就至少存在 \(2\) 个非空子序列的按位与为 \(1\) 了。

接下来考虑这种数的性质，一定是在 \(i\) 个数中至少存在一位，二进制只有这个数是 \(0\)，其他数都是 \(1\) 的情况。

我们把这种二进制位叫做特殊位。

那么我们定义 \(dp_{n,m}\) 为 \(n\) 个数都存在特殊位且有 \(m\) 个特殊位。

① \((n-1,m-1)->(n,m)\) 在新增一个数的基础上，特殊位数量多了一个，那么这个特殊位一定是给新增的这个数，然后新增的数的位置有 \(n\) 种选择，贡献 \(n*(n-1,m-1)\)。

② \((n-1,m)->(n,m)\) 在新增一个数的基础上，特殊位数量不变，这是不可能的情况，我们的要求是每个数都至少要有一个特殊位。

③ \((n,m-1)->(n,m)\) 在数的数量不变的基础上，特殊位数量多了一个，那么这个特殊位可以给任何一个数，贡献 \(n*(n,m)\)

最终转移方程为 \(dp_{i,j}=i*(dp_{i-1,j-1}+dp_{i,j-1})\)

初始状态 \(dp_{0,0}=1\)

那么如果子序列长度为 \(i\) 且有 \(j\) 个特殊位，那么说明剩下 \(m-1-j\) 个位至少存在 \(2\) 个数为 \(0\)，

所以 \(C_i^2+C_i^3+…+C_i^i=2^i-C_i^0-C_i^1=2^i-i-1\)。

那么此时的贡献是 \(C_{m-1}^j*dp_{i,j}*(2^i-i-1)^{m-1-j}\)。

这里我们可以知道 \(i\le j\le m-1\)，因为每个数都至少存在一个特殊位，所以特殊位的数量要 \(\ge\) 数的数量。

当 \(i=1\) 不能通过本式子直接计算，因为要求 \(m-1-j\) 个二进制位至少存在 \(2\) 个数为 \(0\)，

但是现在只有一个数，所以这个数的二进制最低位一定是 \(1\)，其他位一定是 \(0\)

那么 \(i=1\) 的贡献为 \(C_n^1*2^{(n-1)(m-1)}\)

然后我们有 \((=1)=C_n^1*2^{(n-1)(m-1)}+\sum_{i=2}^nC_n^i*(\sum_{j=i}^{m-1}C_{m-1}^j*dp_{i,j}*(2^i-i-1)^{m-1-t})\)

那么 \((\ge2)=(\ge1)-(=1)=\sum_{i=1}^nC_n^i*(2^i-1)^{m-1}*2^{(m-1)*(n-i)}-(C_n^1*2^{(n-1)(m-1)}+\sum_{i=2}^nC_n^i*(\sum_{j=i}^{m-1}C_{m-1}^j*dp_{i,j}*(2^i-i-1)^{m-1-j}))\)

本题的答案为 \((\ge2)\mod q\)

使用快速幂可以做到时间复杂度 \((n*m*\log V)\)

但是常数特别大，考虑不使用快速幂，去掉 \(\log V\)。

对于 \(2^i\)，我们可以预处理 \(2\) 的 \(0\) 次幂到 \(2\) 的 \(5000*5000\) 次幂。

对于 \((2^i-i-1)^{(m-1-j)}\)，我们可以发现对于每个 \(i\)，变化的是 \(m-1-j\) ，而且 \(j\) 越大，\(m-1-j\) 越小。

所以我们可以从大到小枚举 \(j\)，进而实现 \(O(1)\) 的转移。

取模次数过多也会增大常数，可以对加法和减法进行优化，或者使用快速取模算法优化。

最终优化后时间复杂度为 \(O(n*m)\)。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 c[5005][5005], dp[5005][5005];
i64 p2[5005 * 5005];
int p;
i64 qpow(i64 a, i64 b, i64 res = 1) {
    res %= p;
    while (b) {
        if (b & 1) {
            res = res * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
i64 add(i64 x, i64 y) {
    x += y;
    if (x >= p) {
        x -= p;
    }
    return x;
}
i64 sub(i64 x, i64 y) {
    x -= y;
    if (x < 0) {
        x += p;
    }
    return x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m >> p;
    c[0][0] = 1;
    p2[0] = 1;
    for (int i = 1 ; i <= 5000 * 5000 ; i++) {
        p2[i] = p2[i - 1] * 2 % p;
    }
    for (int i = 1 ; i <= 5000 ; i++) {
        c[i][0] = 1;
        for (int j = 0 ; j <= i ; j++) {
            c[i][j] = add(c[i - 1][j - 1], c[i - 1][j]);
        }
    }
    dp[0][0] = 1;
    for (int i = 1 ; i <= 5000 ; i++) {
        for (int j = 1 ; j <= 5000 ; j++) {
            dp[i][j] = 1LL * i * add(dp[i][j - 1], dp[i - 1][j - 1]) % p;
        }
    }
    i64 ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        i64 res = qpow((p2[i] - 1 + p) % p, m - 1) * c[n][i] % p * p2[(m - 1) * (n - i)] % p;
        ans = add(ans, res);
    }
    ans = sub(ans, n * p2[(n - 1) * (m - 1)] % p);
    for (int i = 2 ; i <= n ; i++) {
        i64 res = 0, temp = 1;
        for (int j = m - 1 ; j >= i ; j--) {
            res = add(res, c[m - 1][j] * dp[i][j] % p * temp % p);
            temp = temp * sub(p2[i], i + 1) % p;
        }
        ans = sub(ans, c[n][i] * p2[(n - i) * (m - 1)] % p * res % p);
    }
    cout << ans << "\n";
    return 0;
}

C Sum of Suffix Sums

题意

一个空数组，需要进行 \(q\) 次操作。

每次操作如下： - 有两个非负整数 \(t,v\)，首先从数组的末尾删去 \(t\) 个数，然后再将 \(v\) 插入到数组的末尾。

假设 \(n\) 为当前数组的大小。

令 \(s_i=\sum_{j=i}^na_j,ans=\sum_{i=1}^ns_i\)

请你输出每次操作后的 \(ans\)。

解题思路

可以考虑到 \(ans\) 的定义，其实可以写成 \(ans=\sum_{i=1}^ni*a_i\)。

那么已知，如果是删掉数组末尾的一位，\(ans\) 减少 \(n*a_n\)，

如果是将 \(v\) 插入到数组末尾，\(ans\) 增加 \((n+1)*v\)。

这个贡献转移是 \(O(1)\) 的，

因为最多 \(500000\) 次操作，也就是说 \(500000\) 次插入，那么删除也不超过 \(500000\) 次。

我们暴力插入和删除，然后 \(O(1)\) 求贡献即可。

总时间复杂度 \(O(q)\)

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 P = 1000000007;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a;
    i64 ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        int t, v;
        cin >> t >> v;
        while (t--) {
            ans = (ans - (i64) a.size() * a.back() % P + P) % P;
            a.pop_back();
        }
        a.push_back(v);
        ans = (ans + (i64) a.size() * a.back() % P) % P;
        cout << ans << "\n";
    }
    return 0;
}

D XOR of Suffix Sums

题意

一个空数组，需要进行 \(q\) 次操作。

每次操作如下：

有两个非负整数 \(t,v\)，首先从数组的末尾删去 \(t\) 个数，然后再将 \(v\) 插入到数组的末尾。

假设 \(n\) 为当前数组的大小。

令 \(s_i=\sum_{j=i}^na_j,ans=s_1\oplus s_2\oplus s_3\oplus…\oplus s_n\)

请你输出每次操作后的 \(ans\mod 2097152\)。

解题思路

可以看到模数 \(2097152=2^{21}\)，由于看到异或运算，我们考虑到拆位。

我们定义前缀和 \(p_i=a_1+a_2+…+a_i\)，

那么 \(s_i=p_n-p_{i-1}\)，

因为最终是异或和，所以我们二进制拆位，通过每一位 \(1\) 的个数进行计算答案。

如果二进制第 \(i\) 位的数量为偶数，那么答案的这一位为 \(0\)，否则为 \(1\)。

因为模数是 \(2^{21}\) 所以我们只需要看二进制前 \(21\) 位即可。

当考虑二进制第 \(i\) 位的时候，二进制第 \(>i\) 位的 \(0/1\) 都对我们没有影响，

当二进制第 \(i\) 位为 \(1\) 时，有 \((p_n-x)\mod 2^{21}\) 的第 \(i\) 位为 \(1\)，则 \((p_n-x)\mod 2^{i+1}\ge2^i\)

对 \(x\mod 2^i\) 相当于把 \(x\) 第 \(i\) 位的高位全部置 \(0\)，只考虑 \(\le i\) 的位。

简单的说，那么问题转换成了 \((p_n-x)\mod 2^{i+1}\ge2^i\)，求 \(x\) 的种数即可。

接下来我们对 \((p_n-x)\mod 2^{i+1}\ge2^i\) 进行讨论：

假定 \(p_n,x<2^(i+1)\)

因为要 \(\ge2^i\)，所以我们对 \(p_n\) 和 \(2^i\) 的大小关系进行讨论。

① 当 \(p_n\ge2^i\)，有一种是直接相减就 \(\ge2^i\)，此时不等式可以写成 \(p_n-x\ge2^i\)

得到 \(x\le p_n-2^i\)。

还有一种是 \(p_n<x\)，此时需要通过取模使得值变大，此时不等式可以写成 \(p_n-x+2^{i+1}\ge2^i\)，

得到 \(x\le p_n+2^{i+1}-2^i=p_n+2^i\)，

从而 \((x\le p_n-2^i)\cup(p_n<x\le p_n+2^{i+1}-2^i=p_n+2^i)\)

② 当 \(p_n<2^i\)，此时如果我们要使得不等式成立，一定是通过 \(x>p_n\)，使得变为负数，通过取模变大，

那么不等式化可以写成 \(p_n-x+2^{i+1}\ge2^i\)

得到 \(x\le p_n+2^{i+1}-2^i=p_n+2^i\)

从而 \(p_n<x\le p_n+2^{i+1}-2^i=p_n+2^i\)

易知，只需要一个可以查询值在 \([L,R]\) 范围内的个数的可增加可删除的数据结构，这里我们使用树状数组。

对二进制的每一位都使用一颗树状数组进行维护。

最终时间复杂度 \(O(q(\log V)^2)\)

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1 << 22;
int tr[22][N];
int lowbit(int x) {
    return x & -x;
}
void add(int idx, int x, int k) {
    x++;
    while (x < N) {
        tr[idx][x] += k;
        x += lowbit(x);
    }
}
int query(int idx, int x) {
    x++;
    int res = 0;
    while (x) {
        res += tr[idx][x];
        x -= lowbit(x);
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(1, 0);
    function<void(int, int)> add = [&](int x, int k) {
        for (int i = 0 ; i < 21 ; i++) {
            int y = x % (1 << (i + 1));
            ::add(i, y, k);
        }
    };
    add(0, 1);
    for (int i = 1 ; i <= n ; i++) {
        int t, v;
        cin >> t >> v;
        while (t--) {
            int x = a.back();
            add(x, -1);
            a.pop_back();
        }
        {
            int x = (a.back() + v) % (1 << 22);
            a.push_back(x);
        }
        i64 ans = 0;
        for (int j = 0 ; j < 21 ; j++) {
            int x = a.back() % (1 << (j + 1));
            int cnt = 0;
            if (x >= (1 << j)) {
                cnt += query(j, x - (1 << j));
            }
            cnt += query(j, x + (1 << j)) - query(j, x);
            if (cnt & 1) {
                ans |= 1 << j;
            }
        }
        cout << ans << "\n";
        add(a.back(), 1);
    }
    return 0;
}

H World Finals

题意

有两场比赛，分别有 \(n,m\) 个队伍。

给出每个队伍的预测成绩(解题数和罚时)。

每个队伍必须参加一场比赛。

如果让你来安排比赛，问 lzr010506 参加任意比赛的最好排名。

解题思路

如果两场比赛都参加，就可以把这个队伍(除 lzr010506)的预测解题数改为 \(-1\)，

因为如果 lzr010506 参加第一场比赛，那么就可以让都参加的队伍去参加第二场，从而让 lzr010506 的排名尽可能靠前，

如果 lzr010506 参加第二场比赛，同理。

然后对解题数和罚时排序，分别求出两场比赛 lzr010506 的名次，并取最优即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct Node {
    string name;
    int solve, time;
    friend bool operator<(const Node &x, const Node &y) {
        if (x.solve == y.solve) {
            return x.time < y.time;
        }
        return x.solve > y.solve;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    map<string, int> mp;
    vector<Node> v1, v2;
    for (int i = 1 ; i <= n ; i++) {
        string name;
        int solve, time;
        cin >> name >> solve >> time;
        v1.push_back({name, solve, time});
        mp[name]++;
    }
    int m;
    cin >> m;
    for (int i = 1 ; i <= m ; i++) {
        string name;
        int solve, time;
        cin >> name >> solve >> time;
        v2.push_back({name, solve, time});
        mp[name]++;
    }
    for (auto &v : {&v1, &v2}) {
        for (auto &[name, solve, _] : *v) {
            if (mp[name] == 2 && name != "lzr010506") {
                solve = -1;
            }
        }
        sort(begin(*v), end(*v));
    }
    int ans = max(n, m);
    for (auto &v : {&v1, &v2}) {
        int rk = 0;
        for (auto &[name, solve, _] : *v) {
            rk++;
            if (name == "lzr010506") {
                ans = min(ans, rk);
                break;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

I Mirror Maze

题意

有 \(n*m\) 面镜子，每个镜子有 '|'、'\'、'-'、'/'。

对于 '|' 来说，如果光从左方或右方发射过来，则会直线反射回相反的方向，如果光从上方或下方发射过来，则会直接穿过镜子不会反射；

对于 '-' 来说，如果光从上方或下方发射过来，则会直线反射回相反的方向，如果光从左方或右方发射过来，则会直接穿过镜子不会反射；

对于 '\' 来说，如果光从左方或下方发射过来，则会反射到下方或左方，如果光从右方或上方发射过来，则会反射到上方或右方；

对于 '/' 来说，如果光从左方或上方发射过来，则会反射到上方或左方，如果光从右方或下方发射过来，则会反射到下方或右方；

然后 \(q\) 次询问，每次询问给定一个点，和一个方向，

问你从这个点按照这个方向发射一道光，会被多少不同的镜子反射。

解题思路

我们可以知道，可能有一些镜子构成了回路，使得光无限反射，也就是环。

易知，从外部一定无法进环。

所以我们可以分成两类，一种是从环中出发，一种是不从环中出发。

我们对每面镜子建立四个方向节点，枚举每个点，进行染色，求出连通块，在过程中，若要前往的下一个点已经被染色，则说明是一个环。

染色后，枚举每个环，预处理中环上被反射的镜子种数，如果连续路径没有改变方向，说明没有发生反射，否则我们可以把这个点(不带方向)放入集合中。

处理完环之后，我们对链进行处理。

我们可以知道，任意一条链的终点一定是射向外界的。

因为这条链有重复的点(不带方向)，所以我们不能简单的记忆化，

我们可以反着来，假设是从外界射向内部，则我们的顺序正好是，这条链的逆序，这样不会算重复的贡献。

所以我们类似于环的处理方法，对路径逆序处理即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
// 右 上 左 下
const int dx[] = {0, -1, 0, 1};
const int dy[] = {1, 0, -1, 0};
int n, m;
// | - \ /
int D[4][4] = {
    {2, 1, 0, 3},
    {0, 3, 2, 1},
    {3, 2, 1, 0},
    {1, 0, 3, 2}
};
int g[1005][1005];
int c[1005][1005][4];
int tot = 1;
vector<array<int, 3>> vec[1005 * 1005 * 4];
bool vis[1005 * 1005 * 4];
int ans[1005][1005][4];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    map<char, int> f;
    f['|'] = 0; f['-'] = 1; f['\\'] = 2; f['/'] = 3;
    map<string, int> mp;
    mp["below"] = 3; mp["right"] = 0; mp["left"] = 2; mp["above"] = 1;
    for (int i = 1 ; i <= n ; i++) {
        string str;
        cin >> str;
        str = " " + str;
        for (int j = 1 ; j <= m ; j++) {
            g[i][j] = f[str[j]];
        }

    }
    // 连通块染色
    auto work1 = [&](int x, int y, int d) {
        while (true) {
            c[x][y][d] = tot;
            vec[tot].push_back({x, y, d});
            int xx = x + dx[d], yy = y + dy[d];
            if (xx < 1 || xx > n || yy < 1 || yy > m) {
                break;
            }
            int dd = D[g[xx][yy]][d];
            if (c[xx][yy][dd] != 0) {
                if (c[xx][yy][dd] == c[x][y][d]) {
                    vis[tot] = true;
                }
                break;
            }
            x = xx;
            y = yy;
            d = dd;
        }
        tot++;
    };
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= m ; j++) {
            for (int k = 0 ; k < 4 ; k++) {
                if (c[i][j][k] == 0) {
                    work1(i, j, k);
                }
            }
        }
    }
    // 预处理所有环
    for (int i = 1 ; i < tot ; i++) {
        if (!vis[i]) continue;
        bool flag = true;
        unordered_set<int> st;
        int len = vec[i].size();
        for (int j = 0 ; j < len ; j++) {
            auto [x1, y1, d1] = vec[i][(j - 1 + len) % len];
            auto [x2, y2, d2] = vec[i][j];
            if (d1 == d2) continue;
            st.insert(x2 * 1005 + y2);
        }
        int res = st.size();
        for (auto &[x, y, d] : vec[i]) {
            ans[x][y][d] = res;
        }
    }
    // 预处理所有链
    auto work2 = [&](int x, int y, int d) {
        vector<array<int, 3>> path;
        do {
            path.push_back({x, y, d});
            int xx = x + dx[d], yy = y + dy[d];
            if (xx < 1 || xx > n || yy < 1 || yy > m) {
                break;
            }
            x = xx;
            y = yy;
            d = D[g[xx][yy]][d];
        } while (true);
        map<int, int> cnt;
        int len = path.size();
        for (int k = 1 ; k < len ; k++) {
            auto [x1, y1, d1] = path[k - 1];
            auto [x2, y2, d2] = path[k];
            if (d1 != d2) {
                cnt[x2 * 1005 + y2]++;
            }
        }
        for (int i = len - 2 ; i >= 0 ; i--) {
            auto [x1, y1, d1] = path[i + 1];
            auto [x2, y2, d2] = path[i];
            int td = (d2 + 2) % 4;
            if (d1 != d2) {
                cnt[x1 * 1005 + y1]--;
                if (cnt[x1 * 1005 + y1] == 0) {
                    cnt.erase(x1 * 1005 + y1);
                }
            }
            ans[x1][y1][td] = cnt.size();
        }
    };
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= m ; j++) {
            if (i == 1) {
                work2(0, j, 3);
            }
            if (i == n) {
                work2(n + 1, j, 1);
            }
            if (j == 1) {
                work2(i, 0, 0);
            }
            if (j == m) {
                work2(i, m + 1, 2);
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        string s;
        cin >> x >> y >> s;
        cout << ans[x][y][mp[s]] << "\n";
    }
    return 0;
}

J 2D Travel

题意

在一个二维平面 \(W={(x,y)\mid0\le x\le n,0\le y\le m}\)

有如下四种操作：

'U'：\((x,y)\xrightarrow{U}(x,y+1)\)

'D'：\((x,y)\xrightarrow{D}(x,y-1)\)

'L'：\((x,y)\xrightarrow{L}(x-1,y)\)

'R'：\((x,y)\xrightarrow{R}(x+1,y)\)

每次操作都不能走到平面外。

按顺序给出 \(k\) 个操作，\(c,t\)，表示执行操作 \(c\)，\(t\) 次。

有 \(q\) 次询问，问起点为 \((x,y)\)，并顺序执行 \([L,R]\) 中的操作，最终走到了哪个位置，有效步数是多少。

解题思路

首先我们就要考虑越界，所以有边界点和越界点两个概念。

我们定义：

\(sxL\) 为 \(x\) 轴从点 \(sxL\) 出发恰好不会越界的最小点(左端点)。

\(txL\) 为 \(x\) 轴从点 \(sxL\) 出发的终点。

\(sxR\) 为 \(x\) 轴从点 \(sxR\) 出发恰好不会越界的最大点(右端点)。

\(txR\) 为 \(x\) 轴从点 \(sxR\) 出发的终点。

对于 \(y\) 轴同理有 \(syL,tyL,syR,tyR\)。

我们还需要记录有效步数，那么我们定义 \(sum\) 为最大的有效步数。

所以对于一个区间，我们有起点 \((x,y)\)，

当 \(x<sxL\) 时，一定会往左越界，且走到 \(txL\)，

当 \(x>sxR\) 时，一定会往右越界，且走到 \(txR\)，

当 \(sxL\le x\le sxR\) 时，此时不会越界，我们可以发现 \([sxL,sxR]\) 和 \([txL,txR]\) 会有一对一的关系，所以我们会走到 \(x-sxL+txL\)。

对于 \(y\) 也同理。

现在我们考虑两个区间合并，

取左区间为 \(x\)，右区间为 \(y\)。

定义 \(xL=\max(x.txL,y.sxL)\) 为区间合并后的左端点，\(xR=\min(x.txR,y.sxR)\) 为区间合并后的右端点。

首先我们可以将合并后区间的 \(sum\) 暂定为 \(x.sum+y.sum\)。

当 \(xL>xR\) 时，说明合并后的区间一定越界了而且一定只有一个点，

这个时候由于完全越界了，那么我们合并后的区间的 \(sum\) 算多了，需要减去 \(xL-xR\)。
然后我们要考虑是左越界点还是右越界点，
当 \(x.txR<y.sxL\) 时，说明左越界，所以合并后的区间 \(sxL=sxR=x.sxR，txL=txR=y.txL\)，
当 \(x.txR\ge y.sxL\) 时，说明右越界，所以合并后的区间 \(sxL=sxR=x.sxL，txL=txR=y.txR\)。

当 \(xL\le xR\) 时，说明合并后区间没有完全越界，

如果 \(x.txL>y.sxL\) 即左侧区间的左终点小于右侧区间的左边界点，
说明区间合并后不会越界，此时合并区间的左边界点为 \(x.sxL\)，左终点为 \(x.txL+x.txL-y.sxL\)。
如果 \(x.txL\le y.sxL\) 即左侧区间的左终点大于等于右侧区间的左边界点，
说明区间合并后越界了，此时合并区间的左边界点为 \(y.sxL + x.sxL - x.txL\)，左终点为 \(y.txL\)。
综合来说，可以看做合并区间的左边界点为 \(x.sxL-\max(x.txL,y.sxL)-x.txL\)，左终点为 \(x.txL+\max(x.txL,y.sxL)-y.sxL\)。
同理，合并区间的右边界点为 \(x.syL-\max(x.tyL,y.syL)-x.tyL\)，左终点为 \(x.tyL+\max(x.tyL,y.syL)-y.syL\)。

最终使用线段树维护区间即可，在线查询，时间复杂度 \(O(n*\log n)\)。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
struct Node {
    int Lrt, Rrt;
    i64 sum;
    i64 sxL, sxR, syL, syR;
    i64 txL, txR, tyL, tyR;
} tr[100005 << 5];
int tot;
Node merge(Node x, Node y) {
    Node z{};
    i64 xL = max(x.txL, y.sxL), yL = max(x.tyL, y.syL);
    i64 xR = min(x.txR, y.sxR), yR = min(x.tyR, y.syR);
    z.sum = x.sum + y.sum;
    if (xL > xR) {
        if (x.txR < y.sxL) {
            z.sxL = z.sxR = x.sxR;
            z.txL = z.txR = y.txL;
        } else {
            z.sxL = z.sxR = x.sxL;
            z.txL = z.txR = y.txR;
        }
        z.sum -= xL - xR;
    } else {
        z.sxL = x.sxL + xL - x.txL;
        z.txL = y.txL + xL - y.sxL;
        z.sxR = x.sxL + xR - x.txL;
        z.txR = y.txL + xR - y.sxL;
    }
    if (yL > yR) {
        if (x.tyR < y.syL) {
            z.syL = z.syR = x.syR;
            z.tyL = z.tyR = y.tyL;
        } else {
            z.syL = z.syR = x.syL;
            z.tyL = z.tyR = y.tyR;
        }
        z.sum -= yL - yR;
    } else {
        z.syL = x.syL + yL - x.tyL;
        z.syR = x.syL + yR - x.tyL;
        z.tyL = y.tyL + yL - y.syL;
        z.tyR = y.tyL + yR - y.syL;
    }
    return z;
}
void pushup(int p) {
    Node z = merge(tr[tr[p].Lrt], tr[tr[p].Rrt]);
    z.Lrt = tr[p].Lrt;
    z.Rrt = tr[p].Rrt;
    tr[p] = z;
}
int n, m;
char c[100005];
int t[100005];
int build(int L, int R) {
    int now = ++tot;
    if (L == R) {
        if (c[L] == 'U') {
            tr[now].sxL = 0;
            tr[now].sxR = n;
            tr[now].txL = 0;
            tr[now].txR = n;
            tr[now].syL = 0;
            tr[now].syR = max(0, m - t[L]);
            tr[now].tyL = min(m, t[L]);
            tr[now].tyR = m;
            tr[now].sum = min(m, t[L]);
        }
        if (c[L] == 'D') {
            tr[now].sxL = 0;
            tr[now].sxR = n;
            tr[now].txL = 0;
            tr[now].txR = n;
            tr[now].syL = min(m, t[L]);
            tr[now].syR = m;
            tr[now].tyL = 0;
            tr[now].tyR = max(0, m - t[L]);
            tr[now].sum = min(m, t[L]);
        }
        if (c[L] == 'R') {
            tr[now].sxL = 0;
            tr[now].sxR = max(0, n - t[L]);
            tr[now].txL = min(n, t[L]);
            tr[now].txR = n;
            tr[now].syL = 0;
            tr[now].syR = m;
            tr[now].tyL = 0;
            tr[now].tyR = m;
            tr[now].sum = min(n, t[L]);
        }
        if (c[L] == 'L') {
            tr[now].sxL = min(n, t[L]);
            tr[now].sxR = n;
            tr[now].txL = 0;
            tr[now].txR = max(0, n - t[L]);
            tr[now].syL = 0;
            tr[now].syR = m;
            tr[now].tyL = 0;
            tr[now].tyR = m;
            tr[now].sum = min(n, t[L]);
        }
        return now;
    }
    int mid = L + R >> 1;
    tr[now].Lrt = build(L, mid);
    tr[now].Rrt = build(mid + 1, R);
    pushup(now);
    return now;
}
Node query(int old, int L, int R, int QL, int QR) {
    if (QL <= L && R <= QR) {
        return tr[old];
    }
    int mid = L + R >> 1;
    if (QR <= mid) {
        return query(tr[old].Lrt, L, mid, QL, QR);
    }
    if (QL > mid) {
        return query(tr[old].Rrt, mid + 1, R, QL, QR);
    }
    return merge(query(tr[old].Lrt, L, mid, QL, QR), query(tr[old].Rrt, mid + 1, R, QL, QR));
}
int main() {
    int k, q;
    cin >> n >> m >> k >> q;
    for (int i = 1 ; i <= k ; i++) {
        cin >> c[i] >> t[i];
    }
    int rt = build(1, k);
    while (q--) {
        int x, y, L, R;
        cin >> x >> y >> L >> R;
        auto res = query(rt, 1, k, L, R);
        i64 X, Y, Z;
        Z = res.sum;
        if (x < res.sxL) {
            X = res.txL;
            Z -= res.sxL - x;
        } else if (x > res.sxR) {
            X = res.txR;
            Z -= x - res.sxR;
        } else {
            X = x + res.txL - res.sxL;
        }
        if (y < res.syL) {
            Y = res.tyL;
            Z -= res.syL - y;
        } else if (y > res.syR) {
            Y = res.tyR;
            Z -= y - res.syR;
        } else {
            Y = y + res.tyL - res.syL;
        }
        cout << X << " " << Y << " " << Z << "\n";
    }
    return 0;
}