牛客练习赛28 - B
题目
qn姐姐最好了~
qn姐姐给你了一个长度为n的序列还有m次操作让你玩，
1 l r 询问区间[l,r]内的元素和
2 l r 询问区间[l,r]内的
元素的平方
和
3 l r x 将区间[l,r]内的每一个元素都乘上x
4 l r x 将区间[l,r]内的每一个元素都加上x
输入描述:
第一行两个数n,m
接下来一行n个数表示初始序列
就下来m行每行第一个数为操作方法opt，
若opt=1或者opt=2，则之后跟着两个数为l,r
若opt=3或者opt=4，则之后跟着三个数为l,r,x
操作意思为题目描述里说的
输出描述:
对于每一个操作1,2，输出一行表示答案
输入
复制
5 6
1 2 3 4 5
1 1 5
2 1 5
3 1 2 1
4 1 3 2
1 1 4
2 2 3
输出
复制
15
55
16
41
备注:
对于100%的数据 n=10000,m=200000 (注意是等于号)
保证所有询问的答案在long long 范围内
虽然这道题暴力能卡过去，真的是卡过去的，什么乱七八糟的宏定义、全局变量都要删了。。。
线段树做法：主要是处理x[i] * x[i]的前 n 项和，这里sum[][0]表示前区间和，sum[][1]表示区间内的元素平方和。
这里x = mul * x + add;下面是做各种操作后sum及懒惰标记的变化
乘法 * num:
mul[rt] = mul[rt] * num
add[rt] = add[rt] * num (如果add = 0，那么add * num = 0，如果add = a， 那么 x = (mul * x + a) * num，即 x = mul * num * x + a * num，按照x = mul * x + add的格式)
sum[][0] = sum[][0] * num
sum[][1] = sum[][1] * num * num
加法 + num:
add[rt] += num
sum[][1] += 2 * sum[][0] * num + (r - l + 1) * num * num
这里的sum[][0]是还没改变的，即这里先处理sum[][1]，下面再处理sum[][0]。先来看单个元素的变化，(x + num) * (x + num) = x * x + 2 * num * x + num * num, 然后多个这样的式子相加，即可得上式，也可以解释为什么先处理sum[][1]
sum[][0] += (r - l + 1) * num
最后要记得long long，查询和更新都要下推标记，mul[]要初始化
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
typedef long long LL;
#define Fil(Array, len, num) fill(Array, Array + len, num)
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const double PI = 3.1415926;
const double E = 2.1718281828;
const int MAXN = 10005;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
LL sum[MAXN << 2][3], add[MAXN << 2], mul[MAXN << 2];
void PushUp(LL rt)
{
sum[rt][0] = sum[rt << 1][0] + sum[rt << 1 | 1][0];
sum[rt][1] = sum[rt << 1][1] + sum[rt << 1 | 1][1];
}
void PushDown(LL ln, LL rn, LL rt)
{
if(mul[rt] != 1)
{
mul[rt << 1] *= mul[rt], mul[rt << 1 | 1] *= mul[rt];
sum[rt << 1][1] *= mul[rt] * mul[rt], sum[rt << 1 | 1][1] *= mul[rt] * mul[rt];
sum[rt][0] *= mul[rt], sum[rt << 1 | 1][0] *= mul[rt];
mul[rt] = 1;
}
if(add[rt])
{
add[rt << 1] += add[rt], add[rt << 1 | 1] += add[rt];
sum[rt << 1][1] += 2 * sum[rt << 1][0] * add[rt] + ln * add[rt] * add[rt];
sum[rt << 1 | 1][1] += 2 * sum[rt << 1 | 1][0] * add[rt] + rn * add[rt] * add[rt];
sum[rt << 1][0] += ln * add[rt], sum[rt << 1 | 1][0] += rn * add[rt];
add[rt] = 0;
}
}
void Build(LL l, LL r, LL rt)
{
add[rt] = 0, mul[rt] = 1;
if(l == r)
{
scanf("%lld", &sum[rt][0]);
sum[rt][1] = sum[rt][0] * sum[rt][0];
return ;
}
LL m = (l + r) >> 1;
Build(lson);
Build(rson);
PushUp(rt);
}
void Updata_Add(LL L, LL R, LL num, LL l, LL r, LL rt)
{
if(L <= l && r <= R)
{
sum[rt][1] += 2 * sum[rt][0] * num + (r - l + 1) * num * num;
sum[rt][0] += (r - l + 1) * num;
add[rt] += num;
return ;
}
LL m = (l + r) >> 1;
PushDown(m - l + 1, r - m, rt);
if(L <= m)
Updata_Add(L, R, num, lson);
if(m < R)
Updata_Add(L, R, num, rson);
PushUp(rt);
}
void Updata_mul(LL L, LL R, LL num, LL l, LL r, LL rt)
{
if(L <= l && r <= R)
{
sum[rt][0] *= num;
sum[rt][1] *= num * num;
mul[rt] *= num;
add[rt] *= num;
return ;
}
LL m = (l + r) >> 1;
PushDown(m - l + 1, r - m, rt);
if(L <= m)
Updata_mul(L, R, num, lson);
if(m < R)
Updata_mul(L, R, num, rson);
PushUp(rt);
}
LL Query(LL L, LL R, LL l, LL r, LL rt, LL opt)
{
if(L <= l && r <= R)
{
if(opt == 1)
return sum[rt][0];
if(opt == 2)
return sum[rt][1];
}
LL ans = 0;
LL m = (l + r) >> 1;
PushDown(m - l + 1, r - m, rt);
if(L <= m)
ans += Query(L, R, lson, opt);
if(m < R)
ans += Query(L, R, rson, opt);
return ans;
}
int main()
{
Fil(mul, (MAXN << 2), 1);
LL n, m;
scanf("%d%d", &n, &m);
Build(1, n, 1);
while(m--)
{
LL opt, l, r, x;
scanf("%d%d%d", &opt, &l, &r);
if(opt == 1 || opt == 2)
printf("%lld\n", Query(l, r, 1, n, 1, opt));
else if(opt == 3)
{
scanf("%lld", &x);
Updata_mul(l, r, x, 1, n, 1);
}
else
{
scanf("%lld", &x);
Updata_Add(l, r, x, 1, n, 1);
}
}
return 0;
}