记录编号	385664	评测结果	AAAAAAAAAA
题目名称	[SDOI 2012] 体育课	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	7.335 s
提交时间	2017-03-22 09:00:49	内存使用	6.99 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>

using namespace std;

typedef long long LL;

void read(LL &x) {
    char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = x*10+c-'0';
    flag?x=-x:x;
}

void read(int &x) {
    char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = x*10+c-'0';
    flag?x=-x:x;
}

const LL inf = ~0u>>2;
void FRE();

void upval(LL &a,const LL &b) {if(a<b) a=b;}

#define MAXX 101000
#define N 600
int n,m;
LL h[MAXX],bsf[N];
int bsiz,bl[N],br[N],bk[MAXX];
LL lazy1[N],lazy2[N];
struct pii{LL h,pos;pii(LL h=0,LL pos=0):h(h),pos(pos){}} st[N][N];
int top[N];

void reset(int bk) {
	bsf[bk] = inf; top[bk] = 0;
	for (LL i = bl[bk]; i <= br[bk]; i++) {
		while(top[bk] && st[bk][top[bk]].h <= h[i]) top[bk]--;
		st[bk][++top[bk]] = pii(h[i],i);			
	}
	for (LL i = 2; i <= top[bk]; i++)
	  bsf[bk] = min(bsf[bk], 
	     ((st[bk][1].h-st[bk][i].h)/(st[bk][i].pos-st[bk][1].pos)));
}

void push_down(int bk) {
	if(!lazy1[bk] && !lazy2[bk]) return;
	for (LL i = bl[bk]; i <= br[bk]; i++)
	 h[i] += lazy1[bk]+i*lazy2[bk];
	lazy1[bk] = lazy2[bk] = 0;
}

void Swap(int x,int y) {
	push_down(bk[x]); push_down(bk[y]);
	swap(h[x],h[y]);
	reset(bk[x]); reset(bk[y]);
}

LL Max(int x,int y) {
	int li = min(br[bk[x]],y); LL mx = 0;
	push_down(bk[x]);
	for (int i = x; i <= li; i++) upval(mx,h[i]);
	reset(bk[x]);
	for (int i = bk[x]+1; i < bk[y]; i++) {
	  	if(lazy2[i] >= bsf[i] && lazy2[i]) {
			push_down(i);
			reset(i);
		}
		upval(mx,st[i][1].h+lazy1[i]+lazy2[i]*st[i][1].pos);
	}
	if(bk[x] != bk[y]) {
		push_down(bk[y]);
		for (int i = bl[bk[y]]; i <= y; i++) upval(mx,h[i]);
		reset(bk[y]);
	}
    mx -= h[1]+lazy1[bk[1]]+lazy2[bk[1]];
    return mx>0 ? mx:0;
}

void Add(int x,int y,LL t) {
	int li = min(br[bk[x]],y); LL L = x-1;
	push_down(bk[x]);
	for (int i = x; i <= li; i++) h[i] += (i-L)*t;
	reset(bk[x]);
	for (int i = bk[x]+1; i < bk[y]; i++) 
		lazy1[i] += -L*t,lazy2[i] += t;
	if(bk[x] != bk[y]) {
		push_down(bk[y]);
		for (int i = bl[bk[y]]; i <= y; i++) h[i] += (i-L)*t;
		reset(bk[y]);
	}
}

int main() {
	FRE();
	read(n); read(m);
	bsiz = sqrt(n+0.5);
    for (int i = 1; i <= n; i++) {
       read(h[i]);
       bk[i] = i/bsiz+1;
       if(!bl[bk[i]]) bl[bk[i]] = i;
       br[bk[i]] = i;
	} 
	for (int i = 1; i <= bk[n]; i++) reset(i);
	for (int i = 1,tp,x,y,t; i <= m; i++) {
		read(tp); read(x); read(y);
		if(tp == 1) printf("%lld\n",Max(x,y));
		else if(tp == 2) Swap(x,y);
		else read(t),Add(x,y,t);
	}
	return 0;
}

void FRE() {
	assert(freopen("sdoi12_line.in","r",stdin));
    assert(freopen("sdoi12_line.out","w",stdout));
}