jzoj 3191. [selected by Zhongshan City 2013] vase line tree

Description

Little love receives flowers all day. She has N vases from 0 to N-1. If she receives F flowers, she will choose A vase A and try to put them in it. If the vase already has flowers, she will look for the next one in order until all the flowers have been put or there is no vase behind. Sometimes she would clean the vase and throw all the flowers between A and B (A < = b).

Input

The first line has two integers, N and M, representing the number of vases and operands.

Then the first number in each row of row M is K(1 or 2). If K is 1, then enter A and F, if K is 2, then enter A and B, meaning as above.

Output

Output one line per operation.

For operation 1, output the first position and the last position of the flower successfully placed. If a flower is not placed, output "Can not put any one.".

For operation 2, the output throws how many flowers.

Sample Input

10 5

1 3 5

2 4 5

1 1 8

2 3 6

1 8 8

Sample Output

3 7

2

1 9

4

Can not put any one.

Data Constraint

For 40% of the data, 1 ≤ N,M ≤ 100.

For 100% of the data, there are 1 ≤ N,M ≤ 50000.

Analysis: a line tree is used to maintain the number of vases with flowers in an interval. It's good to do whatever you want to ask. The dog number is 0~N-1.

code:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define N 50001
#define inf 0x3f3f3f3f
#define fo(i,a,b) for (int i=a;i<=b;i++)

using namespace std;

int n,m,q,x,y,l,r,ans1,ans2,mid,g;
struct node{int x,q;};
node t[3*N];

void change(int p,int l,int r,int x,int y,int c)
{
    if ((l==x) && (r==y))
    {
        if (c==0) t[p].x=0,t[p].q=0;
             else t[p].x=r-l+1,t[p].q=1;
        return;    
    }
    if (t[p].q==c) return;
    int mid=(l+r)/2;
    if (t[p].q!=2) t[p*2].q=t[p*2+1].q=t[p].q;
    if (t[p].q==1) t[p*2].x=mid-l+1,t[p*2+1].x=r-mid;
    if (t[p].q==0) t[p*2].x=0,t[p*2+1].x=0;
    t[p].q=2;
    if (y<=mid) change(p*2,l,mid,x,y,c);
     else 
     {
        if (x>=mid+1) change(p*2+1,mid+1,r,x,y,c);
         else 
         {

            change(p*2,l,mid,x,mid,c);
            change(p*2+1,mid+1,r,mid+1,y,c);
         }
     }
     t[p].x=t[p*2].x+t[p*2+1].x;
}

int find(int p,int l,int r,int x,int y)
{
    if ((l==x) && (r==y))
    {
        return t[p].x;
    }
    if (t[p].q==1) 
    {
        return y-x+1;
    }
    if (t[p].q==0)
    {
        return 0;
    }
    int sum=0;
    int mid=(l+r)/2;
    if (y<=mid) sum+=find(p*2,l,mid,x,y);
     else 
     {
        if (x>=mid+1) sum+=find(p*2+1,mid+1,r,x,y);
         else 
         {
            sum+=find(p*2,l,mid,x,mid);
            sum+=find(p*2+1,mid+1,r,mid+1,y);
         }
     }
    return sum; 
}

int main()
{
    scanf("%d%d",&n,&m);
    fo(i,1,m)
    {
        scanf("%d%d%d",&q,&x,&y);
        if (q==1)
        {
            x++;
            l=x; r=n; ans1=inf;
            while (l<=r)
            {
                mid=(l+r)/2;
                g=mid-x+1;
                if (g-find(1,1,n,x,mid)!=0)
                {
                    r=mid-1;
                    ans1=min(ans1,mid);
                }
                else l=mid+1; 
            }
            l=x; r=n; ans2=inf;
            y=min(y,n-x+1-find(1,1,n,x,n));
            while (l<=r)
            {
                mid=(l+r)/2;
                g=mid-x+1;
                if (g-find(1,1,n,x,mid)>=y)
                {
                    r=mid-1;
                    ans2=min(ans2,mid);
                }
                else l=mid+1;
            }           
            if (find(1,1,n,x,ans2)==ans2-x+1)  printf("Can not put any one.\n");
                                          else printf("%d %d\n",ans1-1,ans2-1);                             
            change(1,1,n,x,ans2,1);
        }
        else
        {
            x++; y++;
            ans1=find(1,1,n,x,y);
            change(1,1,n,x,y,0);
            printf("%d\n",ans1);
        }
    }
}

Posted on Fri, 01 May 2020 10:03:55 -0700 by jonniejoejonson