博客

原题链接



https://leetcode.cn/problems/booking-concert-tickets-in-groups/

存个模板，以备不时之需🧐

class BookMyShow {
    public int n;
    public int m;
    public MaxSegmentTree t1;
    public SumSegmentTree t2;
    public int lastLine=0;

    public BookMyShow(int n, int m) {
        this.n=n;
        this.m=m;
        t1=new MaxSegmentTree(0,n-1);
        t2=new SumSegmentTree(0,n-1);
        for(int i=0;i<n;i++){
            t1.change(t1.root,i,m);
            t2.change(t2.root,i,i,m);
        }
    }
    
    
    public int[] gather(int k, int maxRow) {
        if(t1.root.max<k)
            return new int[]{};
        int row=t1.ask(t1.root,k);
        if(row>maxRow)
            return new int[]{};
        int cur=(int)t2.ask(t2.root,row,row);
        t1.change(t1.root,row,cur-k);
        t2.change(t2.root,row,row,cur-k);
        return new int[]{row,m-cur};
    }
    
    public boolean scatter(int k, int maxRow) {
        int l=0;
        int r=maxRow;
        int idx=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(t2.ask(t2.root,0,mid)<k){
                idx=mid;
                l=mid+1;
            }else
                r=mid-1;
        }
        if(idx==maxRow)
            return false;
        long cur=0;
        if(idx!=-1){
            cur=t2.ask(t2.root,0,idx);
            t2.change(t2.root,0,idx,0);
        }
        for(int i=lastLine;i<=idx;i++){
            t1.change(t1.root,i,0);
        }
        lastLine=Math.max(idx,lastLine);
        long now=t2.ask(t2.root,idx+1,idx+1);
        t2.change(t2.root,idx+1,idx+1,now-(k-cur)); 
        t1.change(t1.root,idx+1,(int)(now-(k-cur))); 
        return true;
    }
    
     static class SumSegmentTree{
    	class Node{
    		int l;
    		int r;
    		long sum;
            long tag;
            Node lchild;
            Node rchild;
    		
    		public Node(int l,int r) {
    			this.l=l;
    			this.r=r;
                this.tag=-1;
    		}
            
            public Node(int l,int r,long tag,long sum){
                this.l=l;
    			this.r=r;
                this.tag=tag;
                this.sum=sum;
            }
    	}
    	public Node root;
        
        public SumSegmentTree(int l,int r){
            root=new Node(l,r);
        }
        
        
        public void pushUp(Node cur){
            cur.sum=0;
            if(cur.lchild!=null)
                cur.sum+=cur.lchild.sum;
            if(cur.rchild!=null)
                cur.sum+=cur.rchild.sum;
        }
    	
    	public void  pushDown(Node cur) {
            if(cur.tag!=-1){
                int mid=(cur.l+cur.r)/2;
                if(cur.lchild==null)
                    cur.lchild=new Node(cur.l,mid,cur.tag,cur.tag);
                else{
                    cur.lchild.tag=cur.tag;
                    cur.lchild.sum=cur.tag;
                }
                if(cur.rchild==null)
                    cur.rchild=new Node(mid+1,cur.r,cur.tag,cur.tag);
                else{
                    cur.rchild.tag=cur.tag;
                    cur.rchild.sum=cur.tag;
                }
            }
            cur.tag=-1;
    	}
    	
    	
    	public void change(Node cur,int l,int r,long val) {
    		if(cur.l>=l&&cur.r<=r) {
    			cur.tag=val;
    			cur.sum=val;
    			return ;
    		}
    		pushDown(cur);
    		int mid=(cur.l+cur.r)/2;
    		if(l<=mid){
                if(cur.lchild==null)
                    cur.lchild=new Node(cur.l,mid,0,0);
    			change(cur.lchild,l,r,val);
            }
    		if(r>mid){
                if(cur.rchild==null)
                    cur.rchild=new Node(mid+1,cur.r,0,0);
    			change(cur.rchild,l,r,val);
            }
            pushUp(cur);
    	}

        public long ask(Node cur,int l,int r){
            if(cur.l>=l&&cur.r<=r) {
    			return cur.sum;
    		}
    		pushDown(cur);
    		int mid=(cur.l+cur.r)/2;
            long ans=0;
    		if(l<=mid){
                if(cur.lchild==null)
                    cur.lchild=new Node(cur.l,mid,0,0);
    			ans+=ask(cur.lchild,l,r);
            }
    		if(r>mid){
                if(cur.rchild==null)
                    cur.rchild=new Node(mid+1,cur.r,0,0);
    			ans+=ask(cur.rchild,l,r);
            }
            pushUp(cur);
            return ans;
        }
    	
    }
    
    static class MaxSegmentTree{
    	class Node{
    		int l;
    		int r;
    		int max;
            Node lchild;
            Node rchild;
    		
    		public Node(int l,int r) {
    			this.l=l;
    			this.r=r;
    		}
            
            public Node(int l,int r,int max){
                this.l=l;
    			this.r=r;
                this.max=max;
            }
    	}
    	public Node root;
        
        public MaxSegmentTree(int l,int r){
            root=new Node(l,r);
        }
        
        
        public void pushUp(Node cur){
            cur.max=0;
            if(cur.lchild!=null)
                cur.max=Math.max(cur.max,cur.lchild.max);
            if(cur.rchild!=null)
                cur.max=Math.max(cur.max,cur.rchild.max);
        }
    	
    	public void change(Node cur,int idx,int val) {
    		if(cur.l==cur.r) {
    			cur.max=val;
    			return ;
    		}
    		int mid=(cur.l+cur.r)/2;
    		if(idx<=mid){
                if(cur.lchild==null)
                    cur.lchild=new Node(cur.l,mid);
    			change(cur.lchild,idx,val);
            }
    		if(idx>mid){
                if(cur.rchild==null)
                    cur.rchild=new Node(mid+1,cur.r);
    			change(cur.rchild,idx,val);
            }
            pushUp(cur);
    	}

        public int ask(Node cur,int val){
            if(cur.l==cur.r) {
    			return cur.l;
    		}
            int ans=0;
    		if(cur.lchild.max>=val){
    			return ask(cur.lchild,val);
            }else{
                return ask(cur.rchild,val);
            }
        }
    	
    }

}

/**
 * Your BookMyShow object will be instantiated and called as such:
 * BookMyShow obj = new BookMyShow(n, m);
 * int[] param_1 = obj.gather(k,maxRow);
 * boolean param_2 = obj.scatter(k,maxRow);
 */