「SDOI2012」体育课 - 分块+阈值/凸包

题目大意

    又是一节体育课的时间了，有$n$个同学排成了一排。他们都很讨厌排在第一个位置的同学，于是后面的同学中比第一个高的都会产生一个高兴值，这个高兴值等于他的身高减去第一个同学的身高。当然比第一个同学矮的同学产生兴奋值为$0$。
    现在体育老师来了，他拥有神奇的魔法，现在他能做如下的三件事：

1. 询问某段区间高兴值最大的那个是多少。
2. 把某两个同学交换一下位置。
3. 选取一段区间的人，把第一个人身高加上$t$，第二个加上$2t$，第三个加上$3t$以此类推。

    但是体育老师不会数数，于是他找到你了，对于每一个询问，他要你帮他求出那个值。

---

题目分析

一道究极好题！

解法一

考虑对原序列分块，每个块维护如下信息：

• $left,right$：块的边界
• $lazy1$：这个块整体应该增加的量
• $lazy2$：这个块中第$i$个位置应该增加$(i-left)\times lazy2$的量

那么第一个操作就可以列出一个类似斜率的东西，然后就可以维护凸包，二分找出最大值。
第二个操作就暴力交换，暴力重构凸壳。
第三个操作就两头暴力修改，中间打标记。

这样时间复杂度为$O(n\sqrt n\log n)$，听说会被光荣卡常数。

解法二

还是对原序列分块，每个块维护如下信息：

• $left,right$：块的边界
• $lazy1$：这个块整体应该增加的量
• $lazy2$：这个块中第$i$个位置应该增加$(i-left)\times lazy2$的量
• $pos$：这个块当前的最大值位置
• $limit$：再增加$limit$的$lazy2$，这个块的最大值将会发生改变

对于第一个操作，两头暴力查值，中间询问最大值点即可。
对于第二个操作，暴力交换，暴力重构块并重新维护信息。
对于第三个操作，暴力修改两头的值，并重构两头的块并重新维护信息，中间的部分若没超过$limit$就直接打标记，否则打了标记后重构块并重新维护信息。

这样做的时间复杂度是$O((n+q)\sqrt n)$的。
下面我们来证明这个时间复杂度。
首先，若没有第二个操作，每次重构时最大值都会向后移动若干位，显然对于每个块最大值最多移动$O(\sqrt n)$次，然后到达最后端不再移动。
这样均摊下来时间复杂度是$O(n\sqrt n)$的。

然后现在加入第二个操作：

• 若插入的位置在$pos$后，如图所示：
  
  显然对时间复杂度没有影响。
• 若插入的位置在$pos$前，如图所示：
  
  若插入的高度比$pos$的高度小，显然对复杂度没有影响。
  若插入的高度比$pos$高，如图所示：
  
  此时$pos$前的高度一定是升序的，因此只可能多暴力重建一次，对复杂度有$O(\sqrt n)$的贡献。
  因此均摊时间复杂度为$O((n+q)\sqrt n)$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=100005,maxb=325;

int L[maxb],R[maxb],Belong[maxn];
LL a[maxn];

struct Block {
	int left,right,pos;
	LL limit,lazy1,lazy2;
	Block(int l=0,int r=0) {
		left=l,right=r;
		pos=lazy1=lazy2=0;
		limit=LLONG_MAX;
		reset();
	}
	void reset() {
		LL Max=0,delta=lazy1;
		pos=0;
		for(int i=left; i<=right; i++) {
			a[i]+=delta;
			if(a[i]>=Max) {
				Max=a[i];
				pos=i;
				limit=LLONG_MAX;
			} else limit=min(limit,(Max-a[i])/(i-pos));
			delta+=lazy2;
		}
		lazy1=lazy2=0;
	}
	LL get_val(int x) {
		return a[x]+lazy1+lazy2*(x-left);
	}
	LL get_max() {
		return get_val(pos);
	}
};

vector<Block> B;

LL Query(int Left,int Right) {
	int Lb=Belong[Left],Rb=Belong[Right];
	LL ans=0;
	if(Rb-Lb<=1) {
		for(int i=Left; i<=Right; i++)ans=max(ans,B[Belong[i]].get_val(i));
		return ans;
	}
	for(int i=Left; i<=R[Lb]; i++)ans=max(ans,B[Belong[i]].get_val(i));
	for(int i=L[Rb]; i<=Right; i++)ans=max(ans,B[Belong[i]].get_val(i));
	for(int i=Lb+1; i<=Rb-1; i++)ans=max(ans,B[i].get_max());
	return ans;
}

void modify(int Left,int Right,int st,int val) { //局部修改 
	int b=Belong[Left];
	LL delta=1ll*(Left-st+1)*val;
	for(int i=Left; i<=Right; i++) {
		a[i]+=delta;
		delta+=val;
	}
	B[b].reset();
}

void Modify(int Left,int Right,int val) {
	int Lb=Belong[Left],Rb=Belong[Right];
	if(Lb==Rb) {
		modify(Left,Right,Left,val);
		return;
	}
	modify(Left,R[Lb],Left,val);
	modify(L[Rb],Right,Left,val);
	for(int i=Lb+1; i<=Rb-1; i++) {
		if(val<=B[i].limit) {
			B[i].limit-=val;
			B[i].lazy1+=1ll*(L[i]-Left+1)*val;
			B[i].lazy2+=val;
		} else {
			B[i].lazy1+=1ll*(L[i]-Left+1)*val;
			B[i].lazy2+=val;
			B[i].reset();
		}
	}
}

int n,m,BCC=0;

int main() {
	n=Get_Int();
	m=Get_Int();
	int size=sqrt(n);
	for(int i=1; i<=n; i++) {
		a[i]=Get_Int();
		Belong[i]=(i-1)/size;
		if(!L[Belong[i]])L[Belong[i]]=i,BCC++;
		R[Belong[i]]=i;
	}
	for(int i=0; i<BCC; i++)B.push_back(Block(L[i],R[i]));
	for(int i=1; i<=m; i++) {
		int opt=Get_Int(),l=Get_Int(),r=Get_Int();
		if(opt==1) {
			LL ans=Query(l,r);
			if(ans<B[0].get_val(1))puts("0");
			else printf("%lld\n",ans-B[0].get_val(1));
		} else if(opt==2) {
			int Lb=Belong[l],Rb=Belong[r];
			B[Lb].reset();
			if(Lb!=Rb)B[Rb].reset();
			swap(a[l],a[r]);
			B[Lb].reset();
			if(Lb!=Rb)B[Rb].reset();
		} else Modify(l,r,Get_Int());
	}
	return 0;
}