Adjustment Office

杂

Input file: adjustment.in
Output file: adjustment.out

Description

Garrison and Anderson are working in a company named “Adjustment Office”. In competing companies workers change the reality, in this company they try to predict the future.

They are given a big square board $n × n$. Initially in each cell $(x, y)$ of this board the value of $x + y$ is
written $(1 ≤ x, y ≤ n)$. They know that in the future there will be two types of queries on the board:

• “R r” — sum up all values in row r, print the result and set all values in row r to zero;
• “C c” — sum up all values in column c, print the result and set all values in column c to zero.

They have predicted what queries and results there will be. They need to ensure that they have correctly predicted the results. Help them by computing the results of the queries.

Input

The first line of the input contains two integers n and q $(1 ≤ n ≤ 10^6, 1 ≤ q ≤ 10^5 )$ — the size of the square and the number of queries.

Each of the next q lines contains the description of the query. Each query is either “R r” (1 ≤ r ≤ n) or “C c” (1 ≤ c ≤ n).

Output

The output file shall contain q lines. The i-th line shall contain one integer — the result of the i-th query.

Sample input

3 7
R 2
C 3
R 2
R 1
C 2
C 1
R 3

Sample output

12
10
0
5
5
4
0

题意：输入n和q，代表有一个n*n的数字正方形，a[i][j]的值为i+j（1≤i,j≤n），下面有q次询问及操作，先输入一个字母R或者C，再输入数字x，要求输出该行或者该列数字的总和，然后把这行或者这列的所有数字置零。

分析：肯定不能暴力……然后画图，找了下规律，发现行和对应的列的和是相等的，比如3*3的正方形，第一列和第一行的数字都是2,3,4，和都是9，然后发现：

计算n*n大小的正方形，第x行/列的和的公式：n*x+n（n+1）/2；

然后要将该行/列置零，就用数组将他们标记一下，并且为零的行数/列数+1，即 r++或c++；
并且把行/列号加起来，sumr+=x或sumc+=x

最后用每行每列原始的和减去置零的行/列的个数*输入的行/列+置零行/列编号之和:
n*x+(n+1)*n/2-x*r-sumr或n*x+(n+1)*n/2-x*c-sumc

这样说可能有点不清楚，举个例子：
3*3的正方形，把第一行和第二行都置为0了，那么这个时候置零的行数r=2，sumr=3，（1+2=3），如果这个时候C 3，需要知道第三列的和，第三列原来的和是15，可以由上面的那个公式得到，再减去 r*x+sumr（x是输入的行/列，这时为3），那么就是15-2*3-3=6

画一下然后算一下……还比较好理解

• 完整代码：

#include<stdio.h>
#include<string.h>
#define LL long long
LL sr[1000005],sc[1000005]; //某行某列是否用过
int main()
{
    freopen("adjustment.in","r",stdin);
    freopen("adjustment.out","w",stdout);
    LL n,q,x;
    LL r,c,sumr,sumc;
    LL sum,ans;
    char ch[3];
    while(scanf("%lld%lld",&n,&q)!=EOF)
    {
        sum=(n*(n+1))/2;
        r=0,c=0,sumr=0,sumc=0;
        memset(sr,0,sizeof(sr));
        memset(sc,0,sizeof(sc));
        while(q--)
        {
            scanf("%s%lld",ch,&x);
            if(ch[0]=='R')
            {
                if(sr[x]!=0)
                    ans=0;
                else
                {
                    r++,sumr+=x,sr[x]=1;
                    ans=x*n+sum-c*x-sumc;
                }
            }
            if(ch[0]=='C')
            {
                if(sc[x]!=0)
                    ans=0;
                else
                {
                    c++,sumc+=x,sc[x]=1;
                    ans=x*n+sum-r*x-sumr;
                }
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}