A2426 迷雾【无数据】

#include <bits/stdc++.h>
using namespace std;

/*
迷雾：n*m 网格，q 次移动。每次移动 c_i 走 a_i 步；
若这次移动结束后停在迷雾 'X' 上，就把 c_{i+k}, c_{i+2k}, ... 这 b_i 个方向全部反转。

关键：所有被修改的位置与修改源 i 同余模 k，且步数 t 满足 i <= i+t*k <= i+b_i*k。
于是对每个模 k 的余数类单独维护一条差分数组：
  源 i 落在类内的下标 idx，则给类内 [idx+1, idx+b_i] 区间 +1。
按 i 从小到大处理，走到一个位置时，它的翻转次数就是本类差分数组在该下标的前缀和。
*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q, k;
    cin >> n >> m >> q >> k;
    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    vector<char> c(q);
    vector<int> a(q), b(q);
    for (int i = 0; i < q; i++) cin >> c[i] >> a[i] >> b[i];

    // 每个余数类一条差分数组，类内下标从 0 开始
    vector<vector<int>> diff(k);
    vector<int> clsSize(k, 0);
    for (int i = 0; i < q; i++) clsSize[i % k]++;
    for (int r = 0; r < k; r++) diff[r].assign(clsSize[r] + 1, 0);
    vector<int> cur(k, 0);

    int x = 1, y = 1; // 1-based
    for (int i = 0; i < q; i++) {
        int r = i % k;
        int idx = i / k;
        cur[r] += diff[r][idx]; // 本位置累计到的翻转次数

        char dir = c[i];
        if (cur[r] & 1) {       // 翻转奇数次
            if (dir == 'U') dir = 'D';
            else if (dir == 'D') dir = 'U';
            else if (dir == 'L') dir = 'R';
            else if (dir == 'R') dir = 'L';
        }

        int step = a[i];
        if (dir == 'U') x = max(1, x - step);
        else if (dir == 'D') x = min(n, x + step);
        else if (dir == 'L') y = max(1, y - step);
        else if (dir == 'R') y = min(m, y + step);

        if (g[x - 1][y - 1] == 'X' && b[i] > 0) {
            int lo = idx + 1;
            int hi = idx + b[i];
            if (hi >= clsSize[r]) hi = clsSize[r] - 1;
            if (lo <= hi) {
                diff[r][lo] += 1;
                if (hi + 1 < (int)diff[r].size()) diff[r][hi + 1] -= 1;
            }
        }
    }
    cout << x << ' ' << y << "\n";
    return 0;
}