CDOJ1863 除草 [ODT]

Author Avatar
空気浮遊 2018年06月26日
  • 在其它设备中阅读本文章

一道珂树的有趣题目...

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;
}