数组变换（array.cpp)

题目描述

你的面前有一个长度为 $n$ 的数组。初始时，第 $i$ 个位置的元素为 $i$（即所有位置上的元素依次为从 $1$ 到 $n$ 的正整数）。 接下来，你需要帮我依次完成 $m$ 个操作。每个操作可能是：

• $A$ $p$ $q$，表示你需要修改数组中的所有元素。具体地，第 $i$个位置的元素被修改成 $p*i+q$。
• $B$ $x$ $y$，表示你需要修改数组中的单个元素。具体地，第 $x$ 个位置的元素被修改成 $y$。

其中上述 $p,q,x,y$ 均为整数，每次操作结束后，你需要输出数组中所有元素的和。

输入格式

第一行包含两个数 $n,m$。 接下来$m$行，每行依次表示一个操作，格式为$A$ $p$ $q$ 或者 $B$ $x$ $y$，意义如【题目描述】中所述。

输出格式

输出共 $m$ 行，每行表示每个操作结束后，数组中所有数的和。

样例 #1

样例输入 #1

5 4
B 1 5
A -1 0
A 1 2
A 2 -5

样例输出 #1

19
-15
25
5

提示

样例解释

第 $1$ 次操作结束后，数组变为 ${5, 2, 3, 4, 5}$；

第 $2$ 次操作结束后，数组变为 ${-1, -2, -3, -4, -5}$；

第 $3$ 次操作结束后，数组变为 ${3, 4, 5, 6, 7}$；

第 $4$ 次操作结束后，数组变为 ${-3, -1, 1, 3, 5}$。

数据范围

对于 $20\%$ 的数据，$n\le 100$

另外 $20\%$ 的数据，$n\le 5*10^7,m\le5*10^5$ ,所有操作均为 $B$ 类型

另外 $20\%$ 的数据，$n\le 5*10^7,m\le5*10^5$ ,所有操作均为 $A$ 类型

对于 $100\%$ 的数据，$n \le 5*10^7,m \le 5*10^5,|p|\le1000,|q|、|y|\le 10^9,1\le x\le n$

#include<bits/stdc++.h>
#define int long long 
#define fast register int 

using namespace std;

const int N=5e7+100;

int n,cnt=0,m;

signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin>>n>>m;
	
	for (fast i=1;i<=n;i++){
		cnt+=i;
	}
	
	for (fast i=1;i<=m;i++){
		char x;
		int a,b;
		cin>>x>>a>>b;
		if (x=='A'){
			cout<<cnt*a+n*b<<endl;
		}
		else {
			cout<<cnt+b-a<<endl;
		}
	}
	
	return 0;
}