「JOI 2021 Final」地牢 3

Posted on Edited on In

「JOI 2021 Final」地牢 3

判定无解

无解即： \(\exists i\in[S,T-1],A_i>U\)

是一个简单的区间最值问题

\[\ \]

\(O(nm)\)

关于用单调队列之类的东西维护每个点权值的方法这里就不提了

形式化地，我们把一层层点放到数轴上，令 \(X_i=\sum_{j<i}A_j\)

在数轴上坐标每 \(+1\) 消耗一点能量，我们要从 \(X_S\) 走到 \(X_T\)

考虑每个点的情况，不妨看做是用 \(B_i\) 去覆盖 \((X_S,X_T]\) ，求最小权值

发现对于 \(B_i\) ，它能够合法覆盖的区间一定是 \((X_i,X_i+U]\)

暴力地，可以直接让 \(B_i\) 更新这段区间的最小权值，然后暴力求和

\[\ \]

进一步分析每个 \(B_i\) 覆盖的区间，可以发现是合法区间 \((X_i,X_i+U]\) 中的某一连续段 \((L_i,R_i]\)

而 \(L_i\) 取决于 \(B_i\) 前面第一个 \(B_{pre}<B_i\) ， \(R_i\) 取决于后面第一个 \(B_{nxt}\leq B_i\)

关于 \(pre,nxt\) 的求解显然只是一个单调栈解决

得到 \((L_i,R_i]\) 简单的描述

\(L_i=\max\{X_i,X_{pre}+U\}\)

\(R_i=\min\{X_i+U,X_{nxt}\}\)

(ps:这样求得的 \(L_i\) 不一定 \(<R_i\) )

暴力枚举即可 \(O(n)\) 查询

\[ \ \]

\[ \ \]

\(T_i=n+1\) 从这里开始需要一些数据结构？

考虑倒着从 \(n\) 到 \(1\) 计算每一个 \(S_i\) 的答案

发现在刚插入 \(i\) 的时候， \(pre_i\) 还未出现，可以看做 \(-\infty\) ， \(nxt_i\) 已经确定

当 \(pre_i\) 出现时可以重新进行一次插入

每次插入可以用三元组表示 \((i,pre,nxt)\) ，为了便于叙述这里 \(pre,nxt\) 直接是坐标

考虑对于 \(L_i,R_i\) 进行参数分离计算，首先要考虑何时满足 \(L_i<R_i\)

显然条件就是 \(nxt-pre>U\)

\(\displaystyle L_i=\max\{X_i,X_{pre}+U\}=X_{pre}+\max\{X_i-X_{pre},U\}\)

\(\displaystyle R_i=\min\{X_i+U,X_{nxt}\}=X_i+\min\{U,X_{nxt}-X_i\}\)

\(\displaystyle Answer=\sum_{nxt-pre>U} (R_i-L_i)\cdot B_i\)

离线询问，离散之后可以用树状数组维护上述式子，对于不合法部分不要加入即可

\[\ \]

\[ \ \]

\(O(n\log n)\)

上面已经能计算 \(T_i=n+1\) 的询问，考虑将 \(S,T\) 转化为 \(T_{i}=n+1\) 的问题

如果直接 \(S,T\) 相减显然不合法，不妨找到在 \((S,n+1)\) 的方案中，覆盖的 \(T\) 的点 \(T'\)

\((S,n+1)-(T',n+1)\) 会抵消掉在 \(S\) 的方案中 \(T\) 右边的部分，而 \((X_{T'},X_T]\) 显然仍然是由 \(B_{T'}\) 覆盖，补回来即可

由此完成分离操作，而根据上面区间覆盖的定义， \(T'\) 实际上就是 \((X_T-U,X_T]\) 中最小的 \(B_i\)

所有操作都可以 \(O(n\log n)\) 完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10,INF=1e9+10;

int n,m,A[N],B[N],nxt[N],stk[N],top,C;
ll ans[N],X[N],H[N];
struct Node{ int U,k,id; };
vector <Node> Q[N];
vector <int> G[N];
struct BIT{
	ll s[N];
	void Add(int p,ll x){ 
		while(p<=C) s[p]+=x,p+=p&-p; 
	}
	ll Que(int p){
		ll res=0;
		while(p) res+=s[p],p-=p&-p;
		return res;
	}
} T1,T2;
// T1维护式子中含U项的和
// T2维护式子中常数和

struct MaxTree{
	int s[N<<2],bit;
	void Build(){
		for(bit=1;bit<=n+1;bit<<=1) ;
		rep(i,1,n) s[bit+i]=A[i];
		drep(i,bit,1) s[i]=max(s[i<<1],s[i<<1|1]);
	}
	int Que(int l,int r){
		if(l==r) return s[l+bit];
		int res=0;
		for(l+=bit-1,r+=bit+1;l^r^1;l>>=1,r>>=1){
			if(~l&1) cmax(res,s[l^1]);
			if(r&1) cmax(res,s[r^1]);
		}
		return res;
	}
} Max;
struct MinTree{
	int s[N<<2],bit;
	int Min(int x,int y){ return mp(B[x],x)<mp(B[y],y)?x:y; }
	void Build(){
		B[0]=1e9;
		for(bit=1;bit<=n+1;bit<<=1) ;
		rep(i,1,n) s[bit+i]=i;
		drep(i,bit,1) s[i]=Min(s[i<<1],s[i<<1|1]);
	}
	int Que(int l,int r){
		if(l==r) return s[l+bit];
		int res=0;
		for(l+=bit-1,r+=bit+1;l^r^1;l>>=1,r>>=1){
			if(~l&1) res=Min(res,s[l^1]);
			if(r&1) res=Min(res,s[r^1]);
		}
		return res;
	}
} Min;
// Min 用于寻找T'

void Add(int i,ll pre,ll nxt,int k){
	int p=lower_bound(H+1,H+C+1,X[i]-pre)-H,r=lower_bound(H+1,H+C+1,nxt-pre)-H;
	// -L
	T1.Add(p,-B[i]*k), T1.Add(r,B[i]*k);
	T2.Add(p,k*B[i]*(X[i]-pre)), T2.Add(r,-k*B[i]*(X[i]-pre));
	// +R 
	p=lower_bound(H+1,H+C+1,nxt-X[i])-H;
	T1.Add(1,k*B[i]),T1.Add(p,-k*B[i]);
	T2.Add(p,k*(nxt-X[i])*B[i]),T2.Add(r,-k*(nxt-X[i])*B[i]);
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) A[i]=rd(),X[i+1]=X[i]+A[i];
	rep(i,1,n) B[i]=rd();
	drep(i,n+1,1) {
		while(top && B[stk[top]]>=B[i]) G[i].pb(stk[top--]);
		nxt[i]=stk[top],stk[++top]=i;
	}
	Min.Build(),Max.Build();
	rep(i,1,m) {
		int S=rd(),T=rd(),U=rd();
		if(Max.Que(S,T-1)>U){ ans[i]=-1; continue; }
		H[++C]=U,Q[S].pb((Node){U,1,i});
		int l=lower_bound(X+1,X+n+2,X[T]-U)-X; cmax(l,S);
		int t=Min.Que(l,T);
		ans[i]+=(X[T]-X[t])*B[t];
		Q[t].pb((Node){U,-1,i});
	}
	sort(H+1,H+C+1),C=unique(H+1,H+C+1)-H-1;
	drep(i,n,1){
		Add(i,-1e9,X[nxt[i]],1);
		for(int j:G[i]) Add(j,-1e9,X[nxt[j]],-1),Add(j,X[i],X[nxt[j]],1);
		for(Node j:Q[i]){
			int p=lower_bound(H+1,H+C+1,j.U)-H;
			ans[j.id]+=j.k*(j.U*T1.Que(p)+T2.Que(p));
		}
	}
	rep(i,1,m) printf("%lld\n",ans[i]);
}