首页 > > 程序设计 > C/C++ >

bzoj2957 -- 线段树

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

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

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

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

时间复杂度O(nlog²n)

代码：

 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 }