这个思想是挺好的...
存斜率, 其实就是问有多少个数比它前面的数都大, 这样的数能成为答案
考虑用线段树维护每个线段树区间 $x$ 内的最大值 $mx_x$ 和答案 $s_x$
我们要计算 $s_x$,$ls_x$ 贡献的答案就是 $s_{ls_x}$,$rs_x$ 贡献的答案是 (在 $rs_x$ 中有多少个能成为答案且 $\gt mx_{ls_x}$ 的数)
$\text{calc}(x,v)$: 在 $x$ 中有多少个能成为答案且 $\gt v$ 的数
如果 $v\geq mx_{ls_x}$, 那么答案只可能在 $rs_x$ 中, 直接递归即可
否则答案就是 $\text{calc}(ls_x,v)+\text{calc}(rs_x,mx_{ls_x})$, 注意到 $\text{calc}(rs_x,mx_{ls_x})=s_x-s_{ls_x}$, 所以只需递归 $ls_x$
一次单点修改维护 $O\left(\log_2n\right)$ 次 $s$, 所以总时间复杂度是 $O\left(n\log_2^2n\right)$
- #include<stdio.h>
- typedef double du;
- du max(du a,du b){return a>b?a:b;}
- du mx[400010];
- int s[400010];
- int calc(du v,int l,int r,int x){
- if(l==r)return mx[x]>v;
- int mid=(l+r)>>1;
- if(v>=mx[x<<1])
- return calc(v,mid+1,r,x<<1|1);
- else
- return s[x]-s[x<<1]+calc(v,l,mid,x<<1);
- }
- void modify(int p,du v,int l,int r,int x){
- if(l==r){
- mx[x]=v;
- s[x]=1;
- return;
- }
- int mid=(l+r)>>1;
- if(p<=mid)
- modify(p,v,l,mid,x<<1);
- else
- modify(p,v,mid+1,r,x<<1|1);
- mx[x]=max(mx[x<<1],mx[x<<1|1]);
- s[x]=s[x<<1]+calc(mx[x<<1],mid+1,r,x<<1|1);
- }
- int main(){
- int n,m,x,y;
- scanf("%d%d",&n,&m);
- while(m--){
- scanf("%d%d",&x,&y);
- modify(x,y/(du)x,1,n,1);
- printf("%d\n",s[1]);
- }
- }
[BZOJ2957] 楼房重建
来源: http://www.bubuko.com/infodetail-2683006.html