自动搬运

查看原文

来自洛谷，原作者为

	lbw 若有 笃信之物 莫忘厮守

搬运于2025-08-24 22:34:19，当前版本为作者最后更新于2024-08-05 17:05:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

爆标做法。

观察题目，发现这个又是最小值又是最大值非常难搞，每次 AB 操作次数相等看起来也没什么用。

我们考虑通过枚举 $w$，将 $\geq w$ 转为 1，剩下的为 0，这里复杂度看起来全错，但是等一下就对了。

这个东西怎么计算答案呢？我们知道 $A=\sum_{i}(w_i-w_{i-1})[A\geq w_i]$ 于是把每个 $w_i$ 对询问时的贡献即为最终序列中 1 个数乘上 $w_i-w_{i-1}$。

取出初始序列中所有极长 1 连续段，模拟可知：

• 每次 A 操作会使 1 连续段右端点左移一位
• 每次 B 操作会使 1 连续段左端点左移一位

因此，做完一个整段操作后，会使所有段往左移动 $a_i$ 位，并且长度小于 $a_i$ 的段会被删除。

这个形式的性质非常好！同时，它启发我们找出所有初始序列中所有极长 1 连续段。

每一次 $w_i$ 增加的时候，会变化的极长 1 连续段是 $\mathcal{O}(1)$ 的，我们把相同的极长 1 连续段缩起来，这样最多只会有 $\mathcal{O}(n)$ 个段 $(l_i,r_i,v_i)$，记段长为 $L_i$。

这一段的代码如下：

IV add(i64 l,i64 r,i64 v){
	tot++;
	L[tot]=l;R[tot]=r;V[tot]=v;
}
int main(){
	n=read();m=read();q=read();
	FL(i,1,n)pi[i]=make_pair(b[i]=read(),i);
	F(i,1,m)a[i]=read();sort(pi+1,pi+1+n);
	add(1,n,0);
	st.insert({1,n});
	F(i,1,n){
		i64 v=pi[i].first,pos=pi[i].second;
		auto p=prev(st.upper_bound({pos}));
		auto[l,r]=*p;add(l,r,v);st.erase(p);
		if(l<pos)st.insert({l,pos-1}),add(l,pos-1,-v);
		if(pos<r)st.insert({pos+1,r}),add(pos+1,r,-v);
	}
}

如果只会在整段处询问，问题即为每次给定 $w,\Delta_l,\Delta_r,ql,qr$ 求：

$$\sum_{L_i\geq w}v_i\left|[l_i-\Delta_l ,r_i-\Delta_r]\cap[ql,qr]\right| $$

这里 $\Delta_l=\Delta_r$，所以我们可以直接把 $[ql,qr]$ 往后平移。

于是，此问题可以通过直接从小到大枚举 $L_i$ 同时维护 区间加-区间查询 的数据结构做到 $n\log n$。

若查询不在整段，我们仍然可以计算一个 $w$ 表示区间最小可能长度，而 $\Delta_l$ 和 $\Delta_r$ 不一定相等。

注意到分类讨论一堆大小关系多维偏序就可以做到 $\textsf{polylog}$ 了，考虑优化 $\log$ 数量。

首先有 $\Delta_l\leq \Delta_r$，平移区间，问题转化为：

$$\sum_{L_i\geq w}v_i|[l_i ,r_i-k]\cap[ql_i,qr_i]|$$

拆分左右端点贡献，枚举左/右端点取值，列出区间长度 $\geq 0$ 的不等式，为三维偏序，时间复杂度 $\mathcal{O}((n+q)\log ^2n)$。

代码。

进一步，考虑容斥，有：

$$|[l_i ,r_i-k]\cap[ql_i,qr_i]|=|[l_i,r_i]\cap[ql_i,qr_i]|-|[r_i-k+1,r_i]\cap[ql_i,qr_i]| $$

前半部分与查询不在整段一致，容易解决。

容易发现后半部分不同位置 $r_i$ 的贡献为分段一次函数，可以用树状数组维护单点加，区间查询 $\sum v$ 和 $\sum v\times pos$。

时间复杂度 $\mathcal{O}((n+q)\log n)$，代码如下。

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<random>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define her1 20081214
#define cht 998244353
#define I i64
#define IV void
#define ull unsigned long long
#define mem(x,val) memset(x,val,sizeof x)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
ll read(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
	return ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
const int maxn = 1.5e5+5;
i64 n,m,q,b[maxn],a[maxn];char s[maxn];
struct sg{
	i64 l,r;
	bool operator<(const sg&V)const{
		return l<V.l;
	}
};
set<sg>st;pair<i64,i64>pi[maxn];
i64 L[maxn],R[maxn],V[maxn],tot,all;
struct node{
	i64 l,r,len,v,K,id;
}qwq[maxn*5];
IV add(i64 l,i64 r,i64 v){
	tot++;
	// L[tot]=l;R[tot]=r;V[tot]=v;
	qwq[tot]={l,r,r-l+1,v,0,0};
}
i64 sa[maxn],mx[maxn],sl[maxn],sr[maxn];

long long Ans[maxn];
struct BIT{
	long long c[maxn],qwq[maxn],tot,ans;bool vis[maxn];
	IV clr(){F(i,1,tot)vis[qwq[i]]=c[qwq[i]]=0;tot=0;}
	IV add(i64 p,long long v){
		for(;p<=n;p+=p&-p){
			if(!vis[p])vis[qwq[++tot]=p]=1;
			c[p]+=v;
		}
	}
	i64 Q(i64 p){
		if(p<1)return 0;p=min(p,n);
		ans=0;for(;p;p-=p&-p)ans+=c[p];return ans;
	}
	i64 Q(i64 l,i64 r){
		if(r<1||l>n)return 0;
		return Q(r)-Q(l-1);
	}
};

struct DS{
	#define ls (o<<1)
	#define rs (o<<1|1)
	i64 len[4*maxn],sum[4*maxn],tag[4*maxn];
	IV upd(i64 o){sum[o]=sum[ls]+sum[rs];}
	IV givet(i64 o,i64 v){sum[o]+=len[o]*v;tag[o]+=v;}
	IV pd(i64 o){if(!tag[o])return;givet(ls,tag[o]);givet(rs,tag[o]);tag[o]=0;}
	IV M(i64 o,i64 l,i64 r,i64 x,i64 y,i64 v){
		if(x<=l&&r<=y)return givet(o,v);if(r<x||l>y)return;pd(o);
		i64 mid=l+r>>1;M(ls,l,mid,x,y,v);M(rs,mid+1,r,x,y,v);upd(o);
	}
	i64 Q(i64 o,i64 l,i64 r,i64 x,i64 y){
		if(x<=l&&r<=y)return sum[o];if(r<x||l>y)return 0;pd(o);
		i64 mid=l+r>>1;return Q(ls,l,mid,x,y)+Q(rs,mid+1,r,x,y);
	}
	IV Build(i64 o,i64 l,i64 r){
		len[o]=r-l+1;if(l==r)return;i64 mid=l+r>>1;
		Build(ls,l,mid);Build(rs,mid+1,r);
	}
}ds;
struct DS2{
	BIT b1,b2;
	IV add(i64 p,i64 v){
		b1.add(p,v);
		b2.add(p,p*v);
	}
	i64 Q(i64 ql,i64 qr,i64 k){
		i64 sum=0;
		if(qr-ql+1>=k){
			sum+=b2.Q(ql,ql+k-1)-(ql-1)*b1.Q(ql,ql+k-1);
			sum+=(qr+k)*b1.Q(qr+1,qr+k-1)-b2.Q(qr+1,qr+k-1);
			sum+=k*b1.Q(ql+k,qr);
		}
		else{
			sum+=b2.Q(ql,qr)-(ql-1)*b1.Q(ql,qr);
			sum+=b1.Q(qr+1,ql+k-1)*(qr-ql+1);
			sum+=(qr+k)*b1.Q(ql+k,qr+k-1)-b2.Q(ql+k,qr+k-1);
		}
		return sum;
	}
}ds2;
int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);

	n=read();m=read();q=read();
	FL(i,1,n)pi[i]=make_pair(b[i]=read(),i);
	F(i,1,m)a[i]=read();sort(pi+1,pi+1+n);

	F(i,1,m){
		F(j,1,a[i])s[++all]='A';
		F(j,1,a[i])s[++all]='B';
	}
	F(i,1,all){
		sr[i]=sr[i-1]+(s[i]=='A');
		sl[i]=sl[i-1]+(s[i]=='B');
	}
	F(i,1,m){
		mx[i]=max(mx[i-1],a[i]);
		sa[i]=sa[i-1]+2*a[i];
	}
	add(1,n,0);
	st.insert({1,n});
	F(i,1,n){
		i64 v=pi[i].first,pos=pi[i].second;
		auto p=prev(st.upper_bound({pos}));
		auto[l,r]=*p;add(l,r,v);st.erase(p);
		if(l<pos)st.insert({l,pos-1}),add(l,pos-1,-v);
		if(pos<r)st.insert({pos+1,r}),add(pos+1,r,-v);
	}
	F(i,1,q){
		i64 x=read(),ql=read(),qr=read(),ans=0;
		i64 pos=lower_bound(sa+1,sa+1+m,x)-sa-1;
		i64 nd=max(mx[pos],min(x-sa[pos],a[pos+1]));
		i64 dl=sl[x],dr=sr[x],K=dr-dl;ql+=dl;qr+=dl;
		qwq[++tot]={ql,qr,nd,0,K,i};
	}
	sort(qwq+1,qwq+1+tot,[](node A,node B){
		return A.len==B.len?A.id>B.id:A.len>B.len;
	});
	ds.Build(1,1,n);
	F(i,1,tot){
		if(!qwq[i].id){
			ds.M(1,1,n,qwq[i].l,qwq[i].r,qwq[i].v);
			ds2.add(qwq[i].r,qwq[i].v);
		}
		else{
			Ans[qwq[i].id]+=ds.Q(1,1,n,qwq[i].l,qwq[i].r);
			Ans[qwq[i].id]-=ds2.Q(qwq[i].l,qwq[i].r,qwq[i].K);
		}
	}
	F(i,1,q)printf("%lld\n",Ans[i]);
	return 0;
}