【Ynoi2013】D2T2
分块，分治。
题目大意：
给定一个长度为 $n$ 的序列，多次询问，每次给出 $l,r,L,R$，需要求出，只保留权值在 $[L,R]$ 中的数，其他数的权值为 $0$ 时，区间 $[l,r]$ 的最大子段和。
题解：
第七分块太难了就先来写一下这个。
结果交了 59 发才过……
有一个非常简单的做法，将值域离散化之后对值域进行莫队，用线段树维护最大子段和。时间复杂度为 $O(n\sqrt m\log n)$。
考虑更优的做法。如果我们有一种时间复杂度 $O(n^2)$ 的做法求出一个长度为 $n$ 的序列的所有不同值域限制下的全局最大子段和，那我们就可以通过分块将这个复杂度降为 $O(n\sqrt n)$。
关于最大子段和的问题，分治是一个常见的思路。由于长度为 $n$ 的序列，只有 $O(n^2)$ 个本质不同的值域限制，所以我们希望每层都能 $O(n^2)$ 合并信息。这样分治的复杂度为 $T(n)=2T(\frac n 2)+O(n^2)$。根据主定理即可得到 $T(n)=O(n^2)$。
我们考虑已知两个子区间的本质不同的值以及限制，如何合并为这一层的答案。对于合并上来的 $[L,R]$，我们需要在左、右分别找到区间 $[L_1,R_1]$ 和 $[L_2,R_2]$，其中 $[L_1,R_1]$ 和 $[L_2,R_2]$ 都是被 $[L,R]$ 包含的最大区间。那么这两个区间的最大子段和信息进行合并，即可得到 $[L,R]$ 的最大子段和信息。
我们考虑预处理对每个 $L$，左、右区间第一个大于等于 $L$ 的值。同样，对于 $R$，预处理左、右区间第一个小于等于 $R$ 的值。由于我们是要选最大的两个区间合并，那么两个端点和 $L,R$ 最接近的一定是最大的。这样就可以直接 $O(n^2)$ 枚举 $L,R$，然后 $O(1)$ 找到两个需要合并的区间，进行合并。
分治的时空复杂度均为 $O(n^2)$，考虑对序列分块，每个块的大小为 $O(\sqrt n)$，则对每个块进行分治的时间复杂度为 $O(n)$。分治花费的时间复杂度为 $O(n\sqrt n)$。
对于一个询问，拆成整块的和边角的。对于边界的显然可以 $O(\sqrt n)$ 解决。对于整块的，我们已经知道所有本质不同的值域限制的答案，那么对于值域限制为 $[L,R]$ 的询问，我们要找到被它包含的最大的区间的信息。那么和上面的处理方式相同，对每个 $L$ 和 $R$ 分别找到最靠近的端点即可。这里为了保证复杂度，必须用双指针处理，否则时间复杂度将退化为 $O(m\sqrt n\log n)$。
由于直接存储所有块的信息需要 $O(n\sqrt n)$ 的空间，无法接受。所以我们对询问离线，在一个块的信息处理完后，直接把这个块对所有询问的贡献都更新掉。这样空间复杂度为 $O(n)$。
时间复杂度为 $O((n+m)\sqrt n)$。
注意实现时的常数。
Code：
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<functional>
using namespace std;
typedef long long LoveLive;
typedef unsigned long long ULL;
#define bel(x)((x-1)/siz+1)
const int N=1e5+5,siz=200,B=siz+2;
char buf[(int)1e7],*ss=buf;
inline int init(){buf[fread(buf,1,(int)1e7-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline int readint(){
int d=0;bool f=0;
while(!isdigit(*ss))f=*ss++=='-';
while(isdigit(*ss))d=d*10+(*ss++^'0');
return f?-d:d;
}
char bwf[5000005],*ww=bwf;
int xx[24];
inline void print(LoveLive x){
static int*q=xx;
if(!x)*ww++='0';else{
for(;x;x/=10)*q++=(x%10)^'0';
while(q!=xx)*ww++=*--q;
}
*ww++='\n';
}
int n,m,A[N],a[B],beL[N],beR[N],b[B],tmp[B],vec[B];
struct data{
LoveLive lmax,rmax,mx,sum;
inline data(LoveLive a,LoveLive b,LoveLive c,LoveLive d):lmax(a),rmax(b),mx(c),sum(d){}
inline data(){lmax=rmax=mx=sum=0;}
inline data(LoveLive x){sum=x,lmax=rmax=mx=max(x,0LL);}
inline data operator+(const data&rhs)const{
return(data){max(lmax,sum+rhs.lmax),max(rhs.rmax,rhs.sum+rmax),max({mx,rhs.mx,rmax+rhs.lmax}),sum+rhs.sum};
}
inline void operator+=(const data&rhs){mx=max({mx,rhs.mx,rmax+rhs.lmax}),lmax=max(lmax,sum+rhs.lmax),rmax=max(rhs.rmax,rhs.sum+rmax),sum+=rhs.sum;}
}ans[N],p[65536],Lt[65536],Rt[65536];
ULL lf[N],rg[N];
int IT[B];
struct que{
int l,r,L,R;
}q[N];
struct info{
int zt;
data s;
}D[600000],*ed;
void solve(int l,int r,info*V,int&tot){
if(l==r){
V[tot++]=(info){a[l]<<8|a[l],data(vec[a[l]])};
return;
}
const int mid=l+r>>1;
info*L=ed;ed+=(mid-l+1)*(mid-l+2);
info*R=ed;ed+=(r-mid+1)*(r-mid);
int cntL=0,cntR=0;
solve(l,mid,L,cntL),solve(mid+1,r,R,cntR);
int i=l,j=mid+1,t=l,k;
while(i<=mid&&j<=r)if(b[i]<=b[j])tmp[t++]=b[i++];else tmp[t++]=b[j++];
while(i<=mid)tmp[t++]=b[i++];while(j<=r)tmp[t++]=b[j++];
for(int i=0;i<cntL;++i)Lt[L[i].zt]=L[i].s;
for(int i=0;i<cntR;++i)Rt[R[i].zt]=R[i].s;
static int _L[B],_R[B],L_[B],R_[B];
t=l,k=mid+1;
for(int i=l;i<=r;++i){
while(t<=mid&&b[t]<tmp[i])++t;
while(k<=r&&b[k]<tmp[i])++k;
_L[i]=t<=mid?b[t]:114514,L_[i]=k<=r?b[k]:114514;
}
t=mid,k=r;
for(int i=r;i>=l;--i){
while(t>=l&&b[t]>tmp[i])--t;
while(k>mid&&b[k]>tmp[i])--k;
_R[i]=t>=l?b[t]:0,R_[i]=k>mid?b[k]:0;
}
for(int i=l;i<=r;++i)b[i]=tmp[i];
for(int i=l;i<=r;++i)if(i==l||b[i]!=b[i-1])
for(int j=i;j<=r;++j)if(j==i||b[j]!=b[j-1]){
const data&ztL=Lt[_L[i]<<8|_R[j]],&ztR=Rt[L_[i]<<8|R_[j]];const int X=b[i]<<8|b[j];
if(_L[i]<=_R[j]&&L_[i]<=R_[j])V[tot++]=(info){X,ztL+ztR};else
if(_L[i]<=_R[j])V[tot++]=(info){X,ztL};else
if(L_[i]<=R_[j])V[tot++]=(info){X,ztR};
}
ed=L;
}
inline data get(int l,int r,const int&L,const int&R){
LoveLive lm=0,rm=0,sum=0,mx=0,s=0;
for(int i=l;i<=r;++i)if(lm<(s+=(L<=A[i]&&A[i]<=R)?A[i]:0))lm=s;
s=0;
for(int i=r;i>=l;--i)if(rm<(s+=(L<=A[i]&&A[i]<=R)?A[i]:0))rm=s;
s=0;
for(int i=l;i<=r;++i){
const int x=(L<=A[i]&&A[i]<=R)?A[i]:0;
sum+=x,s+=x;
if(mx<s)mx=s;
if(s<0)s=0;
}
return data(lm,rm,mx,sum);
}
int main(){
n=readint(),m=readint();
for(int i=1;i<=n;++i)A[i]=readint();
for(int i=1;i<=m;++i){
int l=readint(),r=readint(),L=readint(),R=readint();
q[i]=(que){l,r,L,R},L+=1000000000,R+=1000000000,lf[i]=(ULL)L<<32|i,rg[i]=(ULL)R<<32|i;
}
sort(lf+1,lf+m+1),sort(rg+1,rg+m+1,greater<ULL>());
for(int l=siz+1,r=2*siz;r<=n;l+=siz,r+=siz){
int len=r-l+1;
for(int i=l;i<=r;++i)vec[i-l]=A[i];
int Val=len;
sort(vec,vec+len);
Val=unique(vec,vec+len)-vec;
for(int i=l;i<=r;++i)a[i-l]=lower_bound(vec,vec+Val,A[i])-vec;
memcpy(b,a,sizeof a);
int tp=0;
ed=D+len*(len+1);
solve(0,len-1,D,tp);
for(int i=0;i<tp;++i)p[D[i].zt]=D[i].s;
int it1=0,it2=Val-1;
for(int i=1;i<=m;++i){
while(it1<Val&&(lf[i]>>32)>vec[it1]+1000000000)++it1;
while(~it2&&(rg[i]>>32)<vec[it2]+1000000000)--it2;
beL[(int)lf[i]]=it1,beR[(int)rg[i]]=it2;
}
for(int i=1;i<=m;++i)if(beL[i]<=beR[i]&&q[i].l<l&&r<q[i].r)ans[i]+=p[beL[i]<<8|beR[i]];
}
for(int i=1;i<=m;++i){
int l=q[i].l,r=q[i].r;
const int bL=bel(l),bR=bel(r);
if(bL==bR)print(get(l,r,q[i].L,q[i].R).mx);else
print((get(l,bL*siz,q[i].L,q[i].R)+ans[i]+get((bR-1)*siz+1,r,q[i].L,q[i].R)).mx);
}
fwrite(bwf,ww-bwf,1,stdout);
return 0;
}