首页 > 其他 > 详细

Bzoj 2653: middle

时间:2018-02-24 23:56:34      阅读:146      评论:0      收藏:0      [点我收藏+]

标签:固定   问题   end   cst   不可   %d   post   script   ins   

Description

一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。回答Q个这样的询问:s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中,最大的中位数。

其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。

Input

第一行序列长度n。接下来n行按顺序给出a中的数。

接下来一行Q。然后Q行每行a,b,c,d,我们令上个询问的答案是x(如果这是第一个询问则x=0)。令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。将q从小到大排序之后,令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。

输入保证满足条件。第一行所谓“排过序”指的是从大到小排序!

Output

Q行依次给出询问的答案。

Sample Input

5

170337785

271451044

22430280

969056313

206452321

3

3 1 0 2

2 3 1 4

3 1 4 0

Sample Output

271451044

271451044

969056313

HINT

n<=20000,Q<=25000

 

思路好题。先简化一下问题,如果是求一个固定区间的中位数,这样求中位数可以二分,验证的话...可以把比当前二分出的答案mid小的数设为-1,大于等于mid的设为1,然后求这一段的和如果大于等于0说明mid是一个可行解,否则就不是。区间和用线段树维护,相当于对于每一个不同的mid,都对应一棵不同的线段树,貌似不可做。可以先让mid=0,那么原序列就全为1,但是mid每增加一次,最多改变原序列的一个值,那么就可以用可持久化线段树了。先排序,每次修改一个位置(把1变成-1),就可以解决简化版问题了。有了这样的做法,问题其实已经解决了,排好序的q数组写成a,b,c,d,显然必须取的区间是[b,c],然后最优解就是再加上[a,b-1]从b-1向左的最大子段和和[c+1,d]从c+1向右的最大子段和,让可持久化线段树去维护区间和和最大子段和,问题解决。

下面贴代码:

 

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<cmath>
  6 using namespace std;
  7 struct node{
  8     int id,val;
  9     friend bool operator <(const node &a,const node &b){
 10         return a.val<b.val;
 11     }
 12 }in[20010];
 13 struct seg{int lson,rson,sum,ll,rr;}tree[400010];
 14 int q[4],root[20010],st,ed,n,ans,fz,cnt=1;
 15 void merge(seg &pos,seg &lson,seg &rson){
 16     pos.ll=max(lson.ll,lson.sum+rson.ll);
 17     pos.rr=max(rson.rr,rson.sum+lson.rr);
 18     pos.sum=lson.sum+rson.sum;
 19     return;
 20 }
 21 void build(int l,int r,int pos){
 22     tree[pos].ll=tree[pos].rr=tree[pos].sum=r-l+1;
 23     if(l==r) return;
 24     int mid=(l+r)/2;
 25     tree[pos].lson=++cnt;
 26     tree[pos].rson=++cnt;
 27     build(l,mid,tree[pos].lson);
 28     build(mid+1,r,tree[pos].rson);
 29     return;
 30 }
 31 void insert(int l,int r,int pos,int las){
 32     if(l==r){
 33         tree[pos].ll=tree[pos].rr=tree[pos].sum=-1;
 34         return;
 35     }
 36     int mid=(l+r)/2;
 37     if(st<=mid){
 38         tree[pos].lson=++cnt;
 39         tree[pos].rson=tree[las].rson;
 40         insert(l,mid,tree[pos].lson,tree[las].lson);
 41     }
 42     else{
 43         tree[pos].rson=++cnt;
 44         tree[pos].lson=tree[las].lson;
 45         insert(mid+1,r,tree[pos].rson,tree[las].rson);
 46     }
 47     merge(tree[pos],tree[tree[pos].lson],tree[tree[pos].rson]);
 48     return;
 49 }
 50 int find(int l,int r,int pos){
 51     if(st<=l&&r<=ed) return tree[pos].sum;
 52     int mid=(l+r)/2;
 53     if(ed<=mid) return find(l,mid,tree[pos].lson);
 54     if(mid<st) return find(mid+1,r,tree[pos].rson);
 55     return find(l,mid,tree[pos].lson)+find(mid+1,r,tree[pos].rson);
 56 }
 57 void findl(int l,int r,int pos){
 58      if(st<=l&&r<=ed){
 59          ans=max(ans,fz+tree[pos].rr);
 60          fz+=tree[pos].sum;
 61          return;
 62      }
 63      int mid=(l+r)/2;
 64      if(mid<ed) findl(mid+1,r,tree[pos].rson);
 65      if(st<=mid) findl(l,mid,tree[pos].lson);
 66      return;
 67 }
 68 void findr(int l,int r,int pos){
 69     if(st<=l&&r<=ed){
 70         ans=max(ans,fz+tree[pos].ll);
 71         fz+=tree[pos].sum;
 72         return;
 73     }
 74     int mid=(l+r)/2;
 75     if(st<=mid) findr(l,mid,tree[pos].lson);
 76     if(mid<ed) findr(mid+1,r,tree[pos].rson);
 77     return;
 78 }
 79 int erfen(){
 80     int l=0,r=n+1,mid,val;
 81     while(l<r){
 82         mid=(l+r)/2;
 83         st=q[1],ed=q[2];
 84         if(st<=ed) val=find(1,n,root[mid]);
 85         else val=0;
 86         st=q[0],ed=q[1]-1,ans=fz=0;
 87         if(st<=ed) findl(1,n,root[mid]);
 88         val+=ans;
 89         st=q[2]+1,ed=q[3],ans=fz=0;
 90         if(st<=ed) findr(1,n,root[mid]);
 91         val+=ans;
 92         if(val>=0) l=mid+1;
 93         else r=mid;
 94     }
 95     printf("%d\n",in[l].val);
 96     return in[l].val;
 97 }
 98 int main()
 99 {
100     int m,i,las=0;
101     scanf("%d",&n);
102     for(i=1;i<=n;i++){
103         scanf("%d",&in[i].val);
104         in[i].id=i;
105     }
106     sort(in+1,in+n+1);
107     root[0]=1;
108     build(1,n,1);
109     for(i=1;i<=n;i++){
110         root[i]=++cnt;
111         st=in[i].id;
112         insert(1,n,root[i],root[i-1]);
113     }
114     scanf("%d",&m);
115     for(i=1;i<=m;i++){
116         scanf("%d%d%d%d",&q[0],&q[1],&q[2],&q[3]);
117         q[0]=(q[0]+las)%n+1,q[1]=(q[1]+las)%n+1;
118         q[2]=(q[2]+las)%n+1,q[3]=(q[3]+las)%n+1;
119         sort(q,q+4);
120         las=erfen();
121     }
122     return 0;
123 }

 

Bzoj 2653: middle

标签:固定   问题   end   cst   不可   %d   post   script   ins   

原文:https://www.cnblogs.com/pncbf/p/8467940.html

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

鲁公网安备 37021202000002号