Vases and Flowers HDU - 4614

点击打开链接

难点在第一问求第一朵和最后一朵花的位置 共有两种方法

一 二分求解

#include <bits/stdc++.h>
using namespace std;
#define N 0x3f3f3f3f

struct node
{
    int l;
    int r;
    int val;
    int laz;
    int pre;
};

node tree[200010];
int n,s,e;

void pushup(int cur)
{
    tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;
    return;
}

void pushdown(int cur)
{
    if(tree[cur].laz)
    {
        tree[cur*2].val=tree[cur].pre*(tree[cur*2].r-tree[cur*2].l+1);
        tree[cur*2].laz=1;
        tree[cur*2].pre=tree[cur].pre;
        tree[cur*2+1].val=tree[cur].pre*(tree[cur*2+1].r-tree[cur*2+1].l+1);
        tree[cur*2+1].laz=1;
        tree[cur*2+1].pre=tree[cur].pre;
        tree[cur].laz=0;
        tree[cur].pre=0;
    }
    return;
}

void build(int l,int r,int cur)
{
    int m;
    tree[cur].l=l;
    tree[cur].r=r;
    tree[cur].val=0;
    tree[cur].laz=0;
    tree[cur].pre=0;
    if(l==r) return;
    m=(l+r)/2;
    build(l,m,cur*2);
    build(m+1,r,cur*2+1);
    return;
}

void update(int val,int ll,int rr,int cur)
{
    if(ll<=tree[cur].l&&tree[cur].r<=rr)
    {
        tree[cur].val=val*(tree[cur].r-tree[cur].l+1);
        tree[cur].laz=1;
        tree[cur].pre=val;
        return;
    }
    pushdown(cur);
    if(ll<=tree[cur*2].r) update(val,ll,rr,cur*2);
    if(rr>=tree[cur*2+1].l) update(val,ll,rr,cur*2+1);
    pushup(cur);
    return;
}

int query(int ll,int rr,int cur)
{
    int res;
    if(ll<=tree[cur].l&&tree[cur].r<=rr)
    {
        return tree[cur].val;
    }
    pushdown(cur);
    res=0;
    if(ll<=tree[cur*2].r) res+=query(ll,rr,cur*2);
    if(rr>=tree[cur*2+1].l) res+=query(ll,rr,cur*2+1);
    return res;
}

int finds(int tar,int val)
{
    int p,l,r,m,pre,ans;
    p=tar,l=tar,r=n-1;
    while(l<=r)
    {
        m=(l+r)/2;
        pre=query(p,m,1);
        if(m-p+1-pre==0)
        {
            l=m+1;
        }
        else if(m-p+1-pre==1)
        {
            ans=m;
            r=m-1;
        }
        else
        {
            r=m-1;
        }
    }
    return ans;
}

int finde(int tar,int val)
{
    int p,l,r,m,pre,ans;
    p=tar,l=tar,r=n-1;
    while(l<=r)
    {
        m=(l+r)/2;
        pre=query(p,m,1);
        if(m-p+1-pre<val)
        {
            l=m+1;
        }
        else if(m-p+1-pre==val)
        {
            ans=m;
            r=m-1;
        }
        else
        {
            r=m-1;
        }
    }
    return ans;
}

int main()
{
    int t,q,op,tar,val,pre,l,r;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&q);
        build(0,n-1,1);
        while(q--)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d",&tar,&val);
                pre=query(tar,n-1,1);
                if(pre==n-tar)
                {
                    printf("Can not put any one.\n");
                }
                else
                {
                    val=min(val,n-tar-pre);
                    s=finds(tar,val);
                    e=finde(tar,val);
                    printf("%d %d\n",s,e);
                    update(1,s,e,1);
                }
            }
            else
            {
                scanf("%d%d",&l,&r);
                printf("%d\n",query(l,r,1));
                update(0,l,r,1);
            }
        }
        printf("\n");
    }
    return 0;
}
           

二 乱搞

还是对区间的操作 在线段树遍历过程中每遇到一个”空区间“  只要手里还有花就插 同时更新第一朵和最后一朵花的位置 插完就一路返回

#include <bits/stdc++.h>
using namespace std;
#define N 0x3f3f3f3f

struct node
{
    int l;
    int r;
    int val;
    int laz;
    int pre;
};

node tree[200010];
int n,s,e,val;

void pushup(int cur)
{
    tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;
    return;
}

void pushdown(int cur)
{
    if(tree[cur].laz)
    {
        tree[cur*2].val=tree[cur].pre*(tree[cur*2].r-tree[cur*2].l+1);
        tree[cur*2].laz=1;
        tree[cur*2].pre=tree[cur].pre;
        tree[cur*2+1].val=tree[cur].pre*(tree[cur*2+1].r-tree[cur*2+1].l+1);
        tree[cur*2+1].laz=1;
        tree[cur*2+1].pre=tree[cur].pre;
        tree[cur].laz=0;
        tree[cur].pre=0;
    }
    return;
}

void build(int l,int r,int cur)
{
    int m;
    tree[cur].l=l;
    tree[cur].r=r;
    tree[cur].val=0;
    tree[cur].laz=0;
    tree[cur].pre=0;
    if(l==r) return;
    m=(l+r)/2;
    build(l,m,cur*2);
    build(m+1,r,cur*2+1);
    return;
}

void update(int val,int ll,int rr,int cur)
{
    if(ll<=tree[cur].l&&tree[cur].r<=rr)
    {
        tree[cur].val=val*(tree[cur].r-tree[cur].l+1);
        tree[cur].laz=1;
        tree[cur].pre=val;
        return;
    }
    pushdown(cur);
    if(ll<=tree[cur*2].r) update(val,ll,rr,cur*2);
    if(rr>=tree[cur*2+1].l) update(val,ll,rr,cur*2+1);
    pushup(cur);
    return;
}

int queryI(int ll,int rr,int cur)
{
    int res;
    if(ll<=tree[cur].l&&tree[cur].r<=rr)
    {
        return tree[cur].val;
    }
    pushdown(cur);
    res=0;
    if(ll<=tree[cur*2].r) res+=queryI(ll,rr,cur*2);
    if(rr>=tree[cur*2+1].l) res+=queryI(ll,rr,cur*2+1);
    return res;
}

void queryII(int ll,int rr,int cur)
{
    if(tree[cur].r-tree[cur].l+1==tree[cur].val||val<=0) return;
    if(ll<=tree[cur].l&&tree[cur].r<=rr)
    {
        if(tree[cur].val==0)
        {
            s=min(s,tree[cur].l),e=max(e,min(tree[cur].l+val-1,tree[cur].r));
            val-=(min(tree[cur].l+val-1,tree[cur].r)-tree[cur].l+1);
            return;
        }
    }
    if(tree[cur].l==tree[cur].r) return;
    pushdown(cur);
    if(ll<=tree[cur*2].r) queryII(ll,rr,cur*2);
    if(rr>=tree[cur*2+1].l) queryII(ll,rr,cur*2+1);
    return;
}

int main()
{
    int t,q,op,tar,l,r;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&q);
        build(0,n-1,1);
        while(q--)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d",&tar,&val);
                s=N,e=-N;
                queryII(tar,n-1,1);
                if(s==N&&e==-N)
                {
                    printf("Can not put any one.\n");
                }
                else
                {
                    printf("%d %d\n",s,e);
                    update(1,s,e,1);
                }
            }
            else
            {
                scanf("%d%d",&l,&r);
                printf("%d\n",queryI(l,r,1));
                update(0,l,r,1);
            }
        }
        printf("\n");
    }
    return 0;
}