首页 > 其他 > 详细

洛谷 3871 [TJOI2010]中位数

时间:2018-10-21 00:25:10      阅读:35      评论:0      收藏:0      [点我收藏+]

标签:earch   print   lin   search   arc   alt   truct   int   cstring   

技术分享图片

【题解】 

   平衡树模板题,不过因为可以离线,所以有别的做法。把询问倒着做,变成删掉数字、求中位数,于是可以二分+树状数组。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define LL long long
 5 #define rg register
 6 #define N 500010
 7 using namespace std;
 8 int n,m,cnt,top,b[N],t[N],ans[N];
 9 struct rec{
10     int num,pos;
11 }a[N];
12 struct que{
13     int opt,num;
14 }q[N];
15 inline int read(){
16     int k=0,f=1; char c=getchar();
17     while(c<0||c>9)c==-&&(f=-1),c=getchar();
18     while(0<=c&&c<=9)k=k*10+c-0,c=getchar();
19     return k*f;
20 }
21 inline void add(int x,int y){for(;x<=n;x+=x&-x)t[x]+=y;}
22 inline int query(int x){int ret=0;for(;x;x-=x&-x)ret+=t[x]; return ret;}
23 inline int search(int x){
24     int l=0,r=n;
25     while(l+1<r){
26         int mid=(l+r)>>1;
27         if(query(mid)>=x) r=mid; else l=mid;
28     }
29 //    printf("l=%d r=%d\n",l,r);
30     return r;
31 }
32 inline bool cmp(rec a,rec b){return a.num<b.num;} 
33 int main(){
34     n=read();
35     for(rg int i=1;i<=n;i++) a[i].num=read();
36     m=read();
37     for(rg int i=1;i<=m;i++){
38         char c=getchar();
39         while(c!=a&&c!=m) c=getchar();
40         if(c==a){
41             q[i].opt=1,q[i].num=a[++n].num=read();
42             a[n].pos=i;
43         }
44         else q[i].opt=2;
45     }
46     sort(a+1,a+1+n,cmp);
47     for(rg int i=1;i<=n;i++) add(i,1);
48     for(rg int i=1;i<=n;i++)if(a[i].pos) b[a[i].pos]=i;
49 //    printf("n=%d\n",n);
50     for(rg int i=m;i;i--){
51         if(q[i].opt==1){
52             add(b[i],-1); cnt++;
53         }
54         else ans[++top]=a[search((n-cnt)/2+(n-cnt)%2)].num;
55     }
56     while(top) printf("%d\n",ans[top--]);
57     return 0;
58 }

 

洛谷 3871 [TJOI2010]中位数

标签:earch   print   lin   search   arc   alt   truct   int   cstring   

原文:https://www.cnblogs.com/DriverLao/p/9823456.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号