洛谷题解

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 200005
#define int long long
using namespace std;
int n,m,a[N],b[N],t,lg[N],c[2][N],o[N],u[N],T,s[N],sta[N],top,pr[N],nx[N],ans[N];
struct node{int s,t,u;}q[N];
namespace st1{
	int f[N][20];
	inline int ck(int x,int y){if(b[x]<b[y])return x;return y;}
	int ask(int l,int r){int cur=lg[r-l+1];return ck(f[l][cur],f[r-(1<<cur)+1][cur]);}
	void init(){
		rep(i,1,n+1)f[i][0]=i;
		rep(j,1,t)rep(i,1,n-(1<<j)+2)f[i][j]=ck(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
}
namespace st2{
	int f[N][20];
	inline int ck(int x,int y){if(a[x]>a[y])return x;return y;}
	int ask(int l,int r){int cur=lg[r-l+1];return ck(f[l][cur],f[r-(1<<cur)+1][cur]);}
	void init(){
		rep(i,1,n+1)f[i][0]=i;
		rep(j,1,t)rep(i,1,n-(1<<j)+2)f[i][j]=ck(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
}
inline void add(int op,int x,int val){for(;x<=T;x+=x&-x)c[op][x]+=val;}
inline int ask(int op,int x){int sum=0;for(;x;x-=x&-x)sum+=c[op][x];return sum;}
inline void change(int op,int l,int r,int k){
	if(l>r)return;
	l=lower_bound(u+1,u+T+1,l)-u;
	r=upper_bound(u+1,u+T+1,r)-u-1;
	add(op,l,k);add(op,r+1,-k);
}
vector<node>w[N];vector<int>dl[N];
signed main(){
	scanf("%lld%lld",&n,&m);t=log2(n+1);
	lg[0]=-1;rep(i,1,n)lg[i]=lg[i>>1]+1;
	rep(i,1,n)scanf("%lld",&a[i]),s[i+1]=s[i]+a[i];
	rep(i,1,n)scanf("%lld",&b[i]);
	st1::init();st2::init();
	rep(i,1,m)scanf("%lld%lld%lld",&q[i].s,&q[i].t,&q[i].u),o[i]=q[i].u;
	sort(o+1,o+m+1);rep(i,1,m)if(o[i]!=o[i-1])u[++T]=o[i];
	//printf("aa ");rep(i,1,n+1)printf("%lld ",s[i]);putchar('\n');
	//printf("bb ");rep(i,1,T)printf("%lld ",u[i]);putchar('\n');
	rep(i,1,m){
		int l=q[i].s,r=q[i].t-1,ed=q[i].t-1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(s[q[i].t]-s[mid]<=q[i].u)ed=mid,r=mid-1;
			else l=mid+1;
		}
		int cur=st1::ask(ed,q[i].t-1);
		//printf("ss %lld %lld %lld\n",i,ed,cur);
		node now;now.u=q[i].u,now.s=i,now.t=1;
		w[q[i].s].push_back(now);
		now.s=i,now.t=-1;w[cur].push_back(now);
		ans[i]+=(s[q[i].t]-s[cur])*b[cur];
	}
	pre(i,n,1){
		while(top&&b[sta[top]]>=b[i]){
			pr[sta[top]]=i;top--;
		}
		if(top)nx[i]=sta[top];
		sta[++top]=i;
	}
	rep(i,1,n)if(!nx[i])nx[i]=n+1;
	//rep(i,1,n)printf("%lld ",pr[i]);putchar('\n');
	//rep(i,1,n)printf("%lld ",nx[i]);putchar('\n');
	pre(i,n,1){
		change(0,0,s[nx[i]]-s[i],b[i]);
		change(1,s[nx[i]]-s[i]+1,0x7fffffff,b[i]*(s[nx[i]]-s[i]));
		dl[pr[i]].push_back(i);
		for(int j=0;j<(int)dl[i].size();j++){
			int x=dl[i][j];
			change(0,s[x]-s[i],s[nx[x]]-s[i],-b[x]);
			change(1,s[x]-s[i],s[nx[x]]-s[i],b[x]*(s[x]-s[i]));
			change(1,s[nx[x]]-s[i]+1,0x7fffffff,-b[x]*(s[nx[x]]-s[x]));
		}
		for(int j=0;j<(int)w[i].size();j++){
			int cur=lower_bound(u+1,u+T+1,w[i][j].u)-u;
			//cout<<"uu "<<i<<" "<<w[i][j].s<<" "<<w[i][j].t<<" "<<(w[i][j].u*ask(0,cur)+ask(1,cur))<<endl;
			ans[w[i][j].s]+=w[i][j].t*(w[i][j].u*ask(0,cur)+ask(1,cur));
		}
	}
	rep(i,1,m){
		if(q[i].u<a[st2::ask(q[i].s,q[i].t-1)])puts("-1");
		else printf("%lld\n",ans[i]);
	}
	return 0;///test
}