题目: https://www.lydsy.com/JudgeOnline/problem.php?id=2957
线段树. 每个点记录斜率, 要一个单增的序列长度(从 1 开始).
线段树每个点记录自己区间的 max 和单增长度, pushup 的时候通过 mx [ ls ]判断往哪个儿子递归.
需要注意的是当右儿子的长度全部可以加上是, 不能加 s [ rs ], 因为不一定全在总的单增序列上 (只有 rs 中大于 mx[ls] 的那一部分);
所以右儿子的贡献应该是原先总区间的 s 减去左儿子的 s, 因为单增序列从最左端开始, 总序列中左儿子肯定全在.
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #define ll long long
- using namespace std;
- const int N=1e5+5;
- int n,m,x,s[N<<2];
- double z,mx[N<<2];
- int dg(int cur,double lm,int l,int r)
- {
- if(l==r)return mx[cur]>lm;
- int ls=(cur<<1),rs=(cur<<1|1);
- if(mx[ls]<=lm)return dg(rs,lm,((l+r)>>1)+1,r);
- return dg(ls,lm,l,((l+r)>>1))+s[cur]-s[ls];
- }
- void pushup(int bh,int l,int r)
- {
- int ls=(bh<<1),rs=(bh<<1|1);
- mx[bh]=mx[ls];s[bh]=s[ls];
- if(mx[rs]<=mx[ls])return;
- mx[bh]=mx[rs];
- // printf("()l=%d r=%d mx=%lf\n",l,r,mx[bh]);
- s[bh]+=dg(rs,mx[ls],((l+r)>>1)+1,r);
- }
- void add(int bh,int l,int r)
- {
- int mid=((l+r)>>1);
- if(l==r){
- mx[bh]=z;s[bh]=1;//bh, 不是 l
- // printf("l=%d r=%d mx=%lf s=%d\n",l,r,mx[bh],s[bh]);
- return;
- }
- if(x<=mid)add(bh<<1,l,mid);
- else add(bh<<1|1,mid+1,r);
- pushup(bh,l,r);
- // printf("l=%d r=%d mx=%lf s=%d\n",l,r,mx[bh],s[bh]);
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++)
- {
- scanf("%d%lf",&x,&z);z/=x;
- add(1,1,n);
- printf("%d\n",s[1]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2579016.html