bzoj2653 — 二分+主席树

对于每一个询问二分答案。

bzoj2653,bzoj

对于每一个询问二分答案。

设当前答案为x,将>=x的数的权值设为1,<x的数的权值设为-1。


[b+1,c-1]的权值和+[a,b]权值和最大的后缀+[c,d]权值和最大的前缀>=0时x可行。

先对每个数离散,然后以每个值建立主席树记录区间和、最大前缀、最大后缀就可以了。

时间复杂度:O(n*log3n)

 

代码:

图片 1

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 #define N 20010 8 struct Node{ 9 int l,r,s,lx,rx;10 }c[N*80];11 struct Ls{12 int w,f;13 }b[N];14 vector<int>g[N];15 int Num,i,j,k,l,r,Mid,n,m,Rt[N],Q,a[N],w[N],q[5],Ans;16 inline int Max(int x,int y){return x<y?y:x;}17 inline bool Cmp(Ls a,Ls b){return a.w<b.w;}18 inline void Up(int x){19 c[x].rx=Max(c[c[x].r].rx,c[c[x].l].rx+c[c[x].r].s);20 c[x].lx=Max(c[c[x].l].lx,c[c[x].r].lx+c[c[x].l].s);21 c[x].s=c[c[x].l].s+c[c[x].r].s;22 }23 inline void Build(int& x,int l,int r){24 if(x==0)x=++Num;25 if(l==r){26 c[x].lx=c[x].rx=c[x].s=1;27 return;28 }29 int Mid=l+r>>1;30 Build(c[x].l,l,Mid);31 Build(c[x].r,Mid+1,r);32 Up(x);33 }34 inline void Update(int& x,int y,int l,int r,int z){35 x=++Num;36 c[x]=c[y];37 if(l==r){38 c[x].lx=c[x].rx=0;39 c[x].s=-1;40 return;41 }42 int Mid=l+r>>1;43 if(z<=Mid)Update(c[x].l,c[y].l,l,Mid,z);else Update(c[x].r,c[y].r,Mid+1,r,z);44 Up(x);45 }46 inline int Query_sum(int x,int l,int r,int L,int R){47 if(l>=L&&r<=R)return c[x].s;48 int Mid=l+r>>1;49 int Ans=0;50 if(Mid>=L)Ans+=Query_sum(c[x].l,l,Mid,L,R);51 if(Mid<R)Ans+=Query_sum(c[x].r,Mid+1,r,L,R);52 return Ans;53 }54 inline int Query_rx(int x,int l,int r,int L,int R){55 if(l>=L&&r<=R)return c[x].rx;56 int Mid=l+r>>1;57 if(Mid>=R)return Query_rx(c[x].l,l,Mid,L,R);58 if(Mid<L)return Query_rx(c[x].r,Mid+1,r,L,R);59 return Max(Query_rx(c[x].r,Mid+1,r,L,R),Query_sum(c[x].r,Mid+1,r,L,R)+Query_rx(c[x].l,l,Mid,L,R));60 }61 inline int Query_lx(int x,int l,int r,int L,int R){62 if(l>=L&&r<=R)return c[x].lx;63 int Mid=l+r>>1;64 if(Mid>=R)return Query_lx(c[x].l,l,Mid,L,R);65 if(Mid<L)return Query_lx(c[x].r,Mid+1,r,L,R);66 return Max(Query_lx(c[x].l,l,Mid,L,R),Query_sum(c[x].l,l,Mid,L,R)+Query_lx(c[x].r,Mid+1,r,L,R));67 }68 int main(){69 scanf("%d",&n);70 for(i=1;i<=n;i++)scanf("%d",&b[i].w),b[i].f=i;71 sort(b+1,b+n+1,Cmp);72 w[1]=b[1].w;73 a[b[1].f]=m=1;74 g[1].push_back(b[1].f);75 for(i=2;i<=n;i++){76 if(b[i].w==b[i-1].w)a[b[i].f]=m;else a[b[i].f]=++m,w[m]=b[i].w;77 g[m].push_back(b[i].f);78 }79 Build(Rt[1],1,n);80 for(i=1;i<m;i++){81 Rt[i+1]=Rt[i];82 for(j=0;j<g[i].size();j++)83 Update(Rt[i+1],Rt[i+1],1,n,g[i][j]);84 }85 scanf("%d",&Q);86 while(Q--){87 for(i=1;i<=4;i++)scanf("%d",&q[i]),q[i]=(q[i]+w[Ans])%n+1;88 sort(q+1,q+5);89 l=1;r=m;90 while(l<=r){91 Mid=l+r>>1;92 if(Query_sum(Rt[Mid],1,m,q[2],q[3])+Query_rx(Rt[Mid],1,m,q[1],q[2]-1)+Query_lx(Rt[Mid],1,m,q[3]+1,q[4])>=0)Ans=Mid,l=Mid+1;else r=Mid-1;93 }94 printf("%d\n",w[Ans]);95 }96 return 0;97 }

bzoj2653

 

对于每一个询问二分答案。
设当前答案为x,将=x的数的权值设为1,x的数的权值设为-1。 当
[b+1,c-1]的权值和+[a,b]权值和最大的...

设当前答案为x,将>=x的数的权值设为1,<x的数的权值设为-1。


[b+1,c-1]的权值和+[a,b]权值和最大的后缀+[c,d]权值和最大的前缀>=0时x可行。

先对每个数离散,然后以每个值建立主席树记录区间和、最大前缀、最大后缀就可以了。

时间复杂度:O(n*log3n)

 

相关文章

Comment ()
评论是一种美德,说点什么吧,否则我会恨你的。。。