題意：給n個數，每次詢問a,b,c,d,你要選定一個區間使得該區間中位數最大，其中a,b為區間左端點可選范圍，c,d同理。

OTZ陳老師出的神題。

先考慮一個簡單問題：只有一個詢問的情況。此時我們二分中位數，并且將區間內小中位數的數標為-1，大于的標為1，此時區間最大和如果大等0，則說明中位數可以變大，然后二分下去就可以了。

加上詢問之后，我們就要維護這樣一個區間最大和了。考慮主席樹，我們對于每一個值，建出它對應的1，-1樹，然后二分，到對應的樹上去求最大區間和就好了。那么問題來了，怎么維護這樣一個最大區間和呢？首先，我們有必選區間b,c所以我要把這個區間的和算上，對于可選區間a,b-1和c+1,d，我們要求一個最大前后綴和。這個東西可以這樣求（以前綴和為例）：max(左兒子sum+右兒子前綴，左兒子前綴)。

那么整體思路出來了：先建出一棵全線段樹（全為1），然后我們把原序列排個序（要把下標對應好），然后一個一個按順序丟進樹里，把小等自己的變為-1，以供這個數的后一個數查詢時使用。 然后我們二分答案，對于當前答案去樹上找最大區間和，如果大等0則滿足條件。

這道題主席樹建出來，第一維度是權值，第二維度是下標。我一開始想的一二唯獨是反的，而大神說這樣有問題，一直沒想通哪里有問題。。。再去和大神討論一下。

寫這道題寫得異常艱難。先是在想二分會不會有問題（實際是不會的，因為題目弄出來的中位數在偶數個時會選擇較大的那個）昨天晚上寫了第一版，有點問題，第二天寫了第二版，還是有問題，什么沒有排序導致沒有正確性啊，建樹不分配編號啊什么的。然后各種改，終于過了（感謝ihopenot大佬）。

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 20005 4 #define M 400005 5 #define CT Chairman_Tree 6 int n,Q,p[5],ans; 7 struct data{ 8 int num,pos; 9 bool operator < (const data& w)const{ 10 if(num==w.num) return pos<w.pos; 11 return num<w.num; 12 } 13 }a[N]; 14 namespace Chairman_Tree{ 15 struct node{ 16 int son[2],sum,ls,rs; 17 }tr[M]; 18 int sz,root[N]; 19 void build(int& x,int l,int r){ 20 x=++sz; 21 tr[x].ls=tr[x].rs=tr[x].sum=r-l+1; 22 if(l==r) return; 23 int mid=(l+r)>>1; 24 build(tr[x].son[0],l,mid); 25 build(tr[x].son[1],mid+1,r); 26 } 27 void insert(int x,int& y,int l,int r,int lim){ 28 tr[y=++sz].sum=tr[x].sum-2; 29 if(l==r){ 30 tr[y].ls=tr[y].rs=0; 31 return; 32 } 33 memcpy(tr[y].son,tr[x].son,sizeof(tr[y].son)); 34 int mid=(l+r)>>1,LS,RS; 35 if(lim>mid) insert(tr[x].son[1],tr[y].son[1],mid+1,r,lim); 36 else insert(tr[x].son[0],tr[y].son[0],l,mid,lim); 37 LS=tr[y].son[0],RS=tr[y].son[1]; 38 tr[y].ls=max(tr[LS].sum+tr[RS].ls,tr[LS].ls); 39 tr[y].rs=max(tr[RS].sum+tr[LS].rs,tr[RS].rs); 40 } 41 inline void insert(int i) {insert(root[i],root[i+1],1,n,a[i].pos);} 42 int query(int x,int L,int R,int l,int r){ 43 if(L==l && R==r) return tr[x].sum; 44 int mid=(L+R)>>1; 45 if(r<=mid) return query(tr[x].son[0],L,mid,l,r); 46 else if(mid<l) return query(tr[x].son[1],mid+1,R,l,r); 47 else return query(tr[x].son[0],L,mid,l,mid)+query(tr[x].son[1],mid+1,R,mid+1,r); 48 } 49 int lquery(int x,int L,int R,int l,int r){ 50 if(L==l && R==r) return tr[x].ls; 51 int mid=(L+R)>>1; 52 if(r<=mid) return lquery(tr[x].son[0],L,mid,l,r); 53 else if(mid<l) return lquery(tr[x].son[1],mid+1,R,l,r); 54 else { 55 int t1=query(tr[x].son[0],L,mid,l,mid)+lquery(tr[x].son[1],mid+1,R,mid+1,r),t2=lquery(tr[x].son[0],L,mid,l,mid); 56 return max(t1,t2); 57 } 58 } 59 int rquery(int x,int L,int R,int l,int r){ 60 if(L==l && R==r) return tr[x].rs; 61 int mid=(L+R)>>1; 62 if(r<=mid) return rquery(tr[x].son[0],L,mid,l,r); 63 else if(mid<l) return rquery(tr[x].son[1],mid+1,R,l,r); 64 else { 65 int t1=rquery(tr[x].son[0],L,mid,l,mid)+query(tr[x].son[1],mid+1,R,mid+1,r),t2=rquery(tr[x].son[1],mid+1,R,mid+1,r); 66 return max(t1,t2); 67 } 68 } 69 } 70 using namespace CT; 71 inline int read(){ 72 int x=0,f=1; char a=getchar(); 73 while(a<'0' || a>'9') {if(a=='-') f=-1; a=getchar();} 74 while(a>='0' && a<='9') x=x*10+a-'0',a=getchar(); 75 return x*f; 76 } 77 inline bool jud(int x){ 78 return rquery(root[x],1,n,p[1],p[2]-1)+query(root[x],1,n,p[2],p[3])+lquery(root[x],1,n,p[3]+1,p[4])>=0; 79 } 80 int main(){ 81 n=read(); 82 for(int i=1;i<=n;i++) a[i]=(data){read(),i}; 83 build(root[1],1,n); 84 sort(a+1,a+1+n); 85 for(int i=1;i<n;i++) insert(i); 86 Q=read(); 87 while(Q--){ 88 int l=1,r=n; 89 for(int i=1;i<=4;i++) p[i]=(read()+ans)%n+1; 90 sort(p+1,p+5); 91 while(l<r){ 92 int mid=(l+r+1)>>1; 93 if(jud(mid)) l=mid; 94 else r=mid-1; 95 } 96 ans=a[l].num; printf("%d\n",ans); 97 } 98 return 0; 99 }

?

轉載于:https://www.cnblogs.com/enigma-aw/p/6202920.html

總結

以上是生活随笔為你收集整理的bzoj2653: middle的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。