來自FallDream的博客，未經(jīng)允許，請勿轉載，謝謝。

---

?

給定一個n個數(shù)排列，求有多少段長度為奇數(shù)的區(qū)間，中位數(shù)是b. n<=100000 時間限制0.1s

我一開始沒看到排列，想著怎么還能O(n)做的啊？？然后突然發(fā)現(xiàn)......

那就很簡單啦，把大于b的數(shù)看作1，小于的看作-1，從b往兩邊前綴和，答案就是兩邊前綴和L[x],R[y]互為相反數(shù)的(x,y)的對數(shù)。

#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define MN 200000 using namespace std; inline int read() {int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }int n,b,p,x=0,ans=0; int a[MN+5],L[MN+5];int main() {x=n=read();b=read();for(register int i=1;i<=n;++i){a[i]=read();if(a[i]>b)a[i]=1;else if(a[i]<b)a[i]=-1;else {a[i]=0;p=i;}}for(register int i=p-1;i;--i){x+=a[i];++L[x];}x=n;ans=++L[n];for(register int i=p+1;i<=n;++i)x-=a[i],ans+=L[x];printf("%d\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/FallDream/p/bzoj1303.html

總結

以上是生活随笔為你收集整理的[bzoj1303][CQOI2009]中位数图的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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