做法

單點加單點刪，在值域線段樹上直接二分就能求值前\(K\)小的和

Code

#include<bits/stdc++.h> typedef long long LL; const LL maxn=1e6+9; inline LL Read(){LL x(0),f(1); char c=getchar();while(c<'0' || c>'9'){if(c=='-') f=-1; c=getchar();}while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0'; c=getchar();}return x*f; } LL n,m,K,sum,ans,L,R; LL a[maxn]; struct D_tree{LL nod,root;LL size[maxn],son[maxn][2],sum[maxn];inline void Update(LL now){size[now]=size[son[now][0]]+size[son[now][1]];sum[now]=sum[son[now][0]]+sum[son[now][1]];}void Build(LL &now,LL l,LL r){now=++nod;if(l==r) return;LL mid(l+r>>1);Build(son[now][0],l,mid); Build(son[now][1],mid+1,r);}void Modify(LL now,LL l,LL r,LL x,LL op){if(l==r){size[now]+=op; sum[now]=size[now]*l; return;}LL mid(l+r>>1);if(x<=mid) Modify(son[now][0],l,mid,x,op);else Modify(son[now][1],mid+1,r,x,op);Update(now);}LL Query_K(LL now,LL l,LL r,LL k){LL ret(0);if(size[now]==k) return sum[now];if(l==r){return l*k;}LL mid(l+r>>1);if(size[son[now][0]]>=k) return Query_K(son[now][0],l,mid,k);else return sum[son[now][0]]+Query_K(son[now][1],mid+1,r,k-size[son[now][0]]);} }T; int main(){n=Read(); m=Read(); K=Read();for(LL i=1;i<=n;++i) a[i]=Read();T.Build(T.root,L=0,R=100000);for(LL i=1;i<=m;++i)T.Modify(T.root,L,R,a[i],1);for(LL i=1;i<=n-m+1;++i){if(i!=1){T.Modify(T.root,L,R,a[i-1],-1); T.Modify(T.root,L,R,a[m+i-1],1);}ans+=T.Query_K(T.root,L,R,K);}printf("%lld\n",ans);return 0; }

轉載于:https://www.cnblogs.com/y2823774827y/p/10921242.html

總結

以上是生活随笔為你收集整理的牛客OI周赛10-提高组：B-Taeyeon的困惑(值域线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。