bzoj2957 -- 线段树

2018-06-17 22:57:55来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

考虑线段树。对于一段区间,记录它的最大斜率和只考虑区间内约束的答案。

合并时一段区间的答案就是左子区间的答案加上右子区间考虑左子区间约束之和的答案。

求一个区间约束为h的答案时,判断左子区间与h的关系。如果不大于h,答案就是右子区间约束为h的答案,否则递归左子区间。

时间复杂度O(nlog2n)

代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 #define N 100010
 8 double c[N<<2];
 9 int i,j,k,n,m,a[N<<2],x,y,l,r,Mid,Ans=1;
10 inline double Max(double x,double y){return x<y?y:x;}
11 inline int Calc(int Node,int l,int r,double h){
12     if(l==r)return c[Node]>h;
13     int Mid=l+r>>1;
14     if(h>=c[Node<<1])return Calc(Node<<1|1,Mid+1,r,h);
15     return Calc(Node<<1,l,Mid,h)+a[Node]-a[Node<<1];
16 }
17 inline void Update(int Node,int l,int r,int x,double y){
18     if(l==r){c[Node]=y;a[Node]=1;return;}
19     int Mid=l+r>>1;
20     if(Mid>=x)Update(Node<<1,l,Mid,x,y);else Update(Node<<1|1,Mid+1,r,x,y);
21     c[Node]=Max(c[Node<<1],c[Node<<1|1]);
22     a[Node]=a[Node<<1]+Calc(Node<<1|1,Mid+1,r,c[Node<<1]);
23 }
24 int main(){
25     scanf("%d%d",&n,&m);
26     for(i=1;i<=m;i++){
27         scanf("%d%d",&x,&y);
28         Update(1,1,n,x,(double)y/x);
29         printf("%d\n",a[1]);
30     }
31     return 0;
32 }
bzoj2957

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:1012. 变换密码

下一篇:bzoj2209 [ JSOI2011 ] -- splay