古明地枣的袜子

题意
给定 n 个操作，每次询问求在执行 l∼r 的操作后全局最大值，操作为将 a1 ∼ax 加 y，可为负数。

做法
很容易想到 O(n n logn) 的莫队加线段树做法，理论复杂度只可以过这题的，但是由于线段树的超大常数，直接 T 飞了。原本还想尝试分块代替线段树，可以做到 O(n 47 )，但是感觉这题不会这么简单，没有去试，直接去学正解了，结果写完发现有人写莫队过了，于是又想了一下分块，发现普通分块确实不行，但是分块 plus 好像可行。

分块 plus 就是可以做到 O(n31 ) 修改和查询的分块，线段树1的板题写这个比大部分线段树都快，具体可以看这篇文章，这里我简单讲一下。普通分块是直接讲序列分块，但我们其实可以把每一块再次分块（理论上可以一直分下去，但常数会越来越大），每次更新修改所在小块和大块的贡献，查询直接查大块，假设小块块长为 b，大块块长为 B，则这个分块的复杂度为 O( Bn + bB +b) 取 B=b=n 31 时复杂度最优。

接下来看这道题，注意到前缀加只会改变 x 所在块的最大值位置，其余只要在这个块上打一个 tag，然后查询时从后往前扫累加上每个块的 tag 即可。

设小块块长为 B，大块块长为 B 2 ，则复杂度为 O(nBn + B 2 n 2 )，考虑到除法操作较慢， B 取 2 的幂次时可用位运算代替除法操作，综合考虑 B 取 8 最优。但这样任然无法通过，所以直接循环展开，最终代码跑得飞快，优于大部分正解。

但到这里交上去还是会WA，原因是在处理最后面的散块时会统计到 n 以外的数，如果答案小于 0 就会输出 0 。我们将全局的操作单独拎出来，这样若答案小于 0 ，则我们可以取第 n 个数使得答案为 0 ，最后加上全局的操作即可。

这样我们终于用暴力通过了这题，并且因为正解的超大常数，这种方法是优于大部分正解的。

代码

#include<bits/stdc++.h>
#define x first
#define y second
//不要乱开long long
#define ll long long
#define inf 1000000000000000000
#define max(A,B) (A)>(B) ? (A) : (B)
using namespace std;
const int N=5e5+10;
int n,m,pos[N],B=750;
ll w[N],tag1[(N>>3)+10],tag2[(N>>6)+10],mx1[(N>>3)+10],mx2[(N>>6)+10],ans[N],sum[N];
pair <int,int> a[N];
//莫队排序
struct node{
	int l,r,id;
	bool operator < (const node &t) const{
		return pos[l]==pos[t.l] ? ((pos[l]&1) ? r<t.r : r>t.r) : pos[l]<pos[t.l];
	}
}q[N];
//循环展开
#define c(p) tg+=w[p],mx=max(mx,tg)
#define cc(p) mx=max(mx,mx1[p]+tg),tg+=tag1[p]
#define ccc(p) mx=max(mx,mx2[p]+tg),tg+=tag2[p]
void update(int x,int y){
  //下标从0开始，便于分块。
	--x;
	w[x]+=y;
	tag1[x>>3]+=y;
	tag2[x>>6]+=y;
	ll tg=0,mx=-inf;
	int i=(x>>3)<<3;
	c(i+7),c(i+6),c(i+5),c(i+4),c(i+3),c(i+2),c(i+1),c(i);
	mx1[x>>3]=mx;
	tg=0,mx=-inf,i=(x>>6)<<3;
	cc(i+7),cc(i+6),cc(i+5),cc(i+4),cc(i+3),cc(i+2),cc(i+1),cc(i);
	mx2[x>>6]=mx;
}
ll query(){
	ll mx=-inf,tg=0,i=(n-1)>>6;
	for(;i>=7;i-=8) ccc(i),ccc(i-1),ccc(i-2),ccc(i-3),ccc(i-4),ccc(i-5),ccc(i-6),ccc(i-7);
	for(;i>=0;--i) ccc(i);
	return mx;
}
void add(int i){
	update(a[i].x,a[i].y);
}
void del(int i){
	update(a[i].x,-a[i].y);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y,pos[i]=(i-1)/B+1;
		if(a[i].x==n) sum[i]+=a[i].y,a[i].y=0;
		sum[i]+=sum[i-1];
	}
	for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+m+1);
	int L=1,R=0;
  //莫队板子
	for(int i=1;i<=m;i++){
		while(R<q[i].r) add(++R);
		while(L>q[i].l) add(--L);
		while(R>q[i].r) del(R--);
		while(L<q[i].l) del(L++);
		ans[q[i].id]=max((ll)0,query())+sum[q[i].r]-sum[q[i].l-1];
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
	return 0;
}