记录编号	607073	评测结果	AAAAAAAAAATTTTT
题目名称	3863.[USACO23 Jan Silver] Following Directions	最终得分	67
用户昵称	wdsjl	是否通过	未通过
代码语言	C++	运行时间	16.724 s
提交时间	2025-10-05 14:51:39	内存使用	110.08 MiB

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

const int N = 1600;

vector<int> son[N * N + 2 * N];
int n, q, c[N * 2], siz[N * N + 2 * N], f[N * N + 2 * N], ans;
char a[N][N];

int id(int x, int y) {
    if (x <= n && y <= n) {
        return (x - 1) * n + y;
    }
    if (x == n + 1) {
        return n * n + n + y;
    }
    return n * n + x;
}

void dfs(int x, int y, int fa) {
    int nid = id(x, y);
    int nidx = id(x - 1, y);
    int nidy = id(x, y - 1);
    siz[nid] = 1;
    f[nid] = fa;
    if (a[x][y - 1] == 'R') {
        son[nid].push_back(nidy);
        dfs(x, y - 1, fa);
        siz[nid] += siz[nidy];
    }
    if (a[x - 1][y] == 'D') {
        son[nid].push_back(nidx);
        dfs(x - 1, y, fa);
        siz[nid] += siz[nidx];
    }
}

void dfs2(int x, int y, int fa, int cha) {
    ans += cha;
    f[id(x, y)] = fa;
    if (a[x][y - 1] == 'R') {
        dfs2(x, y - 1, fa, cha);
    }
    if (a[x - 1][y] == 'D') {
        dfs2(x - 1, y, fa, cha);
    }
}

signed main() {
    freopen("zunxun.in", "r", stdin);
    freopen("zunxun.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
        cin >> c[i];
    }
    for (int i = n + 1; i <= 2 * n; i++) {
        cin >> c[i];
    }
    for (int i = 1; i <= n; i++) {
        if (a[i][n] == 'R') {
            son[n * n + i].push_back(id(i, n));
            dfs(i, n, i);
            siz[n * n + i] = siz[id(i, n)];
        }
    }
    for (int i = n + 1; i <= 2 * n; i++) {
        if (a[n][i - n] == 'D') {
            son[n * n + i].push_back(id(n, i - n));
            dfs(n, i - n, i);
            siz[n * n + i] = siz[id(n, i - n)];
        }
    }
    for (int i = 1; i <= 2 * n; i++) ans += c[i] * siz[n * n + i];
    cout << ans << endl;
    for (int i = 1; i <= n; i++) {
        f[id(n + 1, i)] = i + n;
        f[id(i, n + 1)] = i;
    }
    cin >> q;
    while (q--) {
        int xx, yy;
        cin >> xx >> yy;
        int ff = 0;
        if (a[xx][yy] == 'R') {
            ff = f[id(xx + 1, yy)];
            a[xx][yy] = 'D';
        } else {
            ff = f[id(xx, yy + 1)];
            a[xx][yy] = 'R';
        }
        int val = c[ff];
        int cha = val - c[f[id(xx, yy)]];
        dfs2(xx, yy, ff, cha);
        cout << ans << endl;
    }
    return 0;
}