P1967 -- 无敌的妹子

Description

土豪无敌有很多妹子。妹子们站成一排，每个妹子都有一个美貌值。但是无敌的妹子太多了，妹子的“水平”也参差不齐，所以美貌值有正有负。现在无敌要买很多衣服给妹子穿，来改变妹子的美貌值。但是土豪无敌比较忙，又要给上百万个妹子买衣服，只能把看到的衣服都买下来，所以挑选的衣服质量也是层次不齐的（即改变值也是有正有负）。

现在无敌有两种操作：

1）把 [a, b] 间的妹子都加一件美貌值为v的衣服

2）询问 [a, b] 间所有妹子的美貌值的和

Input Format

第一行两个整数 N， Q

N 表示妹子人数

Q 表示操作次数

接下来 一行 N 个整数（-100 到 100 间），为初始序列

接下来 Q 行

第一个数表示操作类型

如果为 0 ，接下来有两个整数 a,b 表示询问的区间

如果为 1，接下来三个整数 a,b,v ，表示 将区间 [a, b] 所有妹子增加v的美貌值（v可以为负数）

Output Format

每行 一个整数，表示回答询问

Sample Input

3 3
1 2 3
0 1 1
1 2 3 1
0 1 3

Sample Output

1
8

Hint

对于所有的数据（也就是说这题是常数题）

N = 1000000 （果然无敌妹纸很多）

Q = 100000

-100 <= v <= 100

1 <= a <= b <= 1000000

（小叶子：为何答案这么多负数。。。搜索帝你的数据也太不给无敌面子了吧。。。。）

（grh：为何中枪的总是同一人？考虑搜索帝如何？）

（xx：我发现这题吸引了好多人 下回背景一定还要是我）

双倍经验题：2025

记得开long long

【题解】

线段树+lazy模板

# include <stdio.h>

using namespace std;

static int lc[8000010],rc[8000010];
static long long w[8000010],lazy[8000010];
static int res[2000010];

# define Orz __attribute__((optimize("-O3")))

Orz inline void fi(int& g) {
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	g=x*f;
}
Orz inline void fa(long long& g) {
	long long x=0;
	int f=1;char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	g=x*f;
}
Orz void build(int l,int r,int x) {
	lc[x]=l;rc[x]=r;lazy[x]=0;
	if(l==r) {
		w[x]=res[l];
		return ;
	}
	int mid=l+r>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	w[x]=w[x<<1]+w[x<<1|1];
}
Orz inline void add(int x,int ql,int qr,long long del) {
	int l=lc[x],r=rc[x];
	if(ql==l&&r==qr) {
		lazy[x]+=del;
		return ;
	}
	int mid=l+r>>1;
	if(ql<=mid&&qr>mid) {
		add(x<<1,ql,mid,del);
		add(x<<1|1,mid+1,qr,del);
	} else if(ql>mid) add(x<<1|1,ql,qr,del);
	else add(x<<1,ql,qr,del);
	w[x]+=del*(qr-ql+1);
}
long long ans;
Orz inline void query(int x,int ql,int qr,long long laz) {
	int l=lc[x],r=rc[x];
	if(ql==l&&r==qr) {
		ans+=(laz+lazy[x])*(r-l+1)+w[x];
		return;
	}
	int mid=l+r>>1;
	if(ql<=mid&&qr>mid) {
		query(x<<1,ql,mid,laz+lazy[x]);
		query(x<<1|1,mid+1,qr,laz+lazy[x]);
	} else if(ql>mid) query(x<<1|1,ql,qr,laz+lazy[x]);
	else query(x<<1,ql,qr,laz+lazy[x]);
}

int n,q;

Orz int main() {
	fi(n),fi(q);
	for (register int i=1;i<=n;++i) fi(res[i]);
	build(1,n,1);
	while(q--) {
		int A,B,C;
		fi(A),fi(B),fi(C);
		if(A==0) {
			ans=0;
			query(1,B,C,0);
			printf("%lld\n",ans);
		} else {
			long long D;
			fa(D);
			add(1,B,C,D);
			//for (int i=1;i<=6;++i)printf("left:%d,right:%d,    w:%lld,lazy:%lld\n",lc[i],rc[i],w[i],lazy[i]);
		}
	}
}