P12080 [OOI 2025] Order Statistics 题解
TimSwn090306
·
·
题解
思考数十分钟后仍不会 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)。
数据范围：$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$。则有：
$$f_i(x)=\sum_{j=1}^i \max(a_j-x,0)$$
$$g_i(x)=\sum_{j=i+1}^n \min(a_j-x,m)$$
上述函数定义域均为 $[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
```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;
}
```