遇事不決，二分試試

解析

很好的一道題
真是把主席樹玩明白了
一個關于中位數的常用trick：

二分答案mid，把>=mid的看成1，<mid的看成-1，然后看最大子段和是否>=0

然而如果對離散化后的每一個值建一棵小白逛公園那樣的線段樹顯然時空雙炸
這里主席樹就用上了
注意到關于相鄰的值域所建的兩棵主席樹只有個別值從1變成-1
所以就用主席樹優化時空即可
時間復雜度$mlog{n}^2$，空間復雜度$nlogn$

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=20050; inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m; int tot,r[N]; struct node{int sum,l,r; }; struct tree{int ls,rs;node o; }tr[N*20]; inline node merge(node a,node b){node res;res.sum=a.sum+b.sum;res.l=max(a.l,a.sum+b.l);res.r=max(b.r,b.sum+a.r);return res; } #define pushup(k) tr[k].o=merge(tr[tr[k].ls].o,tr[tr[k].rs].o) inline int copy(int x){tr[++tot]=tr[x];return tot; } #define mid ((l+r)>>1) void build(int &k,int l,int r){k=copy(k);if(l==r){tr[k].o=(node){1,1,1};return;}build(tr[k].ls,l,mid);build(tr[k].rs,mid+1,r);pushup(k);//printf("k=%d (%d %d) sum=%d l=%d r=%d\n",k,l,r,tr[k].o.sum,tr[k].o.l,tr[k].o.r); } void upd(int &k,int l,int r,int p,int v){k=copy(k);if(l==r){tr[k].o=(node){v,max(v,0),max(v,0)};return;}if(p<=mid) upd(tr[k].ls,l,mid,p,v);else upd(tr[k].rs,mid+1,r,p,v);pushup(k);return; } node ask(int k,int l,int r,int x,int y){//printf(" k=%d (%d %d) x=%d y=%d sum=%d\n",k,l,r,x,y,tr[k].o.sum);if(x<=l&&r<=y) return tr[k].o;else if(y<=mid) return ask(tr[k].ls,l,mid,x,y);else if(x>mid) return ask(tr[k].rs,mid+1,r,x,y);else return merge(ask(tr[k].ls,l,mid,x,y),ask(tr[k].rs,mid+1,r,x,y)); } int a[N],q[N],num; vector <int>v[N]; int w[5]; bool check(int k,int a,int b,int c,int d){//printf("check:k=%d x=%d (%d %d) (%d %d)\n",k,q[k],a,b,c,d);node o=ask(r[k],1,n,b,c),u=ask(r[k],1,n,a,b-1),v=ask(r[k],1,n,c+1,d);//printf("res=%d+%d+%d\n\n",o.sum,u.r,v.l);return o.sum+u.r+v.l>=0; } int main(){n=read();for(int i=1;i<=n;i++) a[i]=q[i]=read();sort(q+1,q+1+n);num=unique(q+1,q+1+n)-q-1;for(int i=1;i<=n;i++){a[i]=lower_bound(q+1,q+1+num,a[i])-q;v[a[i]].push_back(i);}build(r[1],1,n);for(int i=1;i<num;i++){r[i+1]=r[i];for(int j=0;j<v[i].size();j++){int pl=v[i][j];upd(r[i+1],1,n,pl,-1);}}m=read();int lst=0;for(int i=1;i<=m;i++){for(int j=1;j<=4;j++) w[j]=(read()+lst)%n;sort(w+1,w+1+4);int a=w[1],b=w[2],c=w[3],d=w[4];a++;b++;c++;d++;int st=1,ed=num;while(st<ed){int o=(st+ed+1)>>1;if(check(o,a,b,c,d)) st=o;else ed=o-1;}printf("%d\n",lst=q[st]);}return 0; }

總結

以上是生活随笔為你收集整理的YBTOJ洛谷P2839：最大中位数（主席树、二分答案）的全部內容，希望文章能夠幫你解決所遇到的問題。

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