Problem

https://acm.uestc.edu.cn/problem/chu-cao/description

有 n 棵草，起始高度均为 0，每棵草每天长高 vi。有 m 个除草计划 (di, hi)：在第 di 天结束后，将所有草超过 hi 的部分除掉，输出除掉部分的总高度和。n,m≤5⋅105, vi≤106, di,hi≤1012，保证 di 递增。

Solution

先 orz 一下 YYJ<- 权值线段树做法，而我连权值线段树是什么都不知道

菜鸡就只能讲讲怎么用 ODT 来水这个东西了

由于每次除草范围都是全部，因此考虑按照长高的速度给草排序。
由此易知，草在任意时刻都是严格不递减的。

考虑用 ODT 维护合并区间，则我们找到的区间的共性有：上一次除草的时间和初始高度。
于是使用四元组 $(l,r,s,d)$ 来维护这个信息（$s$ 为初始高度，$d$ 为上次除草时间）。

我们发现每一次我们都会从中间的某一部分除草，将后面的部分全部除掉，与此同时后面的部分显然被合并为同一个区间。

现在主要想办法找到中间的部分，考虑二分。

对于一个四元组区间 $(l,r,s,d)$，若现在除草的高度为 $H$，现在的时间为 $D$，我们需要找到要给最小的 $v_i$ 使得 $s+(D-d)v_i\geq H$。

我们对每一个四元组区间二分，如果二分出来的为四元组区间的左端，则继续二分，直到找到你想要找的东西。

至于怎么二分，你可以自己写一个，也可以用一下lower_bound的自定义比较函数，这部分可以在我博客里查查 STL 的函数。

把那个点找出来了，剩下的怎么处理也就不难了吧。

以及 STL 真可怕啊。

最后关于时间复杂度：
每次二分最多遍历 $n$ 个区间。
而产生这 $n$ 个区间你得先做 $n$ 遍操作。
之后这 $n$ 个区间会被立马删除（合并为一个区间）。

我们可以考虑为每次操作最多会产生两个区间（被分割的区间删除，一半被合并，一半成为新的区间）。
这个区间最多被遍历 + 删除一次。
则最多生成 $2m$ 个区间。
作 $4m$ 次操作。
则复杂度约为 $O(m\log m)$。

PS：由于本题的区间维护一些特殊性，可以用链表维护（逃）

Code

// Code by ajcxsu
// Problem: cut grass

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T> void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=5e5+10;
ll v[N], S[N];
struct Seg {
    int l, r;
    ll s, d;
    Seg(int L, int R=0, ll S=0, ll D=0):l(L), r(R), s(S), d(D) {}
    bool operator < (const Seg &a) const {
        return l<a.l;
    }
} ;

ll rua, rub;
bool cmp(const ll &a, const ll &b) { return rua+rub*a<b; }

set<Seg> s;

set<Seg>::iterator split(int pos) {
    auto it=s.lower_bound(Seg(pos));
    if(it!=s.end() && it->l==pos) return it;
    --it;
    if(pos>it->r) return s.end();
    Seg na=*it;
    s.erase(it);
    s.insert(Seg(na.l, pos-1, na.s, na.d));
    return s.insert(Seg(pos, na.r, na.s, na.d)).first;
}

void assign(int L, int R, ll S, ll D) {
    split(L);
    auto itr=split(R+1), itl=split(L);
    s.erase(itl, itr);
    s.insert(Seg(L, R, S, D));
}

int main() {
    int n, m;
    gn(n), gn(m);
    for(int i=1;i<=n;i++) gn(v[i]);
    sort(v+1, v+1+n);
    for(int i=1;i<=n;i++) S[i]=S[i-1]+v[i];
    s.insert(Seg(1, n, 0, 0));
    ll d, h;
    while(m--) {
        gn(d), gn(h);
        bool found=0;
        ll tot=0;
        for(auto it=s.rbegin(); it!=s.rend(); it++) {
            rua=it->s, rub=d-it->d;
            int t=lower_bound(v+it->l, v+it->r+1, h, cmp)-v;
            if(t!=it->l) {
                printf("%lld\n", tot+(it->r-t+1)*rua+(S[it->r]-S[t-1])*rub-(n-t+1)*h);
                assign(t, n, h, d);
                found=1;
                break;
            }
            else tot+=(it->r-it->l+1)*rua+(S[it->r]-S[it->l-1])*rub;
        }
        if(!found) {
            assign(1, n, h, d);
            printf("%lld\n", tot-n*h);
        }
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-cdoj-1863.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议进行许可☆

网站

加入讨论吧...