又是一道水题

· · 题解

分析亿下

数组需要开很大所以不能开二维数组，询问的次数很多，所以不能通过遍历去求和。

打个表可以发现在原始状态下，第 i 行或列的值为：

n*i+n*(n+1)/2

所以每一行或列的值都是固定的，那么就只需要统计出减少的值。模拟一下可以发现，每一次行的减少，会对所有的列减少当前的行数加上这一列的列数，所以就可以用一个变量统计下所有行减少的当前行数，在统计一下一共减去了多少行，再在输出时将它乘上当前的列数。列的算法同样如此。

重点（代码）

#include<bits/stdc++.h>
using namespace std;
long long n,q,C,R,sumr,sumc,visr[1000005],visc[1000005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=q;i++) {
        char s;
        int x;
        cin>>s>>x;
        if(s=='R'){
            if(visr[x]){
                cout<<0<<'\n';
                continue;
            }
            cout<<n*(n+1+2*x)/2-sumc*x-R<<"\n";
            visr[x]=1;
            C+=x;
            sumr++;
        }
        else {
            if(visc[x]){
                cout<<"0\n";
                continue;
            }
            cout<<n*(n+1+2*x)/2-sumr*x-C<<"\n";
            visc[x]=1;
            R+=x;
            sumc++;
        }
    }
    return 0;
}