线段树二分

左手的ㄟ右手 2023-01-07 10:13 113阅读 0赞

# 题目来源： #

https://vjudge.net/problem/HDU-4614

# 题目描述： #

线段树二分

# 解题思路： #

二分

# 参考代码： #

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=1e6+10;
    #define lch (root<<1)
    #define rch (root<<1|1)
    struct tnode{
        int lazy,sum;}t[MAXN];
    int n,m;
    void pushup(int root)
    {
        
        t[root].sum=t[lch].sum+t[rch].sum;
    }
    void pushdown(int root,int l,int r)
    {
        
        if(t[root].lazy==-1)return;
        int mid=(l+r)>>1;
        t[lch].lazy=t[root].lazy;
        t[lch].sum=(mid-l+1)*t[root].lazy;
    
        t[rch].lazy=t[root].lazy;
        t[rch].sum=(r-mid)*t[root].lazy;
    
        t[root].lazy=-1;
    }
    void build(int root,int l,int r)
    {
        
        t[root].lazy=-1;
        if(l==r)
        {
        
            t[root].sum=1;
            return;
        }
        int mid=(l+r)>>1;
        build(lch,l,mid);
        build(rch,mid+1,r);
        pushup(root);
    }
    void fugai(int root,int l,int r,int ql,int qr,int v)
    {
        
        if(l>qr||r<ql)return;
        if(l>=ql&&r<=qr)
        {
        
            t[root].lazy=v;
            t[root].sum=(r-l+1)*v;
            return;
        }
        pushdown(root,l,r);
        int mid=(l+r)>>1;
        fugai(lch,l,mid,ql,qr,v);
        fugai(rch,mid+1,r,ql,qr,v);
        pushup(root);
    }
    int sum(int root,int l,int r,int ql,int qr)
    {
        
        if(l>qr||r<ql)return 0;
        if(l>=ql&&r<=qr)return t[root].sum;
        pushdown(root,l,r);
        int mid=(l+r)>>1;
        return sum(lch,l,mid,ql,qr)+sum(rch,mid+1,r,ql,qr);
    }
    int query(int root,int l,int r,int f)
    {
        
       if(l==r)return l;
       pushdown(root,l,r);
       int mid=(l+r)>>1;
       if(t[lch].sum>=f)return query(lch,l,mid,f);
       else return query(rch,mid+1,r,f-t[lch].sum);
    }
    void solve()
    {
        
        cin>>n>>m;
        build(1,1,n);
        while(m--)
        {
        
            int op,A,F;
            scanf("%d%d%d",&op,&A,&F);
            if(op==1){
        
                A++;
                int t=sum(1,1,n,A,n);
                int per=sum(1,1,n,1,A-1);
                if(t==0){
        
                    cout<<"Can not put any one.\n";
                }else {
        
                   F=min(t,F);
                 int  l=query(1,1,n,per+1),r=query(1,1,n,F+per);
                    cout<<(l-1)<<" "<<(r-1)<<endl;
                   fugai(1,1,n,l,r,0);
                }
            }else{
        
                A++;F++;
                int res=(F-A+1)-sum(1,1,n,A,F);
                fugai(1,1,n,A,F,1);
                cout<<res<<"\n";
            }
        }
        cout<<"\n";
    }
    int main()
    {
        
        int T;cin>>T;while(T--){
        solve();}
    
        return 0;
    }
    
    ```cpp
    在这里插入代码片