自动搬运

查看原文

来自洛谷，原作者为

	TimSwn090306 你说的对，但是区间LCA是相邻点对LCA中深度最浅的点

搬运于2025-08-24 23:12:38，当前版本为作者最后更新于2025-05-12 13:44:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思考数十分钟后仍不会 $m=10^9,q=0,n=10^5,1\le k\le n$，痛定思痛，遂作此篇。

Description

给定序列 $a_n$，定义 $F_{m,k}(x)$ 表示每次对前 $k$ 大的值 $-1$，进行 $m$ 次后第 $x$ 大的值是多少。需要支持单点修改 $a$，查询 $\sum_{i\in[l,r]}F_{m,k}(i)$。

$m,k$ 每次询问给出。

数据范围：$1\le k\le n\le 2\times 10^5,1\le q\le 2\times 10^5,-10^9\le a_i\le 10^9,0\le m \le 10^9$。

Solution

不妨将 $a$ 排序，问题可以转化为每次选 $k$ 个位置的值 $-1$，操作后序列仍需单调不降，重复 $m$ 次，最大化最终每个下标的前缀和。

Proof：显然“每次选 $k$ 个位置的值 $-1$，操作后序列仍需单调不降”操作与原操作是等价的。不妨设在某次操作中，$i<j,a_i<a_j$，然而对 $a_i$ 执行 $-1$，而没有对 $a_j$ 执行 $-1$，则对于最终在 $[i,j-1]$ 前缀和会造成 $-1$ 的贡献。由于原问题中不会出现上述情况，故“最大化最终每个下标的前缀和”等价于原问题。

令 $f_i(x)$ 表示当 $a_i$ 最终变为 $x$ 时，$a_{1\thicksim i}$ 至少要减多少次 $1$；$g_i(x)$ 表示当 $a_i$ 最终变为 $x$ 时，$a_{(i+1)\thicksim n}$ 至多能减多少次 $1$。则有：

上述函数定义域均为 $[a_i-m,a_i]$。由于 $a$ 单调不降，$f_i(x),g_i(x)$ 可以在 $O(\log n)$ 时间内维护。

最终下标 $i$ 的最大前缀和即为 $(\sum_{j=1}^i a_j)-\min_{x\in[a_i-m,a_i]}(\max(f_i(x),mk-g_i(x)))$。由于 $f_i(x)$ 单调不增，$(mk-g_i(x))$ 单调不减，二分交点可以得出 $\min_{x\in[a_i-m,a_i]}(\max(f_i(x),mk-g_i(x)))$ 的值。

每个下标的最大前缀和可以同时取到，区间 $F_{m,k}(i)$ 的和可以通过两个最大前缀和相减得到。

单点修改 $a$ 不难用树状数组或平衡树维护，具体的，只需要支持点修，全局比某个值小的数的个数与和。

时间复杂度 $O(n\log^2 n)$，略需精细实现。

Code

#include <bits/stdc++.h>
#define fin(str) freopen(str,"r",stdin)
#define fout(str) freopen(str,"w",stdout)
#define ll long long
#define int long long
using namespace std;
inline int rd(){
	register int x=0,f=1; char ch=getchar();
	while (ch<'0' || ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>9) write(x/10);
	putchar('0'+(x%10));
}

bool MEM_beg;

const int maxn=4e5+5;
const ll inf=1e15+5;

struct query{
	int m,k,l,r;
}q[maxn];

int n,m0,k0,qtot,a[maxn];
ll btot,b[maxn];
ll vn;

inline int get(int x){
	return upper_bound(b+1,b+btot+1,x)-b-1;
}

struct BIT{
	ll c[maxn];
	inline int lowbit(int x) {return x&-x; }
	inline void add(int x,int k) {for (int i=x;i<=btot;i+=lowbit(i)) c[i]+=k; }
	inline ll ask(int x){
		ll res=0;
		for (int i=x;i;i-=lowbit(i)) res=res+c[i];
		return res;
	}
	inline ll all(){
		return ask(btot);
	}
}CNT,SUM;

inline int getkth(int x){
	int l=1,r=btot;
	while (l<=r){
		int mid=(l+r)>>1;
		if (CNT.ask(mid)<x) l=mid+1;
		else r=mid-1;
	}
	return b[l];
}
inline ll getsum(int id,int val,int nw){//前id小的和
	if (!id) return 0ll;
	if (val==inf) val=getkth(id);
	if (nw==-1) nw=get(val);
	ll S=SUM.ask(nw-1),C=CNT.ask(nw-1);
	return S+1ll*(id-C)*val;
}
inline ll getsum_max(int id,int val,int x,int v_nw,int x_nw){//前id小分别-x然后对0取max的和
	if (!id) return 0ll;
	if (x_nw==-1) x_nw=get(x);
	int cnt_temp=0;
	if ((cnt_temp=CNT.ask(x_nw))<=id) return (getsum(id,val,v_nw)-SUM.ask(x_nw))-(id-cnt_temp)*x;
	else return 0ll;
}
inline ll getsum_min(int id,int val,int x,int v_nw,int x_nw){//前id小分别-x然后对0取min的和
	if (!id) return 0ll;
	if (x_nw==-1) x_nw=get(x);
	int cnt_temp=0;
	if ((cnt_temp=CNT.ask(x_nw))<=id) return (SUM.ask(x_nw))-cnt_temp*x;
	else{
		return (getsum(id,val,v_nw))-1ll*id*x;
	}
}

inline bool check(int id,int val,int mid,int m,int k,int v_nw,int vn_nw,int mid_nw,int midm_nw){
	return getsum_max(id,val,mid,v_nw,mid_nw)+getsum_min(n,vn,mid+m,vn_nw,midm_nw)-getsum_min(id,val,mid+m,v_nw,midm_nw)+1ll*m*(n-id)>=1ll*m*k;
}
inline ll calc(int id,int val,int x,int m,int k,int v_nw,int vn_nw,int x_nw,int xm_nw){
	return max(1ll*m*k-(getsum_min(n,vn,x+m,vn_nw,xm_nw)-getsum_min(id,val,x+m,v_nw,xm_nw)+1ll*m*(n-id)),getsum_max(id,val,x,v_nw,x_nw));
}
inline ll solve(int id,int m,int k,int flag){
	if (id<=0) return 0;
	
	int val=getkth(id),v_nw=get(val),vn_nw=get(vn);
	ll l=val-m,r=val;
	while (l<=r){
		ll mid=(l+r)/2;
		if (check(id,val,mid,m,k,v_nw,vn_nw,get(mid),get(mid+m))) l=mid+1;
		else r=mid-1;
	}
	
	ll fin=inf; int p=-1;
	for (int i=l-1;i<=l;i++){
		if (i>=val-m && i<=val){
			ll res=calc(id,val,i,m,k,v_nw,vn_nw,get(i),get(i+m));
			if (res<fin){
				fin=res;
				p=i;
			}
		}
	}
	
	if (!flag) return getsum(id,val,v_nw)-fin;
	return p;
}

bool MEM_end;
signed main(){
	n=rd(),m0=rd(),k0=rd(),qtot=rd();
	for (int i=1;i<=n;i++){
		a[i]=rd();
		b[++btot]=a[i];
	}
	
	for (int i=1,opt;i<=qtot;i++){
		opt=rd();
		if (opt==1) q[i].m=rd(),q[i].k=rd(),q[i].l=rd(),q[i].r=q[i].l;
		else if (opt==2) q[i].l=rd(),q[i].k=rd(),q[i].r=-1,q[i].m=-1,b[++btot]=q[i].k;
		else if (opt==3) q[i].m=rd(),q[i].k=rd(),q[i].l=rd(),q[i].r=rd();
	}
	
	b[++btot]=-inf;
	b[++btot]=+inf;
	sort(b+1,b+btot+1);
	btot=unique(b+1,b+btot+1)-b-1;
	
	for (int i=1;i<=n;++i){
		int nw=get(a[i]);
		CNT.add(nw,1);
		SUM.add(nw,a[i]);
	}
	vn=getkth(n);
	
	for (int i=1;i<=n;++i) write(solve(i,m0,k0,0)-solve(i-1,m0,k0,0)),putchar(' ');
	putchar('\n');
	
	for (int i=1;i<=qtot;++i){
		if (q[i].r==-1){
			int nw=get(q[i].k),org=get(a[q[i].l]);
			CNT.add(org,-1);
			SUM.add(org,-a[q[i].l]);
			a[q[i].l]=q[i].k;
			CNT.add(nw,1);
			SUM.add(nw,a[q[i].l]);
			
			vn=getkth(n);
		}else{
			if (q[i].l!=q[i].r) write(solve(q[i].r,q[i].m,q[i].k,0)-solve(q[i].l-1,q[i].m,q[i].k,0));
			else write(solve(q[i].r,q[i].m,q[i].k,1));
			putchar('\n');
		}
	}
	
	cerr<<"\nMemory : "<<1.0*abs(&MEM_end-&MEM_beg)/1048576<<" MB\n";
	return 0;
}