zcmimi's blog
查看原题

点击跳转

很妙的一道题

对每位置i分别统计[l,i],l\in [1,i]的方案数

S_i表示\sum_{j=1}^i [H_i \ge X],pre为位置i-1的方案数,now为位置i的方案数

H_i\ge x,now=pre+\sum_{j=1}^i [S_j=S_i],这些位置是位置i-1不能满足而位置i可以满足的

H_i\le x,now=pre-\sum_{j=1}^i [S_j=S_{i-1}],这些位置是位置i不能满足而位置i-1可以满足的

这样就可以\Theta(n)解决了呢

记得开long long,S_0先赋值为n,防止负数re

#include<bits/stdc++.h>
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
const int N=100011;
int n,k,b[N<<1];
int main(){
    in(n,k);
    int x,pre=0,s=n;
    long long ans=0;
    b[s]=1;
    for(int i=1;i<=n;++i){
        in(x);
        if(x>=k)pre+=b[++s]+1;
        else pre-=b[s--]-1;
        ++b[s];
        ans+=pre;
    }
    printf("%lld\n",ans);
}
LG 3031 [USACO11NOV]Above the Median G
comment评论
Search
search