记录编号	607120	评测结果	AAAAAAAAAATTTTT
题目名称	3863.[USACO23 Jan Silver] Following Directions	最终得分	67
用户昵称	梦那边的没好TM	是否通过	未通过
代码语言	C++	运行时间	26.955 s
提交时间	2025-10-05 17:18:10	内存使用	102.59 MiB

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

#define ll long long
#define cpy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll n,q,p[3005],sz[2253000],f[2253000],ans;
char a[1505][1505];
vector<vector<ll>>son(2253000);

ll deal(ll x,ll 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(ll x,ll y,ll fa){
    ll u=deal(x,y),ux=deal(x-1,y),uy=deal(x,y-1);
    sz[u]=1;
    f[u]=fa;
    if(a[x][y-1]=='R'){
        son[u].push_back(uy);
        dfs(x,y-1,fa);
        sz[u]+=sz[uy];
    }
    if(a[x-1][y]=='D'){
        son[u].push_back(ux);
        dfs(x-1,y,fa);
        sz[u]+=sz[ux];
    }
}

void ddfs(ll x,ll y,ll fa,ll c){
    ans+=c;
    f[deal(x,y)]=fa;
    if(a[x][y-1]=='R'){
        ddfs(x,y-1,fa,c);
    }
    if(a[x-1][y]=='D'){
        ddfs(x-1,y,fa,c);
    }
}

int main(){
    cin>>n;
    foru(i,1,n){
        foru(j,1,n){
            cin>>a[i][j];
        }
        cin>>p[i];
    }
    foru(i,n+1,n*2)cin>>p[i];
    foru(i,1,n){
        if(a[i][n]=='R'){
            son[n*n+i].push_back(deal(i,n));
            dfs(i,n,i);
            sz[n*n+i]=sz[deal(i,n)];
        }
    }
    foru(i,n+1,n*2){
        if(a[n][i-n]=='D'){
            son[n*n+i].push_back(deal(n,i-n));
            dfs(n,i-n,i);
            sz[n*n+i]=sz[deal(n,i-n)];
        }
    }
    foru(i,1,n*2){
        ans+=p[i]*sz[n*n+i];
    }
    cout<<ans<<endl;
    foru(i,1,n){
        f[deal(n+1,i)]=i+n;
        f[deal(i,n+1)]=i;
    }
    cin>>q;
    while(q--){
        ll x,y;
        cin>>x>>y;
        ll tmp=0;
        if(a[x][y]=='R'){
            tmp=f[deal(x+1,y)],a[x][y]='D';
        }else{
            tmp=f[deal(x,y+1)],a[x][y]='R';
        }
        ll v=p[tmp];
        ll c=v-p[f[deal(x,y)]];
        ddfs(x,y,tmp,c);
        cout<<ans<<endl;
    }
    return 0;
}