昨天上课老师讲尽量把学过的知识点总结一下，，，以后尽量写写博客吧，

  • Vases and Flowers

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4614
看到花瓶只有放花不放花这两种状态，应该很快就可以想到01代替状态，
操作2中的求一段区间中有花的瓶数就可以转化为求区间和问题，
操作1中要求区间x~n中，满足有 y个0的第一个区间左右端点。（第一个0的位置，最后一个0的位置）
如果没有0就输出can't，（这里求一个区间和就可以了）
怎么找到区间里第一个0？
一段区间内0的个数肯定是递增的，
那么二分查找第一个满足区间内1的个数和为1的位置，
最后一个零的位置同理。 

	
	

		#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=5e4+10;
#define INF   0x3f3f3f3f
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
	


	

		int n,m;
int tr[MAXN<<4];
int cov[MAXN<<4];
void pushdown(int rt,int l,int r)
{
    int ls=rt<<1,rs=rt<<1|1;
    int  mid=(l+r)>>1;
    cov[ls]=cov[rs]=cov[rt];
    if(cov[rt]==0)
        tr[ls]=tr[rs]=0;
    else
    {
        tr[ls]=mid-l+1;
        tr[rs]=r-mid;
    }
    cov[rt]=-1;
}
int quesum(int x,int y,int rt,int l,int r)
{
    if(x>r||y<l) return 0;
    if(x<=l&&y>=r) return tr[rt];
    if(cov[rt]!=-1) pushdown(rt,l,r);
    int  mid=(l+r)>>1;
    int ans=0;
    ans+=quesum(x,y,rt<<1,l,mid);
    ans+=quesum(x,y,rt<<1|1,mid+1,r);
    return ans;
}
int quezero(int x,int y,int cnt)
{
    int l=x,r=y;
    while(l<r)
    {
        int mid=(l+r)>>1;
        int temp=mid-x+1-quesum(x,mid,1,1,n);
        if(temp>=cnt)//
            r=mid;
        else
            l=mid+1;
    }
    return l;
}
void update(int x,int y,int v,int rt,int l,int r)
{
    if(x>r||y<l) return;
    if(x<=l&&y>=r)
    {
        tr[rt]=v*(r-l+1);
        cov[rt]=v;
        return;
    }
    if(cov[rt]!=-1) pushdown(rt,l,r);
    int  mid=(l+r)>>1;
    update(x,y,v,rt<<1,l,mid);
    update(x,y,v,rt<<1|1,mid+1,r);
    tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
int main()
{
    int t;s1(t);
    while(t--)
    {
        s2(n,m);
        mem(tr,0);mem(cov,-1);
        for(int i=0;i<m;i++)
        {
            int f,x,y;
            s3(f,x,y);
            if(f==1)
            {
                x++;
                int zero=n-x+1-quesum(x,n,1,1,n);
                if(zero==0)
                    printf("Can not put any one.\n");
                else
                {
                    int u=quezero(x,n,1);
                    int v=quezero(u,n,min(y,zero));
                    printf("%d %d\n",u-1,v-1);
                    update(u,v,1,1,1,n);
                }
            }
            else
            {
                x++;y++;
                printf("%d\n",quesum(x,y,1,1,n));
                update(x,y,0,1,1,n);
            }
        }
        endll;
    }
    return 0;
}