记录编号	244199	评测结果	AAAAAATTTTTTTTTTTTTT
题目名称	1897.[国家集训队2011]工作评估	最终得分	30
用户昵称	mikumikumi	是否通过	未通过
代码语言	C++	运行时间	42.007 s
提交时间	2016-03-31 17:20:22	内存使用	4.33 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int SIZEP=250,SIZEN=50010,INF=0x7fffffff/2;
class poi
{
public:
	int l,r;
	int G,S;
	void print()
	{
		cout<<l<<" "<<r<<endl;
		cout<<"G:"<<G<<" "<<"S:"<<S<<endl;
	}
};
int D[SIZEN],L[SIZEN],N,M;
int get(int X,int a,int b)
{
	int tem=X;
	for(int i=a;i<=b;i++)
		tem=min(tem+D[i],L[i]);
	return tem;
}
int sum(int a,int b)
{
	int tem=0;
	for(int i=a;i<=b;i++)
		tem+=D[i];
	return	tem;
}
bool cmp(poi a,poi b)
{
	if(a.G==b.G) return a.S>b.S;
	return a.G>b.G;
}
class miku//块
{
    public:
	poi s[SIZEP];
	poi L[SIZEP];
	poi R[SIZEP];
	int st,en;
	int size,siza,sizb;
	int G,S;
	void make()
	{
		static poi P[SIZEN];
		int tot=0;
		for(int i=st;i<=en;i++)
		{
			for(int j=i;j<=en;j++)
			{
				++tot;
				P[tot].G=get(INF,i,j);
				P[tot].S=sum(i,j);
				P[tot].l=i;P[tot].r=j;
				if(i==st&&j==en) S=P[tot].S,G=P[tot].G;
			}
		}
		sort(P+1,P+1+tot,cmp);
		size=0;
		s[++size]=P[1];
		for(int i=2;i<=tot;i++) if(P[i].S>s[size].S) s[++size]=P[i];
		siza=sizb=0;
		for(int i=1;i<=tot;i++) 
		{
			if(P[i].l==st) 
			{
				if(siza==0||L[siza].S<P[i].S) L[++siza]=P[i];
			}
			if(P[i].r==en)
			{
				if(sizb==0||R[sizb].S<P[i].S) R[++sizb]=P[i];
			}
		}
	}
	int sum3(int x)//二分
	{
		int l=1,r=size;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(s[mid].G>s[mid].S+x) l=mid+1;
			else r=mid;
		}
		int re=min(s[l].G,s[l].S+x);
		if(l>1) re=max(re,min(s[l-1].G,s[l-1].S+x));
		if(l<siza) re=max(re,min(s[l+1].G,s[l+1].S+x));
		return re;
	}
	int sum1(int x)//二分
	{
		int l=1,r=siza;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(L[mid].G>L[mid].S+x) l=mid+1;
			else r=mid;
		}
		int re=min(L[l].G,L[l].S+x);
		if(l>1) re=max(re,min(L[l-1].G,L[l-1].S+x));
		if(l<siza) re=max(re,min(L[l+1].G,L[l+1].S+x));
		return re;
	}
	int sum2(int x)//二分
	{
		int l=1,r=sizb;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(R[mid].G>R[mid].S+x) l=mid+1;
			else r=mid;
		}
		int re=min(R[l].G,R[l].S+x);
		if(l>1) re=max(re,min(R[l-1].G,R[l-1].S+x));
		if(l<sizb) re=max(re,min(R[l+1].G,R[l+1].S+x));
		return re;
	}
	void print()
	{
		cout<<st<<" "<<en<<endl;
		cout<<"size: "<<size<<endl;
		for(int i=1;i<=size;i++) s[i].print();
		cout<<"siza: "<<siza<<endl;
		for(int i=1;i<=siza;i++) L[i].print();
		cout<<endl;
		cout<<"sizb: "<<sizb<<endl;
		for(int i=1;i<=sizb;i++) R[i].print();
	}
}E[SIZEP];
void read()
{
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++) scanf("%d",&D[i]);
	for(int i=1;i<=N;i++) scanf("%d",&L[i]);
}
int best;
int piece;
void prepare()
{
	best=sqrt(N+1.0);
	int tot=1;
	E[tot].st=E[tot].en=1;
	for(int i=2;i<=N;i++)
	{
		//cout<<tot<<" "<<E[tot].en-E[tot].st+1<<endl;
		if(E[tot].en-E[tot].st+1==best)
		{
			E[tot].make();
			tot++;
			E[tot].st=E[tot].en=i;
		}
		E[tot].en=i;
	}
	E[tot].make();
	piece=tot;
	//for(int i=1;i<=tot;i++) E[i].print();
}
int Calc(int st,int ed,int X)
{
	int k1=(st-1)/best+1,k2=(ed-1)/best+1;
	miku A;
	//cout<<k1<<" "<<k2<<endl;
	if(k1==k2)
	{
		A.st=st,A.en=ed;
		A.make();
		//A.print();
		X=max(X,A.sum3(X));
		return X;
	}
	A.st=st,A.en=E[k1].en;
	A.make();
	//A.print();
	int ans=max(X,A.sum3(X));
	int Y=max(X,A.sum2(X));
	//cout<<Y<<endl;
	for(int i=k1+1;i<k2;i++)
	{
		ans=max(ans,E[i].sum3(X));
		ans=max(ans,E[i].sum1(Y));
		Y=min(Y+E[i].S,E[i].G);
		Y=max(Y,E[i].sum2(X));
		Y=max(Y,X);
	}
	A.st=E[k2].st,A.en=ed;
	A.make();
	ans=max(ans,A.sum1(Y));
	ans=max(ans,A.sum3(X));
	return ans;
}
void work()
{
	int st,ed,X;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d%d",&st,&ed,&X);
		int ans=Calc(st,ed,X);
		printf("%d\n",ans);
	}
}
int main()
{
	freopen("nt2011_zej_b.in","r",stdin);
	freopen("nt2011_zej_b.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}