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

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

文章目录

• 2023牛客暑期多校训练营8-C Clamped Sequence II
• • 题意
  • 解题思路
  • 代码

题意

解题思路

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

nu m x=nu m lson +nu m rsonsu m x=nu m lson +su m rsonan s x=an s lson +an s rson +su m rson ×nu m lson −su m lson ×nu m rson num_x=num_{lson}+num_{rson}\\ sum_x=num_{lson}+sum_{rson}\\ ans_x=ans_{lson}+ans_{rson}+sum_{rson}\times num_{lson}-sum_{lson}\times num_{rson} numx​=numlson​+numrson​sumx​=numlson​+sumrson​ansx​=anslson​+ansrson​+sumrson​×numlson​−sumlson​×numrson​
此时我们加入紧凑的设定，对于每一对确定的$[l,r]$我们都可以算出此时的答案：
answer=an s l,r +su m [l,r] ×(nu m [1,l−1] −nu m [r+1,n] )+(nu m [1,l−1] +nu m [l,r] ) ×nu m [r+1,n] −(nu m [r+1,n] +nu m [l,r] )×nu m [1,l−1] answer=ans_{l,r}+sum_{[l,r]}\times(num_{[1,l-1]}-num_{[r+1,n]})+(num_{[1,l-1]}+num_{[l,r]})\\ \times num_{[r+1,n]}-(num_{[r+1,n]}+num_{[l,r]})\times num_{[1,l-1]} answer=ansl,r​+sum[l,r]​×(num[1,l−1]​−num[r+1,n]​)+(num[1,l−1]​+num[l,r]​)×num[r+1,n]​−(num[r+1,n]​+num[l,r]​)×num[1,l−1]​
根据出题人所说，该答案是严格单峰的，所以可以用三分求解，但经过我实践却不太像，需要将三分的范围约束在最中间的数$\pm d$再加上左右游移$2\sim 3$个数，大致能求出正确答案。

代码

#include#define ll long longusing 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<>1;build(res<<1,l,mid);build(res<<1|1,mid+1,r);tr[res]=tr[res<<1]+tr[res<>1;if(x<=mid)add(res<<1,x,d);else add(res<<1|1,x,d);tr[res]=tr[res<<1]+tr[res<y)return node{0,0,0,0,0};int l=tr[res].l,r=tr[res].r;if(x=r){return tr[res];}int mid=l+r>>1;if(y<=mid)return query(res<mid)return query(res<<1|1,x,y);return query(res<<1,x,y)+query(res<>1;if(tr[id<=k) return kth(id<<1,l,mid,k);else return kth(id<<1|1,mid+1,r,k-tr[id<>1);int l=max(1,k-d),r=min(M-1,k+d);ll ma=0;while(l+2=ma2)r=mi2-1;else l=mi1+1;}for(int i=l;i>n>>q;for(int i=1;i>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';}}}