自动搬运

查看原文

来自洛谷，原作者为

	Zelensky 人们心中的成见是一座大山

搬运于2025-08-24 23:16:56，当前版本为作者最后更新于2025-07-10 19:18:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

blog

一个序列计数问题，把题意转化一下，发现如果没有 AI 操作，就是要求有多少个区间的 $\sum_{i=l}^r(h_i-a_i)\ge0$，其中负数的权值要乘上 $k$ ，为求简便，之后的区间不加说明则为 $h_i-a_i$ 所构成的序列中的区间。

考虑 AI 的操作，如果区间修改前为人类胜利，发现 AI 的最优决策一定是选中区间中最大的数交换，这样获得的收益最大，否则 AI 不需要修改操作。

这个启发我们根据最值分治，选取当前分治区间的最大值作为分治中心，这样跨越中心的区间 AI 一定会选择分治中心作为操作对象，我们成功地固定了式子中的一项。

容易计算出操作后的变化量 $\Delta=Mx\times(k+1)$ ，问题转化为有多少区间满足 $\sum_{i=l}^r(h_i-a_i)-\Delta\ge0$ ,考虑启发式分治，枚举区间长度较小的一边，当枚举左区间时，问题转化为以下形式，询问有多少 $R$ 满足

其中 $S$ 为前缀和数组。右区间同理。

显然的一个二维数点问题，可以离线下来扫描线，也可以在线主席树维护，注意一下整形的溢出和边界的处理即可。

#include<bits/stdc++.h>
#define int long long
typedef long long ll; 
using namespace std;
const int M=5e6+10;
long long a[(int)5e6],h[(int)5e6];
int len,rt;
ll b[(int)5e6],tot;
int id(int x){return lower_bound(b+1,b+len+1,x)-b;}
struct ST{
	int f[(int)5e5][30],lg[(int)5e6];
	void build(int n){
		lg[1]=0;
		for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1,f[i][0]=i;
		f[1][0]=1;
		for(int i=1;(1<<i)<=n;i++){
			for(int j=1;j+(1<<i)-1<=n;j++){
				int lp=f[j][i-1],rp=f[j+(1<<(i-1))][i-1];
				f[j][i]=(h[lp]>h[rp]?lp:rp);
			}
		}	
	}
	int query(int l,int r){
		int k=lg[r-l+1],lp=f[l][k],rp=f[r-(1<<k)+1][k];
		return h[lp]>h[rp]?lp:rp;
	}
}s;
struct pre_sum{
	ll s[(int)5e6];
	void build(int n){for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];}
	int query(int l,int r){return s[r]-s[l-1];}
}t;
struct qry{ll v;int opt;};
vector<qry>q1[(int)5e6],q2[(int)5e6];
int n,k;long long ans;
void solve(int l,int r){
	if(l>r)return ; if(l==r)return ans+=h[l]==0,void();
	int mid=s.query(l,r);
	solve(l,mid-1),solve(mid+1,r);
	if(h[mid]<0)return ;
	if(mid-l+1<=r-mid){
		for(int i=mid;i>=l;i--){
			ll val=h[mid]*(k+1)+t.s[i-1];
			q1[r].push_back({val,1}),q1[mid-1].push_back({val,-1});
			b[++tot]=val;
		}
	}
	else {
		for(int i=mid;i<=r;i++){
			ll val=t.s[i]-h[mid]*(k+1);
			q2[mid].push_back({val,1}),q2[l-1].push_back({val,-1}); 	
			b[++tot]=val;
		}
	}
}
struct SEG{
	int cnt=0;
	int siz[(int)5e6],ls[(int)5e6],rs[(int)5e6];
	void add(int &i,int l,int r,int x){
		if(!i)i=++cnt;siz[i]++;if(l==r)return ;int mid=(l+r)>>1;
		x<=mid?add(ls[i],l,mid,x):add(rs[i],mid+1,r,x);
	}
	int query(int i,int l,int r,int x,int opt){
		if(l==r)return siz[i]*opt;int mid=(l+r)>>1;
		return x<=mid?query(ls[i],l,mid,x,opt):(query(rs[i],mid+1,r,x,opt)+siz[ls[i]]);
	}
}T;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>h[i];
	int cnt=0;
	for(int i=1;i<=n;i++){
		cin>>a[i],h[i]-=a[i];
	}
	for(int i=1;i<=n;i++)if(h[i]<0)h[i]*=k;
	s.build(n),t.build(n);
	solve(1,n);
	for(int i=0;i<=n;i++)b[++tot]=t.s[i];
	sort(b+1,b+tot+1);len=unique(b+1,b+tot+1)-b-1;
	for(int i=0;i<=n;i++){
		for(auto x:q2[i])ans+=T.query(rt,1,M,id(x.v)+1,1)*x.opt;
		T.add(rt,1,M,id(t.s[i])+1);
		for(auto x:q1[i])ans+=(i-T.query(rt,1,M,id(x.v)+1,0))*x.opt;
	}
	cout<<ans<<endl;
}