传送门 https://www.luogu.org/problem/P4198
分析
被线段树按在地上摩擦 先把左边转化成斜率, 那么这个题就转化成每次修改一个点的值, 输出前缀最大值的个数
考虑一次询问 (l,r,x), 表示 l 前面的数的最大值为 x, 区间(l,r) 内的前缀最大值, 那么每次就要输出询问(1,n,0)
用 dp 式子转移的思想对询问进行拆分
设 mid=(l+r)/2,mx(l,r)表示 l 到 r 内的最大值
如果 x>mx(l,mid), 那么就左半区间就不可能存在前缀最大值,(l,r,x)的结果就等于(mid,r,x)
如果 x<=mx(l,mid), 那么询问 (l,r,x) 就可以拆成 (l,mid,x) 与(mid+1,r,mx(l,mid)).
注意到 (mid+1,r,mx(l,mid)) 这个东西与 x 无关, 可以在插入值的时候就处理它
所以对于每个询问 (l,r,x) 真正需要现场求的是 (l,mid,x) 或(mid,r,x), 每次拆分区间长度减半, 可以做到 logn 的复杂度
至于每次插入值修改 (mid+1,r,mx(l,mid)) 时, 也可以用同样的方法, 总共有 logn 个区间, 每个区间处理的复杂度为 logn, 所以为 long^2n 的复杂度
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- const int maxn=100005;
- int n,m,vr[maxn<<2];double mx[maxn<<2];
- int que(int id,int l,int r,double L)
- {
- if(l==r)return mx[id]>L?1:0;
- int mid=(l+r)>>1;
- if(L<=mx[id<<1])return que(id<<1,l,mid,L)+vr[id];
- else return que(id<<1|1,mid+1,r,L);
- }
- void fix(int id,int l,int r,int k,double v)
- {
- if(l==r){mx[id]=v;return;}
- int mid=(l+r)>>1;
- k<=mid?fix(id<<1,l,mid,k,v):fix(id<<1|1,mid+1,r,k,v);
- mx[id]=max(mx[id<<1],mx[id<<1|1]);vr[id]=que(id<<1|1,mid+1,r,mx[id<<1]);
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1,x,y;i<=m;i++)
- scanf("%d%d",&x,&y),
- fix(1,1,n,x,double(y)/double(x)),
- printf("%d\n",que(1,1,n,0));
- }
[洛谷] P4198 楼房重建(线段树)
来源: http://www.bubuko.com/infodetail-3268773.html