bzoj2957：楼房重建

题意：http://www.lydsy.com/JudgeOnline/problem.php?id=2957

sol  ：首先考虑转化问题，即给你一个斜率序列，让你动态维护单调栈

　　　考虑线段树，令get(x,r)表示以r为初值在节点x时会增加多少个数

　　　递归处理，get(x,r)=get(lson[x],r)+get(rson[x],max(mx[lson[x]],r))

　　　然而这样复杂度是爆炸的.....考虑预处理get(rson[x],mx[lson[x]])

　　　这样的话每次查询答案分为以下情况

　　　　　mx[lson[x]]>=r，这样的话右边已经预处理好了，递归左边即可

　　　　　mx[lson[x]]<r，这样的话左边的贡献为0，递归右边即可

　　　那么我们只需维护get(rson[x],mx[lson[x]])即可

　　　对于每次将位置pos修改为val，仅会对其右侧产生影响，分为以下情况

　　　　　若val<=mx[lson[x]],则对get(rson[x],mx[lson[x]])无影响

　　　　　若val>mx[lson[x]]，那么递归进右边处理

　　　最终复杂度O(n*log^2)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int Mx=400010;
int n,m,l[Mx],r[Mx],lson[Mx],rson[Mx],ans[Mx];
double maxn[Mx];

void build(int x,int L,int R)
{
    l[x]=L,r[x]=R;lson[x]=x*2,rson[x]=x*2+1;
    if(L==R) return ;
    int mid=(L+R)/2;
    build(lson[x],L,mid);
    build(rson[x],mid+1,R);
}

int cal(int x,double val)
{
    int L=l[x],R=r[x];
    if(L==R) return maxn[x]>val;
    if(maxn[lson[x]]<=val) return cal(rson[x],val);
    return ans[x]-ans[lson[x]]+cal(lson[x],val);
}

void change(int x,int pos,double c)
{
    int L=l[x],R=r[x],mid=(L+R)/2;
    if(L==R) { ans[x]=1,maxn[x]=c; return ; }
    if(pos<=mid) change(lson[x],pos,c);
    else change(rson[x],pos,c);
    maxn[x]=max(maxn[lson[x]],maxn[rson[x]]);
    ans[x]=ans[lson[x]]+cal(rson[x],maxn[lson[x]]);
}

int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        change(1,x,(double) y/x);
        printf("%d
",ans[1]);
    }
    return 0;
}