记录编号	312347	评测结果	WWWWWWWWWW
题目名称	[EZOI 2016]源氏的数学课	最终得分	0
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	1.959 s
提交时间	2016-09-26 10:01:47	内存使用	5.11 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=100010;
struct oper{
	int x,id;
	LL y;//if query,then y means *= 1 or -1
	bool d;//0:modify 1:query
	bool operator<(const oper &a)const{return x<a.x;}
}a[maxn<<1];
void CDQ(int,int);
int n,m,d;
LL b[maxn],c[maxn],ans[maxn]={0},tmpb,tmpc;
int main(){
#define MINE
#ifdef MINE
	freopen("overwatch.in","r",stdin);
	freopen("overwatch.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&b[i]);
		c[i]=b[i]*(LL)(n-i+1);
	}
	for(int i=1;i<=n;i++){
		b[i]+=b[i-1];
		c[i]+=c[i-1];
	}
	m<<=1;
	for(int i=1;i<m;i+=2){
		scanf("%d",&d);
		a[i].id=a[i+1].id=i;
		if(d==1){
			scanf("%d%lld",&a[i].x,&a[i].y);
			a[i].d=a[i+1].d=false;
			a[i+1].x=a[i].x;
			a[i+1].y=0ll;
		}
		else{
			scanf("%d%d",&a[i].x,&a[i+1].x);
			a[i].x--;
			ans[i]+=c[a[i+1].x]-c[a[i].x]-(b[a[i+1].x]-b[a[i].x])*(LL)(n-a[i+1].x);
			a[i].y=-1;
			a[i+1].y=1;
			a[i].d=a[i+1].d=true;
		}
	}
	
	CDQ(1,m);
	for(int i=1;i<=m;i++)if(ans[i])printf("%lld\n",ans[i]);
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
void CDQ(int l,int r){
	if(l>=r)return;
	int mid=(l+r)>>1;
	CDQ(l,mid);
	tmpb=tmpc=0;
	sort(a+l,a+r+1);
	for(int i=l;i<=r;i++){
		if(a[i].d){
			if(a[i].id>mid)ans[a[i].id]+=a[i].y*(tmpc-tmpb*(LL)(n-a[i].x));
		}
		else if(a[i].id<=mid){
			tmpb+=a[i].y;
			tmpc+=a[i].y*(LL)(n-a[i].x+1);
		}
	}
	CDQ(mid+1,r);
}