洛谷 P6974 [NEERC2015] Adjustment Office 题解

题目传送门

xxs又来写题解啦

STEP 1：题意简化：

有一个大小为 n×n?的矩阵，每个位置的值为该位置的行数+列数。

接下来有?q?次操作：

• R?m：输出第?m?行的总和并整行消去。
• C?m：输出第?m?列的总和并整列消去。

这个题目真良心，题意简洁。

STEP 2：思路分析：

第一反应是直接开个数组，直接模拟。但是——

1?n?1e6，1?q?1e5，1?m?n。

这么大的二维数组怎么开！

再度陷入苦恼……

但上帝为我们关一扇门时，又给我们开了一扇窗。

以下是引用：有一个大小为 n×n?的矩阵，每个位置的值为该位置的行数?+?列数。

所以整个矩阵可以画成这样：

n=4

1+1 1+2 1+3 1+4
2+1 2+2 2+3 2+4
3+1 3+2 3+3 3+4
4+1 4+2 4+3 4+4

假设删除的是第?2?列：

1+2
2+2
3+2
4+2

发现了吗，每一列的和就是从?1?加到?n?的和再加上?n?倍的?x（第?x?列）。

行也是一个道理。

但是在这之前，可能会有一些删除：

假设删除了 1 和 3 行：

/
2+2
/
4+2

这个时候答案就应该是?(1+4)×4÷2+2×(4?2)?(1+3)。

其中?4?2 的?2?是删除行的数量，1+3 是删除的行编号之和，这个可以在删除时顺便保存。

所以，在删除一行的时候就需要：

    cc++;
    c_sum+=x;

其中?cc?是删除行的数量，c_sum?即删除行（编号）之和。

在输出时就可以直接：

    cout<<s+x*(n-cc)-c_sum;

其中?s?就是事先算好的 (1+n)×n÷2。

STEP 3：避开坑点

还记得我们开始时的顾虑吗？

1?n?1e6，1?q?1e5，1?m?n。

既然?n?这么大，输出……

所以一定要加上一句：

#define int long long

并且要注意标记已删除，这个用数组没问题。

AC code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,x,c_sum,r_sum,cc,rr;
char ch;
bool c[1000001],r[1000001];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    const int s=(1+n)*n/2;
    while(q--){
        cin>>ch>>x;
        if(ch=='R'){
            if(r[x])cout<<0;//如果已被删除直接输出 0。
            else {
                r[x]=1;//标记已经没有了。
                cout<<s+x*(n-cc)-c_sum;
                rr++;
                r_sum+=x;
            }
        } else {
            if(c[x])cout<<0;
            else {
                c[x]=1;
                cout<<s+x*(n-rr)-r_sum;
                cc++;
                c_sum+=x;
            }
        }
        cout<<'\n';
    }
    return 0;
}

关下呗