目录

BZOJ1303 中位数图

题解

有点考验思维的一题。对于这个排列，我们实际上并不需要知道这个排列中每个数的值，实际上我们只需要知道这个数是否比\(b\)大就行了。所以我们先把所有的数都转化成1或者-1，表示这个数比\(b\)大或者小。然后记\(sum[i]\)为修改之后前\(i\)个数的和，然后再记\(l[i]\)表示在\(b\)左边，前缀和为\(i-n\)的位置的个数，记\(r[i]\)表示在\(b\)右边，前缀和为\(i-n\)的位置的个数。对于相同的\(i\)，每一个\(l[i]\)和\(r[i]\)都是一组合法的答案，因为这两个前缀和相减为0，即这一段区间内比\(b\)大的个数与比\(b\)小的个数是相同的。这样\(b\)就是中位数了，然后答案就是\(\sum_{i=0}^{2n}l[i]*r[i]\)。

ｃｏｄｅ

#include 
    
     using namespace std;typedef long long ll;bool Finish_read;template
     
      inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}template
      
       inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
       
        inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
        
         inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}/*================Header Template==============*/#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);const int maxn=1e5+500;int n,b,st;int a[maxn],sum[maxn],l[maxn<<2],r[maxn<<2];/*==================Define Area================*/int main() {    read(n);read(b);    for(int i=1;i<=n;i++) {        read(a[i]);        if(a[i]>b) a[i]=1;        else if(a[i]