bzoj2653 -- 二分+主席树
2018-06-17 22:47:54来源:未知 阅读 ()
对于每一个询问二分答案。
设当前答案为x,将>=x的数的权值设为1,<x的数的权值设为-1。
当 [b+1,c-1]的权值和+[a,b]权值和最大的后缀+[c,d]权值和最大的前缀>=0时x可行。
先对每个数离散,然后以每个值建立主席树记录区间和、最大前缀、最大后缀就可以了。
时间复杂度:O(n*log3n)
代码:
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:1079 回家
- 剑指offer65:矩阵中的路径(二维数组,二分查找) 2019-09-02
- 二分法(一):二分法的基本思想 2019-08-16
- 二分法(四):采用二分法解决“最大化平均值”问题 2019-08-16
- 二分法(二):采用二分法解决“最小化最大值问题” 2019-08-16
- 洛谷 P3386 【模板】二分图匹配 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash