[NOIP2022] 比赛

\(\mathcal Link\)

大半年前，我在没有难题的 NOIP 大败而归，以一个耻辱的分数。

注意到询问具有分治性。考虑类似线段树一样拆分询问，然后考虑跨过 \(\textit{mid}\) 的子区间贡献。

对于一个固定的 \(r\)，考虑 \(l\) 的贡献。记 \(f\)，\(g\) 分别代表 \(A\) 和 \(B\) 对应区间的最值。
考虑将其分成 4 类：

• \(f(l)>f(r), g(l)>g(r)\)，对应贡献为 \(f(l)g(l)\)
• \(f(l)>f(r), g(l)\leq g(r)\)，对应贡献为 \(f(l)g(r)\)
• \(f(l)\leq f(r),g(l)>g(r)\)，对应贡献为 \(f(r)g(l)\)
• \(f(l)\leq f(r), g(l)\leq g(r)\)，对应贡献为 \(f(r)g(r)\)

由于 \(f,g\) 都具有单调性且单调性相同，所以不会出现交叉，2,3 不会同时出现，然后会发现分布一定是 \(1\to 2/3\to 4\)。
考虑在扫描的时候动态维两个指针表示第一个非 1 的位置和第一个属于 4 的位置，并用线段树维护 \(ql=l,l+1,\cdots mid\) 时右端点的贡献和，查询时直接查询区间和即可。

注意为了保证复杂度，需要处理出分治树上每个节点对应的整区间的贡献，这是容易的。
总复杂度 \(\mathcal O(n\log^2 n)\)。

#include <bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
#define pb push_back
namespace FastIO{
	char buf[1<<14], *p1=buf, *p2=buf;
	#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
	struct Ios{}io;
	template <typename _tp>
	Ios &operator >>(Ios &in, _tp &x){
		x=0; int w=0; char c=GetC();
		for(;!isdigit(c);w|=c=='-', c=GetC());
		for(;isdigit(c);x=x*10+(c^'0'), c=GetC());
		if(w) x=-x;
		return in;
	}
}
using FastIO::io;

const int N=2.5e5+5;
int n, m;
ll ans[N], a[N], b[N];
struct Quest{ int l, r, id; };
vector<Quest> v[N];

struct SegTree{
	ll sum[N<<2], tag[N<<2], fac[N<<2];
	ll init[N];
	#define ls(p) ((p)<<1)
	#define rs(p) ((p)<<1|1)
	void build(int p, int l, int r){
		tag[p]=sum[p]=0;
		if(l==r){
			fac[p]=init[l];
			return ;
		}
		int mid=(l+r)>>1;
		build(ls(p), l, mid);
		build(rs(p), mid+1, r);
		fac[p]=fac[ls(p)]+fac[rs(p)];
	}
	void whole(int p, ll k){
		sum[p]+=k*fac[p];
		tag[p]+=k;
	}
	void pushdown(int p){
		if(tag[p]){
			whole(ls(p), tag[p]);
			whole(rs(p), tag[p]);
			tag[p]=0;
		}
	}
	void pushup(int p){
		sum[p]=sum[ls(p)]+sum[rs(p)];
	}
	void modify(int p, int l, int r, int ql, int qr, ll k){
		if(ql<=l && r<=qr){
			whole(p, k);
			return ;
		}
		int mid=(l+r)>>1;
		pushdown(p);
		if(ql<=mid) modify(ls(p), l, mid, ql, qr, k);
		if(qr>mid) modify(rs(p), mid+1, r, ql, qr, k);
		pushup(p);
	}
	ll query(int p, int l, int r, int ql, int qr){
		if(ql<=l && r<=qr)
			return sum[p];
		int mid=(l+r)>>1;
		pushdown(p);
		if(qr<=mid) return query(ls(p), l, mid, ql, qr);
		if(ql>mid) return query(rs(p), mid+1, r, ql, qr);
		return query(ls(p), l, mid, ql, qr)+query(rs(p), mid+1, r, ql, qr);
	}
}T[4];

#define f(i) T[0].init[i] 
#define g(i) T[1].init[i]

ll solve(int l, int r){
	if(l==r){
		for(auto x:v[l])
			ans[x.id]+=a[l]*b[l];
		return a[l]*b[l];
	}
	int mid=(l+r)>>1;
	ll res=0;
	f(mid)=a[mid]; g(mid)=b[mid];
	for(int i=mid-1;i>=l;--i)
		f(i)=max(f(i+1), a[i]), g(i)=max(g(i+1), b[i]);
	f(mid+1)=a[mid+1]; g(mid+1)=b[mid+1];
	for(int i=mid+2;i<=r;++i)
		f(i)=max(f(i-1), a[i]), g(i)=max(g(i-1), b[i]);
	for(int i=l;i<=r;++i)
		T[2].init[i]=T[0].init[i]*T[1].init[i],
		T[3].init[i]=1;
	for(int i=0;i<=3;++i)
		T[i].build(1, l, mid);
	int p1=mid, p2=mid;
	for(int i=mid+1;i<=r;++i){
		while(p1>=l && !(f(p1)>f(i) && g(p1)>g(i))) --p1;
		while(p2>=l && f(p2)<=f(i) && g(p2)<=g(i)) --p2;
		if(p1>=l) T[2].modify(1, l, mid, l, p1, 1);
		if(p1!=p2){
			if(f(p1+1)>f(i) && g(p1+1)<=g(i)) T[0].modify(1, l, mid, p1+1, p2, g(i));
			else T[1].modify(1, l, mid, p1+1, p2, f(i));
		}
		if(p2!=mid) T[3].modify(1, l, mid, p2+1, mid, f(i)*g(i));
		for(auto x:v[i]){
			if(x.l>mid || (x.l==l && x.r==r)) continue;
			for(int type=0;type<4;++type)
				ans[x.id]+=T[type].query(1, l, mid, x.l, mid);
		}
		if(i==r){
			for(int type=0;type<4;++type)
				res+=T[type].query(1, l, mid, l, mid);
		}
	}
	vector<Quest> Tmp;
	{
		vector<Quest> Tmp2;
		for(auto x:v[r]){
			if(x.l==l) Tmp.pb(x);
			else Tmp2.pb(x);
		}
		swap(v[r], Tmp2);
	}
	for(int i=mid+1;i<=r;++i){
		for(auto &x:v[i]){
			if(x.l<=mid){
				v[mid].pb((Quest){ x.l, mid, x.id });
				x.l=mid+1;
			}
		}
	}
	res+=solve(l, mid);
	res+=solve(mid+1, r);
	for(auto x:Tmp){
		if(x.l==l)
			ans[x.id]+=res;
	}
	return res;
}

int main(){
	int Num; io>>Num>>n;
	for(int i=1;i<=n;++i) io>>a[i];
	for(int i=1;i<=n;++i) io>>b[i];
	io>>m;
	for(int i=1;i<=m;++i){
		int l, r; io>>l>>r;
		v[r].push_back((Quest){ l, r, i});
	}
	solve(1, n);
	for(int i=1;i<=m;++i)
		printf("%llu\n", ans[i]);
	return 0;
}