HDU - 6315 Naive Operations (线段树+思维) 2018 Multi-University Training Contest 2

题意：数量为N的序列a和b，a初始全为0，b为给定的1-N的排列。有两种操作：1.将a序列区间[L,R]中的数全部+1；2.查询区间[L,R]中的 ∑⌊ai/bi⌋（向下取整)

分析：对于一个位置i，如果ai<bi，那么该位置不能对结果做出贡献；而当某一次操作后，ai>=bi了，就对结果的贡献值+1。那么可以用在线段树的结点中维护每个区间的最大a和最小b，和已经产生的贡献cnt。如果一个区间中最大的a超过了b，那么就说明此次更新操作使该区间的结果产生了变化，那么就要向下找到那个产生贡献的位置。当更新完结果值以后，就将这个位置上的bi再加上bi（由于结果要求向下取整），那么相当于这个位置的ai又要重新更新bi次才能再次产生贡献。

所以，update函数中，如果出现a>=b的情况，那么我们必须递归到最底层找到出现；如果a<b，那么只要打上延迟标记即可。

#include<bits/stdc++.h>

#define Lson rt<<1,l,m

#define Rson rt<<1|1,m+1,r

using namespace std;

typedef long long LL;

const int maxn =1e5+;

struct Node{

    int cnt,addv,maxa,minb;

}tree[maxn<<];

int b[maxn];

void pushup(int rt)

{

    tree[rt].cnt = tree[rt<<].cnt+tree[rt<<|].cnt;

    tree[rt].maxa = max(tree[rt<<].maxa,tree[rt<<|].maxa);

    tree[rt].minb = min(tree[rt<<].minb,tree[rt<<|].minb);

}

void pushdown(int rt)

{

    if(tree[rt].addv){

        int v=tree[rt].addv;

        tree[rt].addv=;

        tree[rt<<].maxa+=v;

        tree[rt<<|].maxa+=v;

        tree[rt<<].addv+=v;

        tree[rt<<|].addv+=v;

    }

}

void build(int rt,int l,int r)

{

    tree[rt].addv=;

    if(l==r){

        tree[rt].cnt = tree[rt].maxa = ;

        tree[rt].minb = b[l];

        return;

    }

    int m = (l+r)>>;

    build(Lson);

    build(Rson);

    pushup(rt);

}

void update(int rt,int l,int r,int L,int R)

{

    if(L<=l && R>=r){

        tree[rt].maxa++;

        if(tree[rt].maxa<tree[rt].minb){    //还没有元素做出贡献

            tree[rt].addv++;

            return;

        }

        else if(l==r){

            tree[rt].cnt++;

            tree[rt].minb+=b[l];

            return;

        }

    }

    pushdown(rt);

    int m = (l+r)>>;

    if(L<=m)update(Lson,L,R);

    if(R>m)update(Rson,L,R);

    pushup(rt);

}

int query(int rt,int l,int r,int L,int R)

{

    if(L<=l&&R>=r) return tree[rt].cnt;

    int m =(l+r)>>;

    pushdown(rt);

    int ans=;

    if(L<=m) ans+=query(Lson,L,R);

    if(R>m) ans+=query(Rson,L,R);

    return ans;

}  

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int T,N,M,u,v,tmp;

    while(scanf("%d%d",&N,&M)==){

        for(int i=;i<=N;++i)  scanf("%d",&b[i]);

        build(,,N);

        char op[];

        int L,R;

        while(M--){

            scanf("%s %d %d",op,&L,&R);

            if(op[]=='a') update(,,N,L,R);

            else printf("%d\n",query(,,N,L,R));

        }

    }

    return ;

}

巴特西

HDU - 6315 Naive Operations (线段树+思维) 2018 Multi-University Training Contest 2

最新文章

热门文章