Gym - 100851A Adjustment Office 预处理模拟

在牛客上做的gym某一水题 Adjustment Office

题目描述

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.

输入描述

The first line of the input contains two integers n and q ($1\le n\le 10^6,1\le q\le 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).

输出描述

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

题意

有一个n*n的矩阵，任意格子(x,y)的大小为x+y。 现可以查询q次，查询某行或某列的和，输出后再把该行或该列全部置零。

题解

因为$1\le n\le 10^6$，所以可以设一个$mat[2][10^6+1]$的数组，分别表示行列是否被查询置零过，维护第一行和第一列的和，答案是再加上当前行或列相对第一行或列的大小*当前还剩下多少行或列未被查询置零。

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" const int MAX=1e6+7; ll mat[2][MAX],sum_row,sum_col,nr,nc; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); ll n,q; cin>>n>>q; memset(mat,sizeof(mat),0); nr=nc=n; sum_row=sum_col=n*(n+1)/2; //第一行或列的和 char s[5];ll d; while(q--){ cin>>s>>d; if(s[0]=='R'){ if(mat[0][d])cout<<0; else { mat[0][d]=1; cout<<d*nr+sum_row; nc--; //当前还有nc列不是空白 sum_col-=d; //当前第一列的和 } } else if(s[0]=='C'){ if(mat[1][d])cout<<0; else { mat[1][d]=1; cout<<d*nc+sum_col; nr--; //当前还有nr行不是空白 sum_row-=d; //当前第一行的和 } } cout<<endl; } return 0; }