专栏文章

P12080 [OOI 2025] Order Statistics 题解

TTimSwn090306
P12080题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipbuiwd
此快照首次捕获于
2025/12/03 09:27
3 个月前
此快照最后确认于
2025/12/03 09:27
3 个月前
查看原文
思考数十分钟后仍不会 m=109,q=0,n=105,1≤k≤nm=10^9,q=0,n=10^5,1\le k\le n，痛定思痛，遂作此篇。

Description

给定序列 ana_n，定义 Fm,k(x)F_{m,k}(x) 表示每次对前 kk 大的值 −1-1，进行 mm 次后第 xx 大的值是多少。需要支持单点修改 aa，查询 ∑i∈[l,r]Fm,k(i)\sum_{i\in[l,r]}F_{m,k}(i)。
m,km,k 每次询问给出。
数据范围：1≤k≤n≤2×105,1≤q≤2×105,−109≤ai≤109,0≤m≤1091\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

不妨将 aa 排序，问题可以转化为每次选 kk 个位置的值 −1-1，操作后序列仍需单调不降，重复 mm 次，最大化最终每个下标的前缀和。
Proof：显然“每次选 kk 个位置的值 −1-1，操作后序列仍需单调不降”操作与原操作是等价的。不妨设在某次操作中，i<j,ai<aji<j,a_i<a_j，然而对 aia_i 执行 −1-1，而没有对 aja_j 执行 −1-1，则对于最终在 [i,j−1][i,j-1] 前缀和会造成 −1-1 的贡献。由于原问题中不会出现上述情况，故“最大化最终每个下标的前缀和”等价于原问题。
令 fi(x)f_i(x) 表示当 aia_i 最终变为 xx 时，a1∼ia_{1\thicksim i} 至少要减多少次 11；gi(x)g_i(x) 表示当 aia_i 最终变为 xx 时，a(i+1)∼na_{(i+1)\thicksim n} 至多能减多少次 11。则有：
fi(x)=∑j=1imax⁡(aj−x,0)f_i(x)=\sum_{j=1}^i \max(a_j-x,0)
gi(x)=∑j=i+1nmin⁡(aj−x,m)g_i(x)=\sum_{j=i+1}^n \min(a_j-x,m)
上述函数定义域均为 [ai−m,ai][a_i-m,a_i]。由于 aa 单调不降，fi(x),gi(x)f_i(x),g_i(x) 可以在 O(log⁡n)O(\log n) 时间内维护。
最终下标 ii 的最大前缀和即为 (∑j=1iaj)−min⁡x∈[ai−m,ai](max⁡(fi(x),mk−gi(x)))(\sum_{j=1}^i a_j)-\min_{x\in[a_i-m,a_i]}(\max(f_i(x),mk-g_i(x)))。由于 fi(x)f_i(x) 单调不增，(mk−gi(x))(mk-g_i(x)) 单调不减，二分交点可以得出 min⁡x∈[ai−m,ai](max⁡(fi(x),mk−gi(x)))\min_{x\in[a_i-m,a_i]}(\max(f_i(x),mk-g_i(x))) 的值。
每个下标的最大前缀和可以同时取到，区间 Fm,k(i)F_{m,k}(i) 的和可以通过两个最大前缀和相减得到。
单点修改 aa 不难用树状数组或平衡树维护，具体的，只需要支持点修，全局比某个值小的数的个数与和。
时间复杂度 O(nlog⁡2n)O(n\log^2 n)，略需精细实现。

Code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...