【BZOJ】4293: [PA2015]Siano 线段树上二分

【题意】给定n棵高度初始为0的草，每天每棵草会长高a[i]，m次收割，每次在d[i]天将所有>b[i]的草收割到b[i]，求每次收割量。n<=500000。

【算法】线段树上二分

【题解】按照生长速度a[]排序后，容易发现数列永远单调。

在线段树上的区间维护以下值：

1.最后一棵草的高度a

2.上次收割日期b

3.总的草高和c

4.总的生长速度和d

5.收割标记D和B

上传的时候注意右区间收割晚于左区间时强制合并。

下传的时候注意标记D和B直接覆盖。

线段树上二分：

1.判断当前区间是否符合（一般为区间最右端点），否则返回r+1

2.若l=r，返回。

3.查询左区间。

4.若左区间不符合，查询右区间。

过程中可以顺便查询答案和修改标记。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cctype>

#define int long long

using namespace std;

int read(){

    int s=,t=;char c;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

const int maxn=;

int a[maxn],sum,n,m;

struct tree{int l,r,a,b,c,d,B,D;}t[maxn*];

void modify(int k,int B,int D){t[k].B=B;t[k].D=D;t[k].a=B;t[k].b=D;t[k].c=B*(t[k].r-t[k].l+);}

void up(int k){

    t[k].a=t[k<<|].a;

    t[k].b=t[k<<|].b;

    t[k].c=t[k<<].c+t[k<<].d*(t[k<<|].b-t[k<<].b)+t[k<<|].c;

}

void down(int k){

    if(t[k].D){

        modify(k<<,t[k].B,t[k].D);modify(k<<|,t[k].B,t[k].D);

        t[k].B=t[k].D=;

    }

}

void build(int k,int l,int r){

    t[k].l=l;t[k].r=r;

    if(l==r){t[k].a=;t[k].b=;t[k].c=;t[k].d=a[l];return;}

    int mid=(l+r)>>;

    build(k<<,l,mid);build(k<<|,mid+,r);

    up(k);

    t[k].d=t[k<<].d+t[k<<|].d;

}

void plus(int k,int D,int B){sum+=t[k].c+t[k].d*(D-t[k].b)-B*(t[k].r-t[k].l+);modify(k,B,D);}

int find(int k,int D,int B){

    if(t[k].a+a[t[k].r]*(D-t[k].b)<=B)return t[k].r+;

    if(t[k].l==t[k].r){

        plus(k,D,B);

        return t[k].r;

    }

    down(k);

    int num;

    if((num=find(k<<,D,B))<=t[k<<].r){

        plus(k<<|,D,B);

    }

    else num=find(k<<|,D,B);

    up(k);

    return num;

}

#undef int

int main(){

#define int long long

    n=read();m=read();

    for(int i=;i<=n;i++)a[i]=read();

    sort(a+,a+n+);

    build(,,n);

    while(m--){

        int D=read(),B=read();

        sum=;

        find(,D,B);

        printf("%lld\n",sum);

    }

    return ;

}

写复杂的题目前一定要列好程序草稿，把细节都写清楚，程序写出来就会比较清晰，不容易犯错。

原来这么复杂的题目也是可以1A的（躺