P1168 中位数

P1168 中位数
树状数组+二分答案。
树状数组就是起一个高效查询比二分出来的数小的有几个。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<ctime>
  7 #include<set>
  8 #include<map>
  9 #include<stack>
 10 #include<cstring>
 11 #define inf 2147483647
 12 #define For(i,a,b) for(register int i=a;i<=b;i++)
 13 #define p(a) putchar(a)
 14 #define g() getchar()
 15 //by war
 16 //2017.11.7
 17 using namespace std;
 18 int a[100010],b[100010],c[100010];
 19 int n;
 20 int t[100010];
 21 int x,l,r,mid;
 22 int now,Min;
 23 void in(int &x)
 24 {
 25     int y=1;
 26     char c=g();x=0;
 27     while(c<'0'||c>'9')
 28     {
 29     if(c=='-')
 30     y=-1;
 31     c=g();
 32     }
 33     while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+c-'0',c=g();
 34     x*=y;
 35 }
 36 
 37 void modify(int k)
 38 {
 39     for(;k<=n;k+=(-k)&k)
 40     t[k]++;
 41 }
 42 
 43 int get(int k)
 44 {
 45     int cnt=0;
 46     for(;k>0;k-=(-k)&k)
 47     cnt+=t[k];
 48     return cnt;
 49 }
 50 
 51 void o(int x)
 52 {
 53     if(x<0)
 54     {
 55         p('-');
 56         x=-x;
 57     }
 58     if(x>9)o(x/10);
 59     p(x%10+'0');
 60 }
 61 int main()
 62 {
 63     in(n);
 64     For(i,1,n)
 65     in(a[i]),b[i]=a[i];
 66     sort(b+1,b+n+1);
 67     int len=unique(b+1,b+n+1)-b-1;
 68     For(i,1,n)
 69     {
 70         x=a[i];
 71         a[i]=lower_bound(b+1,b+len+1,a[i])-b;
 72         c[a[i]]=x;
 73     }
 74     For(i,1,n)
 75     b[i]=0;
 76     o(c[a[1]]),p('
');
 77     b[a[1]]++;
 78     modify(a[1]);
 79     for(int i=3;i<=n;i+=2)
 80       {
 81           b[a[i]]++;
 82           b[a[i-1]]++;
 83           modify(a[i]);
 84           modify(a[i-1]);
 85           l=1,r=n;
 86           while(l<r)
 87           {
 88             mid=(l+r)>>1;
 89             if(b[mid]==0)
 90             {
 91                 now=get(mid);
 92                 if(now*2>i)
 93                 r=mid;
 94                 else
 95                 l=mid+1;
 96           }
 97           else
 98           if(b[mid]==1)
 99           {
100               now=get(mid-1);
101                 if(now*2+1==i)
102                 {
103                     o(c[mid]),p('
');
104                     break;
105             }
106             if(now*2>i)
107                 r=mid;
108                 else
109                 l=mid+1;
110           }
111           else
112           {
113               now=get(mid);
114               Min=get(mid-1);
115               if(now*2>=i&&Min*2<i)
116               {
117                     o(c[mid]),p('
');
118                     break;
119             }
120             if(Min*2>i)
121             r=mid;
122             else
123             l=mid+1;
124           }
125         }
126       }
127      return 0;
128 }