首页 > ACM题库 > HDU-杭电 > HDU 4614-Vases and Flowers-线段树-[解题报告]HOJ
2015
09-17

HDU 4614-Vases and Flowers-线段树-[解题报告]HOJ

Vases and Flowers

问题描述 :

  Alice is so popular that she can receive many flowers everyday. She has N vases numbered from 0 to N-1. When she receive some flowers, she will try to put them in the vases, one flower in one vase. She randomly choose the vase A and try to put a flower in the vase. If the there is no flower in the vase, she will put a flower in it, otherwise she skip this vase. And then she will try put in the vase A+1, A+2, …, N-1, until there is no flower left or she has tried the vase N-1. The left flowers will be discarded. Of course, sometimes she will clean the vases. Because there are too many vases, she randomly choose to clean the vases numbered from A to B(A <= B). The flowers in the cleaned vases will be discarded.

输入:

  The first line contains an integer T, indicating the number of test cases.
  For each test case, the first line contains two integers N(1 < N < 50001) and M(1 < M < 50001). N is the number of vases, and M is the operations of Alice. Each of the next M lines contains three integers. The first integer of one line is K(1 or 2). If K is 1, then two integers A and F follow. It means Alice receive F flowers and try to put a flower in the vase A first. If K is 2, then two integers A and B follow. It means the owner would like to clean the vases numbered from A to B(A <= B).

输出:

  The first line contains an integer T, indicating the number of test cases.
  For each test case, the first line contains two integers N(1 < N < 50001) and M(1 < M < 50001). N is the number of vases, and M is the operations of Alice. Each of the next M lines contains three integers. The first integer of one line is K(1 or 2). If K is 1, then two integers A and F follow. It means Alice receive F flowers and try to put a flower in the vase A first. If K is 2, then two integers A and B follow. It means the owner would like to clean the vases numbered from A to B(A <= B).

样例输入:

2
10 5
1 3 5
2 4 5
1 1 8
2 3 6
1 8 8
10 6
1 2 5
2 3 4
1 0 8
2 2 5
1 4 4
1 2 3

样例输出:

[pre]3 7
2
1 9
4
Can not put any one.

2 6
2
0 9
4
4 5
2 3

[/pre]

题意:给你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 ,找到第b个0,就是该操作的末位置pos2,然后区间更新[pos1 ,pos2]全部置为1。

这两个二分写得时候要相当注意,很容易出错!

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 50100
#define lson (pos<<1)
#define rson (pos<<1|1)
struct node
{
    int l,r,tag,sum;
} tree[N*4];

void build(int pos, int l, int r)
{
    tree[pos].l=l;
    tree[pos].r=r;
    tree[pos].tag=0;
    tree[pos].sum=r-l+1;
    if(l==r)return ;
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
}
void pushdown(int pos)
{
    if(tree[pos].tag)
    {
        if(tree[pos].tag==2)
        {
            tree[lson].sum=(tree[lson].r-tree[lson].l+1);
            tree[lson].tag=2;
            tree[rson].sum=(tree[rson].r-tree[rson].l+1);
            tree[rson].tag=2;
            tree[pos].tag=0;
        }
        else
        {
            tree[lson].sum=0;
            tree[lson].tag=1;
            tree[rson].sum=0;
            tree[rson].tag=1;
            tree[pos].tag=0;
        }
    }
}
void pushup(int pos)
{
    tree[pos].sum=tree[lson].sum+tree[rson].sum;
}
void update(int pos, int L, int R, int v)
{
    if(L<=tree[pos].l&&tree[pos].r<=R)
    {
        if(v==1)
        {
            tree[pos].tag=1;
            tree[pos].sum=0;
        }
        else if(v==2)
        {
            tree[pos].tag=2;
            tree[pos].sum=tree[pos].r-tree[pos].l+1;
        }
        return ;
    }
    pushdown(pos);
    int mid=(tree[pos].l+tree[pos].r)/2;
    if(L<=mid)update(lson,L,R,v);
    if(mid<R)update(rson,L,R,v);
    pushup(pos);
}

int query(int pos, int L, int R)
{
    if(L<=tree[pos].l&&tree[pos].r<=R)
    {
        return tree[pos].sum;
    }
    pushdown(pos);
    int mid=(tree[pos].l+tree[pos].r)/2;
    int ans=0;
    if(L<=mid)ans+=query(lson,L,R);
    if(mid<R)ans+=query(rson,L,R);
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        build(1,1,n);
        for(int i = 0; i < m; i++)
        {
            int id;
            scanf("%d",&id);
            if(id==1)
            {
                int A,B;
                int s, w;
                scanf("%d%d",&s,&w);
                s++;
                int sum=query(1,s,n);
                sum=min(w,sum);
                if(sum==0)
                {
                    printf("Can not put any one.\n");
                    continue;
                }
                int l=s,r=n;
                if(sum==1)
                {
                    if(query(1,l,l))
                    {
                        A=l;
                        B=l;
                        printf("%d %d\n",A-1,B-1);
                        update(1,A,B,1);
                        continue;
                    }
                }

                sum--;
                //printf("sum=%d\n",sum);
                while(l+1<r)
                {
                    int mid=(l+r)/2;
                    int tmp=query(1,s,mid);
                    //printf("mid=%d tmp=%d l=%d r=%d\n",mid,tmp,l,r);
                    if(tmp>sum)r=mid;
                    else l=mid;
                }
                B=r;
                l=s;
                r=B;
                if(sum==0)
                {
                    if(query(1,r,r))
                    {
                        A=r;
                        B=r;
                        printf("%d %d\n",A-1,B-1);
                        update(1,A,B,1);
                        continue;
                    }
                }
                while(l+1<r)
                {
                    int mid=(l+r)/2;
                    int tmp=query(1,mid,B);
                    if(tmp>sum)l=mid;
                    else r=mid;
                }
                A=l;
                printf("%d %d\n",A-1,B-1);
                update(1,A,B,1);
            }
            else if(id==2)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                a++;
                b++;
                int hehe=b-a+1-query(1,a,b);
                printf("%d\n",hehe);
                if(hehe!=0)
                    update(1,a,b,2);
            }

        }
        printf("\n");
    }
    return 0;
}
/*2
10 5
1 0 1
1 0 2
1 0 1
*/

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/hhaile/article/details/9499391