题目描述

小明的叔叔是一家工厂的厂长。叔叔的工厂有 n 个车间，编号为1～n。

管理工厂是很麻烦的事情，特别是在多次调整机器以及员工之后，统计总生产量更是难 事。

第 i 个车间在刚开始的时候机器生产力为ai，有bi 个员工，那么这个车间的生产力就为 ai*bi。

工厂的总生产力定义为所有车间的生产力之和。

接下来的m 天，每天叔叔就会调整一段区间的车间。

有两种调整：

第一种，是对于一段区间[l,r]的每一个车间重新分配每个车间的工人数为 x。

第二种，是对于一段区间[l,r]的每一个车间增加机器生产力x。

现在，小明的叔叔想知道每天调整之后工厂的生产量变为多少。

输入

第一行两个整数n 和m，表示车场数以及天数。

接下来n 行，每行描述一个车间。

第 i+1 行描述第i 个车间，包括两个整数ai 和 bi，意义如题目所述。

接下来m 行，每一行表示一个修改操作。

Set l r x 表示对于一段区间[l,r]的每一个车间重新分配每个车间的工人数为 x。

Add l r x 表示对于一段区间[l,r]的每一个车间增加机器生产力 x。

输入

第一行两个整数n 和m，表示车场数以及天数。

接下来n 行，每行描述一个车间。

第 i+1 行描述第i 个车间，包括两个整数ai 和 bi，意义如题目所述。

接下来m 行，每一行表示一个修改操作。

Set l r x 表示对于一段区间[l,r]的每一个车间重新分配每个车间的工人数为 x。

Add l r x 表示对于一段区间[l,r]的每一个车间增加机器生产力 x。

样例输入

4 4 2 1 4 3 6 5 8 7 Set 1 3 2 Add 2 3 1 Add 3 3 2 Set 1 4 2 样例输出

80 84 88 48

#include<bits/stdc++.h>
using namespace std;
long long n, m, i, j, k, x, y, zuo[200000], you[200000], z, ans;
char aa[114514];
struct bb{
	long long le, re, ren, jiqi, add1, add2;
}tree[500000];
void build(long long p, long long xx, long long yy){
	tree[p].le = xx;
	tree[p].re = yy;
	if(xx == yy){
		tree[p].ren = you[xx];
		tree[p].add1 = you[xx];
		tree[p].jiqi = zuo[xx];
		return;
	}
	long long mid = (xx + yy) / 2;
	build(p * 2, xx, mid);
	build(p * 2 + 1, mid + 1, yy);
	tree[p].ren = tree[p * 2].ren + tree[p * 2 + 1].ren;
	tree[p].jiqi = tree[p * 2].jiqi + tree[p * 2 + 1].jiqi;
}
void pushdown1(long long p){
	long long mid = (tree[p].le + tree[p].re) / 2;
	if(tree[p].add1 != 0){
		tree[p * 2].ren = tree[p].add1 * (tree[p * 2].re - tree[p * 2].le + 1);
		tree[p * 2 + 1].ren = tree[p].add1 * (tree[p * 2 + 1].re - tree[p * 2 + 1].le + 1);
		tree[p * 2].add1 = tree[p].add1;
		tree[p * 2 + 1].add1 = tree[p].add1;
		tree[p].add1 = 0;
	}
}
void pushdown2(long long p){
	long long mid = (tree[p].le + tree[p].re) / 2;
	if(tree[p].add2 != 0){
		tree[p * 2].jiqi += tree[p].add2 * (tree[p * 2].re - tree[p * 2].le + 1);
		tree[p * 2 + 1].jiqi += tree[p].add2 * (tree[p * 2 + 1].re - tree[p * 2 + 1].le + 1);
		tree[p * 2].add2 += tree[p].add2;
		tree[p * 2 + 1].add2 += tree[p].add2;
		tree[p].add2 = 0;
	}
}
void change1(long long p, long long xx, long long yy, long long zz){
	if(tree[p].re < xx || tree[p].le > yy) return;
	if(tree[p].le >= xx && tree[p].re <= yy){
		tree[p].add1 = zz;
		tree[p].ren = zz * (tree[p].re - tree[p].le + 1);
		return;
	}
	pushdown1(p);
	long long mid = (tree[p].le + tree[p].re) / 2;
	if(xx <= mid) change1(p * 2, xx, yy, zz);
	if(yy > mid)change1(p * 2 + 1, xx, yy, zz);
	tree[p].ren = tree[p * 2 + 1].ren + tree[p * 2].ren;
}
void change2(long long p, long long xx, long long yy, long long zz){
	if(tree[p].re < xx || tree[p].le > yy) return;
	if(tree[p].le >= xx && tree[p].re <= yy){
		tree[p].add2 += zz;
		tree[p].jiqi += zz * (tree[p].re - tree[p].le + 1);
		return;
	}
	pushdown2(p);
	long long mid = (tree[p].le + tree[p].re) / 2;
	if(xx <= mid) change2(p * 2, xx, yy, zz);
	if(yy > mid) change2(p * 2 + 1, xx, yy, zz);
	tree[p].jiqi = tree[p * 2 + 1].jiqi + tree[p * 2].jiqi;
}
long long ask1(long long p, long long xx, long long yy){
	if(tree[p].re < xx || tree[p].le > yy) return 0;
	if(tree[p].le >= xx && tree[p].re <= yy){
		return tree[p].ren;
	}
	pushdown1(p);
	long long val = 0, mid = (tree[p].le + tree[p].re) / 2;
	if(xx <= mid) val += ask1(p * 2, xx, yy);
	if(yy > mid) val += ask1(p * 2 + 1, xx, yy);
	return val;
}
long long ask2(long long p, long long xx, long long yy){
	if(tree[p].re < xx || tree[p].le > yy) return 0;
	if(tree[p].le >= xx && tree[p].re <= yy){
		return tree[p].jiqi;
	}
	pushdown2(p);
	long long val = 0, mid = (tree[p].le + tree[p].re) / 2;
	if(xx <= mid) val += ask2(p * 2, xx, yy);
	if(yy > mid) val += ask2(p * 2 + 1, xx, yy);
	return val;
}
void qujian(int p, int xx, int yy){
	if(tree[p].re < xx || tree[p].le > yy) return;
	if(tree[p].le >= xx && tree[p].re <= yy){
		if(tree[p].add1 > 0){
			ans -= tree[p].add1 * ask2(1, tree[p].le, tree[p].re);
			return;
		} 
	}
	pushdown1(p);
	long long mid = (tree[p].le + tree[p].re) / 2;
	if(xx <= mid) qujian(p * 2, xx, yy);
	if(yy > mid) qujian(p * 2 + 1, xx, yy);
}
int main(){
	scanf("%lld%lld", &n, &m);
	for(i=1; i<=n; i++){
		scanf("%lld%lld", &zuo[i], &you[i]);
		ans += zuo[i] * you[i];
	}
	build(1, 1, n);
	for(i=1; i<=m; i++){
		scanf("%s%lld%lld%lld", aa, &x, &y, &z);
		if(aa[0] == 'A'){
			ans += z * ask1(1, 1, n);
			change2(1, x, y, z);
		}
		else{
			qujian(1, 1, n);
			ans += z * ask2(1, 1, n);
			change1(1, x, y, z);
		}
		printf("%lld\n", ans);
	}
	return 0;
}
/*
4 4 
2 1 
4 3 
6 5 
8 7 
Set 1 3 2
Add 2 3 1
Add 3 3 2
Set 1 4 2

4 1
2 1 
4 3 
6 5 
8 7 
Set 1 3 2

4 1
2 1 
4 3 
6 5 
8 7 
Add 2 3 1
*/