14pts求卡常

#include<bits/stdc++.h>
#define ll long long
#define len 250
using namespace std;
struct node{
	ll mxl,mxr,mx,all;
	node(ll x=0){
		mxl=mxr=mx=max(x,0ll);
		all=x;
	}
	inline node operator+(const node& b)const{
		node re;
		re.mxl=max(mxl,all+b.mxl);
		re.mxr=max(b.mxr,b.all+mxr);
		re.mx=max({mx,b.mx,mxr+b.mxl});
		re.all=all+b.all;
		return re;
	}
	inline void operator+=(const node& b){
		*this=*this+b;
	}
};
int bgt,allt;
struct block{
	int lsh[len+5],s[len+5],lshl;
	node ans[len+5][len+5],hc1[len+5][len+5],hc2[len+5][len+5];
	vector<pair<pair<int,int>,node> > build(int l,int r){
		if(l==r)return vector<pair<pair<int,int>,node> >(1,make_pair(make_pair(s[l],s[l]),node(lsh[s[l]])));
		int mid=(l+r)>>1;
		auto v1=build(l,mid),v2=build(mid+1,r);
		for(auto i:v1)hc1[i.first.first][i.first.second]=i.second;
		for(auto i:v2)hc2[i.first.first][i.first.second]=i.second;
		
		vector<pair<int,int> > v;
		int tp1=l,tp2=mid+1;
		for(int cnt=0;cnt<=r-l;cnt++){
			if(tp1>mid)v.emplace_back(s[tp2++],1);
			else if(tp2>r)v.emplace_back(s[tp1++],0);
			else if(s[tp1]<s[tp2])v.emplace_back(s[tp1++],0);
			else v.emplace_back(s[tp2++],1);
		}
		for(int i=0;i<v.size();i++)s[l+i]=v[i].first;
		int lstv=INT_MIN;
		vector<pair<pair<int,int>,node> > re;
		for(int i=0;i<v.size();i++){
			if(v[i].first!=lstv){
				lstv=v[i].first;
				int mnl=INT_MAX,mnr=INT_MAX,mxl=INT_MIN,mxr=INT_MIN;
				for(int j=i;j<v.size();j++){
					if(v[j].second==0){
						mnl=min(mnl,v[j].first);
						mxl=max(mxl,v[j].first); 
					}else{
						mnr=min(mnr,v[j].first);
						mxr=max(mxr,v[j].first); 
					}
					if(j+1==v.size()||v[j+1].first!=v[j].first){
						re.emplace_back(make_pair(min(mnl,mnr),max(mxl,mxr)),(mnl!=INT_MAX?hc1[mnl][mxl]:node(0))+(mnr!=INT_MAX?hc2[mnr][mxr]:node(0))); 
					} 
				}
			}
		}
		return re;
	}
	void init(int *S){
		bgt=clock();
		for(int i=0;i<len;i++)s[i+1]=lsh[i+1]=S[i];
		sort(lsh+1,lsh+1+len);
		lshl=unique(lsh+1,lsh+1+len)-lsh-1;
		for(int i=1;i<=len;i++)s[i]=lower_bound(lsh+1,lsh+1+lshl,s[i])-lsh;
		auto x=build(1,len);
		for(auto i:x)ans[i.first.first][i.first.second]=i.second;
		allt+=(clock()-bgt);
	}
};
ll ans[100005],tans[100005];
int n,q,s[100005+len],L[100005],R[100005],VL[100005],VR[100005],lshs[100005][2],in[100005+len];
block blk;
vector<pair<int,pair<int,int> > > lshv;
int main(){
	ios::sync_with_stdio(0);
  	//freopen(".in","r",stdin);
  	//freopen(".out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>s[i];
	for(int i=1;i<=q;i++){
		cin>>L[i]>>R[i]>>VL[i]>>VR[i];
		lshv.emplace_back(VL[i],make_pair(i,0));
		lshv.emplace_back(VR[i]+1,make_pair(i,1));
	}
	sort(lshv.begin(),lshv.end());
	for(int i=1;i<=n;i++)in[i]=(i-1)/len;
	for(int u=0;u<=in[n];u++){
		int bl=u*len+1,br=(u+1)*len;
		blk.init(s+bl);
		int tov=1;
		for(auto x:lshv){ 
			while(tov<=blk.lshl&&blk.lsh[tov]<x.first)tov++;
			lshs[x.second.first][x.second.second]=tov;
		}
		for(int id=1;id<=q;id++){
			int l=L[id],r=R[id],vl=VL[id],vr=VR[id];
			if(r<bl||l>br)continue;
			if(l<=bl&&br<=r){
//				ans[id]+=blk.query(vl,vr);
				auto& u=blk.ans[lshs[id][0]][lshs[id][1]-1];
				ans[id]=max(max(ans[id],tans[id]+u.mxl),u.mx);
				tans[id]=max(tans[id]+u.all,u.mxr);
			}else{
				for(int i=max(l,bl);i<=min(r,br);i++){
					if(vl<=s[i]&&s[i]<=vr){
						tans[id]=max(tans[id]+s[i],(ll)s[i]);
						ans[id]=max(ans[id],tans[id]);
					}
				}
			}
		} 
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	cerr<<allt/(double)CLOCKS_PER_SEC<<'\n';
}