2023牛客暑期多校训练营8-C Clamped Sequence II

2023牛客暑期多校训练营8-C Clamped Sequence II

https://ac.nowcoder.com/acm/contest/57362/C

题意

解题思路

先考虑不加紧密度的情况，要支持单点修改，整体查询，可以用值域线段树来求。设$tree[x].num$表示数值在$[l,r]$区间的数的个数，$tree[x].sum$表示数值在$[l,r]$区间的数的总和，$tree[x].ans$表示数值在$[l,r]$区间的数的紧密度，结合下图，可以求得转移式：

$$\begin{gathered} nu{m}_x=nu{m}_{lson}+nu{m}_{rson} \\ su{m}_x=nu{m}_{lson}+su{m}_{rson} \\ an{s}_x=an{s}_{lson}+an{s}_{rson}+su{m}_{rson}\times nu{m}_{lson}-su{m}_{lson}\times nu{m}_{rson} \end{gathered}$$
此时我们加入紧凑的设定，对于每一对确定的$[l,r]$我们都可以算出此时的答案：
$$\begin{gathered} answer=an{s}_{l,r}+su{m}_{[l,r]}\times (nu{m}_{[1,l-1]}-nu{m}_{[r+1,n]})+(nu{m}_{[1,l-1]}+nu{m}_{[l,r]}) \\ \times nu{m}_{[r+1,n]}-(nu{m}_{[r+1,n]}+nu{m}_{[l,r]})\times nu{m}_{[1,l-1]} \end{gathered}$$
根据出题人所说，该答案是严格单峰的，所以可以用三分求解，但经过我实践却不太像，需要将三分的范围约束在最中间的数$\pm d$再加上左右游移$2\sim 3$个数，大致能求出正确答案。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=1e6+5;
ll n,a[N],b[M],q;
struct node{ll num,l,r;ll sum,ans;node operator +(const node a){node t;t.num=num+a.num,t.sum=sum+a.sum;t.ans=num*a.sum-sum*a.num+ans+a.ans;t.l=l,t.r=a.r;return t;}
};
struct tree{node tr[M<<2];void build(int res,int l,int r){tr[res].l=l,tr[res].r=r;if(l==r){tr[res].num=b[l],tr[res].sum=b[l]*l;return;}int mid=l+r>>1;build(res<<1,l,mid);build(res<<1|1,mid+1,r);tr[res]=tr[res<<1]+tr[res<<1|1];}void add(int res,int x,ll d){int l=tr[res].l,r=tr[res].r;if(l==r&&l==x){tr[res].sum+=d*l;tr[res].num+=d;return;}int mid=l+r>>1;if(x<=mid)add(res<<1,x,d);else add(res<<1|1,x,d);tr[res]=tr[res<<1]+tr[res<<1|1];return;}node query(int res,int x,int y){if(x>y)return node{0,0,0,0,0};int l=tr[res].l,r=tr[res].r;if(x<=l&&y>=r){return tr[res];}int mid=l+r>>1;if(y<=mid)return query(res<<1,x,y);if(x>mid)return query(res<<1|1,x,y);return query(res<<1,x,y)+query(res<<1|1,x,y);}int kth(int id,int l,int r,int k){if(l==r) return l;int mid=l+r>>1;if(tr[id<<1].num>=k) return kth(id<<1,l,mid,k);else return kth(id<<1|1,mid+1,r,k-tr[id<<1].num);}
}t;
ll f(int l,int d){int r=l+d;node p=t.query(1,l,r);ll num1=p.num,ans1=p.ans,sum1=p.sum;ll numl=t.query(1,1,l-1).num,numr=t.query(1,r+1,M-1).num;return ans1-numl*(numr+num1)*l+numr*(numl+num1)*r+sum1*(numl-numr);
}
ll work(int d){int k=t.kth(1,1,M-1,n+1>>1);int l=max(1,k-d),r=min(M-1,k+d);ll ma=0;while(l+2<=r){int mi1=(r-l)/3+l,mi2=r-(r-l)/3;ll ma1=f(mi1,d),ma2=f(mi2,d);ma=max(ma,max(ma1,ma2));if(ma1>=ma2)r=mi2-1;else l=mi1+1;}for(int i=l;i<=r;i++)ma=max(ma,f(i,d));return ma;
}
int main(){ios::sync_with_stdio(false);cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i],b[a[i]]++;t.build(1,1,M-1);while(q--){int op;cin>>op;if(op==1){int x,d;cin>>x>>d;t.add(1,a[x],-1);t.add(1,d,1);a[x]=d;}else{int d;cin>>d;cout<<work(d)<<'\n';}}
}