正題

題目鏈接:https://www.ybtoj.com.cn/contest/68/problem/1

---

題目大意

$n$個(gè)數(shù)字的序列，求有多少個(gè)區(qū)間$[l,r]$的平均值在$[L,R]$的范圍內(nèi)。

---

解題思路

如果讓每個(gè)$a_i?x$，那么統(tǒng)計(jì)區(qū)間和大于等于$1$的區(qū)間數(shù)量就可以統(tǒng)計(jì)平均值大于$x$的區(qū)間數(shù)量，那么我們讓平均值大于等于$L$的減去平均值大于$R$的。

為了方便不離散化，我們讓下標(biāo)和數(shù)值互換一下，注意計(jì)算$R$時(shí)因?yàn)槭谴笥诘乃圆荒芎?span id="ze8trgl8bvbq" class="katex--inline">$L$的方法相同。

時(shí)間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) #define ll long long using namespace std; const ll N=5e5+10; ll n,L,R,p[N],w[N],t[N],a[N],fl; bool cmp(ll x,ll y) {return (w[x]==w[y])?(fl?(x>y):(x<y)):(w[x]<w[y]);} void Change(ll x,ll val){x++;while(x<=n+1){t[x]+=val;x+=lowbit(x);}return; } ll Ask(ll x){ll ans=0;x++;while(x){ans+=t[x];x-=lowbit(x);}return ans; } ll solve(ll x,bool flag){fl=flag;memset(t,0,sizeof(t));for(ll i=1;i<=n;i++)w[i]=w[i-1]+a[i]-x,p[i]=i;ll ans=0;p[n+1]=0;sort(p+1,p+2+n,cmp);for(ll i=1;i<=n+1;i++){ans+=Ask(p[i]);Change(p[i],1);}return ans; } int main() {freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);scanf("%lld%lld%lld",&n,&L,&R);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);ll a=solve(L,0)-solve(R,1);ll b=n*(n+1ll)/2ll,d=__gcd(a,b);a/=d;b/=d;if(!a)printf("0\n");else if(a==b)printf("1\n");else printf("%lld/%lld\n",a,b);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的YbtOJ#20237-[冲刺NOIP2020模拟赛Day10]区间均值【树状数组】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。