【Leetcode】1109. Corporate Flight Bookings（第144周周赛）（线段树模版题）

深碍√TFBOYSˉ_ 2021-12-14 04:51 113阅读 0赞

There are `n` flights, and they are labeled from `1` to `n`.

We have a list of flight bookings. The `i`\-th booking `bookings[i] = [i, j, k]` means that we booked `k`seats from flights labeled `i` to `j` inclusive.

Return an array `answer` of length `n`, representing the number of seats booked on each flight in order of their label.

**Example 1:**

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
    Output: [10,55,45,25,25]

**Constraints:**

*  `1 <= bookings.length <= 20000`
 *  `1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000`
 *  `1 <= bookings[i][2] <= 10000`

题目大意：

给出多个区间(x,y)的值k，这些区间可能会被覆盖，我们需要输出每个多次更新之后，每个位置的数值大小。

解题思路：

线段树模板题。

#define lc (p<<1)
    #define rc (p<<1|1)
    long long n,m,a[100010]; 
    struct node{
    	int l,r,lazy;//延迟标记——lazy
    	long long sum; 
    }T[100010*4];
    void pushnow(long long p,long long v){
    	T[p].sum+=(T[p].r-T[p].l+1)*v;
    	T[p].lazy+=v;
    } 
    void pushdown(long long p){
    	if(T[p].lazy){
    		pushnow(lc,T[p].lazy);
    		pushnow(rc,T[p].lazy);
    		T[p].lazy=0;
    	}
    }
    void pushup(long long p){
    	T[p].sum=T[lc].sum+T[rc].sum;
    }
    void build(long long p,long long l,long long r){//建树 
    	T[p].l=l;
    	T[p].r=r;
    	if(l==r){
    		T[p].sum=a[l];
    		T[p].lazy=0;
    		return ;
    	}
    	long long mid=(l+r)>>1;
    	build(lc,l,mid);
    	build(rc,mid+1,r);
    	pushup(p); 
    }
    void update(long long p,long long ql,long long qr,long long v){//向上维护 
    	if(ql<=T[p].l&&T[p].r<=qr){
    		pushnow(p,v);
    		return ;
    	}
    	long long mid=(T[p].l+T[p].r)>>1;
    	pushdown(p);
    	if(ql<=mid)
    		update(lc,ql,qr,v);
    	if(qr>mid)
    		update(rc,ql,qr,v);
    	pushup(p);
    } 
    long long query(long long p,long long ql,long qr){//区间求和 
    	if(ql<=T[p].l&&qr>=T[p].r)
    		return T[p].sum;
    	long long mid=(T[p].l+T[p].r)>>1;
    	pushdown(p);
    	long long ans=0;
    	if(ql<=mid)
    		ans+=query(lc,ql,qr);
    	if(qr>mid)
    		ans+=query(rc,ql,qr);
    	pushup(p);
    	return ans; 
    }
    
    class Solution {
    public:
        vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
            memset(a, 0, sizeof(a));
            build(1,1,100000);
            for(long long i=1;i<=bookings.size();i++){
                long long x,y,k;
                x = bookings[i-1][0];
                y = bookings[i-1][1];
                k = bookings[i-1][2];
                update(1,x,y,k);
            } 
            
            vector<int> ans;
            for(int i = 1;i<=n;i++){
                long long x, y;
                x = i, y=i;
                int tmp_ans = (int)query(1,x,y);
                ans.push_back(tmp_ans);
            }
            return ans;
        }
    };