HDU 4614 Vases and Flowers (2013多校第二场线段树)

题意摘自：http://blog.csdn.net/kdqzzxxcc/article/details/9474169 ORZZ

题意：给你N个花瓶，编号是0 到 N - 1 ，初始状态花瓶是空的，每个花瓶最多插一朵花。

然后有2个操作。
操作1，a b c ，往在a位置后面(包括a)插b朵花，输出插入的首位置和末位置。

操作2,a b ,输出区间[a , b ]范围内的花的数量，然后全部清空。

很显然这是一道线段树。区间更新，区间求和，这些基本的操作线段树都可以logN的时间范围内完成。

操作2，很显然就是线段树的区间求和，求出[a , b]范围内的花朵的数量，区间更新，将整个区间全部变成0。

操作1，这里我们首先需要找出他的首位置和末位置，所以需要二分他的位置。

首先我们二分他的首位置, l = a , r = n ，在这个区间内二分，找出第一个0的位置，那就是该操作的首位置pos1。

然后再二分他的末位置，l = pos1 , r = n ，找到第c个0，就是该操作的末位置pos2，然后区间更新[pos1 ,pos2]全部置为1。

tmp = n - minn + 1 - query(minn,n,1) ; 表示【minn,n】区间内空花瓶的个数，如果需要插的花束多余tmp，则只能插tmp束花。

这题重点在于二分找位置，找了半天终于在别人的帮助下调试出来了............

#include <iostream>

#include <algorithm>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <vector>

#include <set>

#include <queue>

#include <stack>

#include <climits>//形如INT_MAX一类的

#define MAX 100050

#define INF 0x7FFFFFFF

#define REP(i,s,t) for(int i=(s);i<=(t);++i)

#define ll long long

#define mem(a,b) memset(a,b,sizeof(a))

#define mp(a,b) make_pair(a,b)

#define L(x) x<<1

#define R(x) x<<1|1

# define eps 1e-5

//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂

using namespace std;

struct node {

    int r,l,mid;

    int lazy,sum;

} edge[4*MAX];

void up(int num) {

    edge[num].sum = edge[L(num)].sum + edge[R(num)].sum;

}

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

    edge[num].l = l;

    edge[num].r = r;

    edge[num].mid = (l+r) >> 1;

    edge[num].lazy = -1;

    if(l == r) {

        edge[num].sum = 0;

        return ;

    }

    build(l,edge[num].mid,L(num));

    build(edge[num].mid+1,r,R(num));

    //

    up(num);

}

void down(int num) {

    //if(edge[num].l == edge[num].r) return ;

    if(edge[num].lazy != -1) {

        edge[L(num)].lazy = edge[num].lazy;

        edge[R(num)].lazy = edge[num].lazy;

        edge[L(num)].sum = (edge[L(num)].r - edge[L(num)].l + 1) * edge[num].lazy;

        edge[R(num)].sum = (edge[R(num)].r - edge[R(num)].l + 1) * edge[num].lazy;

        edge[num].lazy = -1;

    }

}

void update(int l,int r,int num,int k) {

    if(l == edge[num].l && r == edge[num].r) {

        edge[num].lazy = k;

        edge[num].sum = (edge[num].r - edge[num].l + 1) * k;

        return ;

    }

    down(num);

    if(r <= edge[num].mid) {

        update(l,r,L(num),k);

    } else if(l > edge[num].mid) {

        update(l,r,R(num),k);

    } else {

        update(l,edge[num].mid,L(num),k);

        update(edge[num].mid + 1,r,R(num),k);

    }

    up(num);

}

int query(int l,int r,int num) {

    if(l == edge[num].l && r == edge[num].r) {

        return edge[num].sum;

    }

    down(num);

    if(r <= edge[num].mid) {

        return query(l,r,L(num));

    } else if(l > edge[num].mid) {

        return query(l,r,R(num));

    } else {

        return query(l,edge[num].mid,L(num)) + query(edge[num].mid + 1,r,R(num));

    }

}

void test(int n) {

    for(int i=1; i<=3*n; i++) {

        printf("l:%d r:%d sum:%d lazy:%d\n",edge[i].l,edge[i].r,edge[i].sum,edge[i].lazy);

    }

}

int main() {

    int n,m,i,t;

    cin >> t;

    while(t --) {

        scanf("%d%d",&n,&m);

        int a,b,c;

        build(1,n,1);

        for(i=0; i<m; i++) {

            scanf("%d%d%d",&a,&b,&c);

            if(a == 1) {

                int low = b + 1,high = n,mid,minn  = 2*n;

                if(n - low + 1 - query(low , n , 1) == 0) {

                    printf("Can not put any one.\n");

                    continue;

                }

                while(low <= high) {

                    mid = (low + high) >> 1;

                    if(mid - (b + 1) + 1- query(b+1,mid,1) >= 1) {

                        minn = min(minn,mid);

                        high = mid - 1;

                    } else {

                        low = mid + 1;

                    }

                }

                int tmp = n - minn + 1 - query(minn,n,1) ;

                if(c >= tmp) c = tmp;   ·

                low = minn,high = n;

                int maxx  = INF;

                while(low <= high) {

                    mid = (low + high) >> 1;

                    tmp = mid - minn + 1 - query(minn,mid,1) ;

                    if(tmp == c) {

                        maxx = min(maxx,mid);

                        high = mid - 1;

                    } else if(tmp > c) {

                        high = mid - 1;

                    } else {

                        low = mid + 1;

                    }

                }

                printf("%d %d\n",minn-1,maxx-1);

                update(minn,maxx,1,1);

            } else {

                printf("%d\n",query(b+1,c+1,1));

                update(b+1,c+1,1,0);

            }

        }

        puts("");

    }

    return 0;

}

这题重点在于二分找位置，找了半天终于在别人的帮助下调试出来了............

巴特西

HDU 4614 Vases and Flowers (2013多校第二场线段树)

最新文章

热门文章