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～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';}}
}