题解：P11453 [USACO24DEC] Deforestation S

· · 题解

P11453 Deforestation 题解

介绍一种和堆贪心正解不同，更加直白好想，用树状数组或线段树的方法。

Preface

这题堆贪心正解还是挺难想的。 赛时想出了这个解法，但是因为是银组懒得写树状数组拿了前五个点就跳了去做第三题，没想到第三题虽然想出正解居然没调出来，痛失金组。赛后老老实实写树状数组这题秒了。哭死。

Problem statement

P11453 解释的比较清楚了。

Solution

首先发现砍树不好想，考虑最少种几棵树。 发现希望每棵树满足尽量多的区间。 尝试贪心，考虑按右端点升序排序，对于每一个区间肯定尽量种最靠右的树。

这样我们就有了一个 O(nk) 的贪心暴力，因为每砍一棵树需要将他做了贡献的区间需要种的树的数量减一。

想优化就需要一个能够快速统计一个区间里已经种了多少棵树的数据结构，考虑线段树或树状数组。每次维护之前右端点较小的区间已经在目前这个区间里种了多少棵树，这次就可以少种这么多棵。

同时注意到我们还需要一个数据结构，支持二分最大的比目前右端点小的树，和删除树两种操作，我用了 multiset。

Code

/*
I hate this problem
it's a good problem, but I really could've solved it in contest
I was so dumb
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct seg{
    int l, r, val, ori;
    const bool operator<(const seg &a) const{
        if(r != a.r)return r<a.r;
        else return l < a.l;
        //always remember to write the ELSE!!!!!!!
    }
} a[100005];
struct event{
    int pos, typ, ori, val;
    const bool operator<(const event &a) const{
        return pos < a.pos;
    }
}eve[300005];
int cmp(int x,int y){//for sort
    return x>y;
}
int n, t, k, p[100005], ans, c[300005], v[300005];
//position of each tree
int rang;
void add(int x, int y){
    for(int i = x; i <= rang; i += i & -i){
        c[i] += y;
    }
}
int get(int x){
    int anst = 0;
    for(int i = x; i > 0; i -= i & -i){
        anst += c[i];
    }
    return anst;
}
signed main(){
    std::ios::sync_with_stdio(0);
    cin>>t;
    while(t--){
        cin>>n>>k;
        ans = n;
        vector<int> e[100005];      
        for(int i = 1; i <= n; i++){
            int x;
            cin>>x;
            eve[i].pos = x;
            eve[i].typ = 0;//a tree is type 0
            eve[i].ori = i;//the ith tree
        }
        for(int i = 1; i <= k; i++){
            int x, y, z;
            cin>>x>>y>>z;
            eve[2 * i - 1 + n].pos = x;
            eve[2 * i - 1 + n].typ = 1;//type1 = region left end
            eve[2 * i - 1 + n].ori = i;
            eve[2 * i - 1 + n].val = z;
            eve[2 * i + n].pos = y;
            eve[2 * i + n].typ = 2;//type2 = right end
            eve[2 * i + n].ori = i;
            eve[2 * i + n].val = z;
        }
        sort(eve + 1, eve + n + 2 * k + 1);
        int rank = 0;
        eve[0].pos = 1e9 + 10;//out of bound
        for(int i = 1; i <= n + 2 * k; i++){
            if(eve[i].pos != eve[i - 1].pos)rank++;
            if(eve[i].typ == 0){
                //a tree
                p[eve[i].ori] = rank;
            }else{
                if(eve[i].typ == 1){
                    a[eve[i].ori].l = rank;
                    a[eve[i].ori].val = eve[i].val;
                }else{
                    a[eve[i].ori].r = rank;
                }
            }
        }
        //discretization done
        sort(a + 1, a + k + 1);
        //ascending regarding right end
        sort(p + 1, p + n + 1);
        //sort so we can binary search
        rang = n + 2 * k;
        //range
        multiset<int> tr;
        for(int i = 1; i <= rang; i++)c[i] = 0;     
        for(int i = 1; i <= n; i++){
            tr.insert(p[i]);
        }
        for(int i = 1; i <= k; i++){
            int now = get(a[i].r) - get(a[i].l - 1);
            if(now >= a[i].val)continue;
            a[i].val -= now;
            //region already satisfied
            auto it = tr.upper_bound(a[i].r);
            it--;
            while(a[i].val){
                //take this tree
                a[i].val--;
                ans--;
                add(*it, 1);
                tr.erase(it--);
                //first erase then --
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Result

Result

这场银组真的好简单，三道题我都想出解了虽然两道都没过及格线还这么低。