HPU 1151(思維)

問題：

 n * n的棋盤，每格上放有豆子，個數是 行數 和 列數 的和，

一次拿走 一行，或一列，

求拿走的個數。

輸入：

多組測試資料。

第一行為兩個整數，n，q(1 ≤ n ≤ 10^6,1 ≤ q ≤ 10^5)，分别代表棋盤有n行n列，取q次

下面q行有兩種形式：

R k代表取出第k行，并輸出該行的豆子總數。

C k代表取出第k列，并輸出該列的豆子總數。

輸出：

每次取走的個數

樣例輸入

3 2
R 1
C 1
      

樣例輸出

9
7       

1	2	3
1	2	3	4
2	3	4	5
3	4	5	6

如上表，n=3，可以觀察到，後一 行/列 的總個數比前一 行/列 的總個數多 n。

是以，第一行/列 總個數，s = （2+(n+1)）*n/2; 

第   n  行/列 的總個數  ，sn = s+（n-1）*n；

因為拿走就不存在了，是以 上述的 sn 要 減去不存在的，

假如：2、3 兩 列已經拿走了，那麼 任意 第  r 行都 少 了  2*r+（2+3） 個！！！ （難點！！！）

          因為  每個格子 都是 行 加 列。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

long long i[1000010],j[1000010];

int main()
{
     char a;
     long long n,t,x,s;  // n 行 n列，t組測試資料
     long long h,h1,l,l1;
     while(scanf("%lld %lld",&n,&t)!=EOF)
     {
         h = 0,h1 = 0,l = 0,l1 = 0;
         memset(i,0,sizeof(i));
         memset(j,0,sizeof(j));
     while(t--)
     {
         getchar();
         scanf("%c%lld",&a,&x);    // R 行   C 列
         s = (3+n)*n/2;            //第一行/列的個數
         s += (x - 1)*n;           //   原本第x 行/列的個數
         if(a=='R')
         {
             if(i[x]==0)
             {
                 i[x]=1;
                 h+=x;    
                 h1++;   // 共 取走 了幾行
                 s-=(x*l1+l);
             }
             else     // 如果之一行已經取走了
             {
                 printf("0\n");
                 continue;
             }
         }
         else
         {
             if(j[x]==0)
             {
                j[x]=1;
                l+=x;   
                l1++;  // 共取走了幾列
                s-=(x*h1+h);
             }
             else   //如果這一列已經取走了
             {
                 printf("0\n");
                 continue;
             }
         }
         printf("%lld\n",s);
     }
     }
    return 0;
}