记录编号	607052	评测结果	AAAAAAAAAAAAAAA
题目名称	3863.[USACO23 Jan Silver] Following Directions	最终得分	100
用户昵称	zhyn	是否通过	通过
代码语言	C++	运行时间	1.240 s
提交时间	2025-10-05 13:46:41	内存使用	14.32 MiB

#include<bits/stdc++.h>
using namespace std;
 
#define maxn 3000
 
#define ll long long
 
int n,t;
bool vis[maxn][maxn];
ll a[maxn],b[maxn];
int l[maxn],r[maxn];
int k[maxn][maxn];
int tot[maxn][maxn];
int p[maxn];
ll cnt=0;
 
 
struct node{
    int x,y;
};
queue<node>q;
ll ans=0;

void solve(int x,int y,ll f){
	tot[x][y]=1;
    if(x-1!=0&&!vis[x-1][y]){
        //cnt++;
        solve(x-1,y,f);
        tot[x][y]+=tot[x-1][y];
    }
    if(y-1!=0&&vis[x][y-1]){
        //cnt++;
        solve(x,y-1,f);
        tot[x][y]+=tot[x][y-1];
    }
}


void sol(int s){
	ll sum=0;
	int x=l[s],y=r[s];
	int p=tot[l[s]][r[s]];
	while(x!=n+1&&y!=n+1){
		tot[x][y]-=p;
        if(vis[x][y]){
            y++;
        }
        else{
            x++;
        }
    }
    if(x==n+1){
    	sum=b[y];
	}
	else{
		sum=a[x];
	}
    tot[l[s]][r[s]]=p;
    ans-=p*sum;
	vis[l[s]][r[s]]^=1;
	x=l[s],y=r[s];
	while(x!=n+1&&y!=n+1){
		tot[x][y]+=p;
        if(vis[x][y]){
            y++;
        }
        else{
            x++;
        }
    }
    if(x==n+1){
    	sum=b[y];
	}
	else{
		sum=a[x];
	}
	tot[l[s]][r[s]]=p;
	ans+=p*sum;
	cout<<ans<<"\n"; 
}
 
int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    
    freopen("zunxun.in","r",stdin);
    freopen("zunxun.out","w",stdout);
    
    
    cin>>n;
    for(int i=1;i<=n;i++){
        char s;
        for(int j=1;j<=n;j++){
            cin>>s;
            if(s=='R'){
                vis[i][j]=1;
            }
            else{
                vis[i][j]=0;
            }
        }
        cin>>a[i];
    }
    
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    
    for(int i=1;i<=n;i++){
    	cnt=0;
    	if(vis[i][n]){	
    		solve(i,n,a[i]);
    		cnt=tot[i][n];
    	}
    	ans+=a[i]*cnt;
    	cnt=0;
    	if(!vis[n][i]){
    		solve(n,i,b[i]);
    		cnt=tot[n][i];
		}
    	ans+=b[i]*cnt;
	} 
	
	cout<<ans<<"\n";
    
    cin>>t;
    
    
    for(int i=1;i<=t;i++){
        int x,y;
        cin>>x>>y;
        l[i]=x,r[i]=y;
    }
    
    for(int i=1;i<=t;i++){
        sol(i);
    }
    
    
    return 0;
}