题解 P4511 【[CTSC2015]日程管理】

wrpwrp · 2020-04-26 19:26:27 · 题解

更好的阅读体验

正题

一开始的时候显然第i天以前可以放i个任务是吧，然后考虑用一棵线段树维护这个数量，设每天的这个值为lev(i) 考虑在t这个截止时间位置放了一个任务，那(t,n)这个区间的 lev(i) 都要减去1。　　

插入

设插入的终止时间为t,这个任务的价值为p。那如何插入呢？

当这个任务与其他的任务不冲突的时候，直接加入完事。也就是当min(lev(t\rightarrow n))>0的时候不会冲突，然后直接加进去就完事了
当这个任务与其他任务冲突的时候，一个显然的想法就是替换掉最小的，或者不替换。那这个最小的值在哪里找呢。为了我们可以把当前的任务加进去，那原来的这个最小值的t2必须要比刚刚所说的(t,n)的最左边的lev(i)=0的i要小才可以释放空间让当前的任务可以插入。所以就在区间 (1,id) (id就是刚刚说的那个位置）找一个价值最小的任务替换掉，然后把替换掉的那个任务丢到没有用的一个集合。为什么是对的呢，因为如果不替换这个任务，那就要有一个更好的任务来替换这个任务，而这个任务比原来的要大，所以就要在中间额外插入一个任务，而显然这是做不到的，所以这个就是最优的了。　　
删除
显然要是没用这个任务直接删掉完事
~~其实这里你不用管就有20分了，岂不美哉？~~　如果用了的话，就在没有用的里面去找个最大的替换要删掉的那个任务就行了。万一找不到的话就不用管了呗。　然后剩下的自己YY一下就出来了　我这么弱都YY出来了您们肯定随便就搞出来了

至于这个集合怎么维护，显然线段树套个multiset就行了

代码

至于代码为什么这么长
当然是为了更好地装逼说明啦！　　
记得点赞啊，我就没收过赞。。。　　
~~下次一定的走开(bushi~~

#include <set>
#include <cstdio>
#include <utility>
#include <algorithm>

using namespace std;

#define R register
#define LL long long
#define IT multiset<int>::iterator

const int MAXN = 3e5 + 10;
const int inf = 1e9 + 10;

inline int read()
{
    char a = getchar();
    int x = 0, f = 1;
    for (; a > '9' || a < '0'; a = getchar())
        if (a == '-')
            f = -1;
    for (; a >= '0' && a <= '9'; a = getchar())
        x = x * 10 + a - '0';
    return x * f;
}

inline char getc()
{
    char a = getchar();
    while (a != 'A' && a != 'D')
        a = getchar();
    return a;
}

int n, m;
LL Ans;

struct Round
{
    int l, r, va;
};

class Tree_for_value
{
private:
    int tag[MAXN << 2];
    Round mn[MAXN << 2];
    inline int ls(int x);
    inline int rs(int x);
    inline void update(int x);
    inline void get(int x, int k);
    inline void pushdown(int x);

public:
    inline Round ask(int x, int l, int r, int Le, int Ri);
    inline void chg(int x, int l, int r, int Le, int Ri, int k);
    inline void build(int x, int l, int r);
} T1;

class Tree_for_mintask
{
private:
    multiset<int> st[MAXN << 2];
    pair<int, int> mn[MAXN << 2];
    inline int ls(int x);
    inline int rs(int x);
    inline void update(int x);

public:
    inline void build(int x, int l, int r);
    inline void insert(int x, int l, int r, int ad, int p);
    inline void del(int x, int l, int r, int ad, int p);
    inline pair<int, int> ask(int x, int l, int r, int Le, int Ri);
    inline int have(int x, int l, int r, int ad, int p);
} T2;

class Tree_for_maxtask
{
private:
    multiset<int> st[MAXN << 2];
    pair<int, int> mx[MAXN << 2];
    inline int ls(int x);
    inline int rs(int x);
    inline void update(int x);

public:
    inline void build(int x, int l, int r);
    inline void insert(int x, int l, int r, int ad, int p);
    inline void del(int x, int l, int r, int ad, int p);
    inline pair<int, int> ask(int x, int l, int r, int Le, int Ri);
} T3;

int main()
{
    freopen("d.in", "r", stdin);
    freopen("d.out", "w", stdout);
    n = read();
    m = read();
    T1.build(1, 1, n);
    T2.build(1, 1, n);
    T3.build(1, 1, n);
    char op;
    int t, p;
    while (m--)
    {
        op = getc();
        t = read();
        p = read();
        if (op == 'A')
        {
            Round pir = T1.ask(1, 1, n, t, n);
            if (pir.va > 0)
            {
                Ans += p;
                T1.chg(1, 1, n, t, n, -1);
                T2.insert(1, 1, n, t, p);
            }
            else
            {
                int id = pir.l;
                pair<int, int> tmp = T2.ask(1, 1, n, 1, id);
                if (tmp.first > p)
                    T3.insert(1, 1, n, t, p);
                else
                {
                    Ans += p - tmp.first;
                    T2.del(1, 1, n, tmp.second, tmp.first);
                    T3.insert(1, 1, n, tmp.second, tmp.first);
                    T1.chg(1, 1, n, tmp.second, n, 1);
                    T2.insert(1, 1, n, t, p);
                    T1.chg(1, 1, n, t, n, -1);
                }
            }
        }
        else
        {
            if (T2.have(1, 1, n, t, p) == 0)
                T3.del(1, 1, n, t, p);
            else
            {
                Ans -= p;
                T2.del(1, 1, n, t, p);
                T1.chg(1, 1, n, t, n, 1);
                Round tmp = T1.ask(1, 1, n, 1, n);
                int id = tmp.va <= 0 ? tmp.r : 0;
                if (id != n)
                {
                    pair<int, int> tmp = T3.ask(1, 1, n, id + 1, n);
                    if (tmp.first != -inf)
                    {
                        T3.del(1, 1, n, tmp.second, tmp.first);
                        T2.insert(1, 1, n, tmp.second, tmp.first);
                        T1.chg(1, 1, n, tmp.second, n, -1);
                        Ans += tmp.first;
                    }
                }
            }
        }
        printf("%lld\n", Ans);
    }
    return 0;
}

inline int Tree_for_value::ls(int x) { return x << 1; }
inline int Tree_for_value::rs(int x) { return x << 1 | 1; }
inline void Tree_for_value::update(int x)
{
    if (mn[ls(x)].va == mn[rs(x)].va)
    {
        mn[x].va = mn[ls(x)].va;
        mn[x].l = mn[ls(x)].l;
        mn[x].r = mn[rs(x)].r;
    }
    if (mn[ls(x)].va < mn[rs(x)].va)
        mn[x] = mn[ls(x)];
    if (mn[ls(x)].va > mn[rs(x)].va)
        mn[x] = mn[rs(x)];
}
inline void Tree_for_value::get(int x, int k)
{
    tag[x] += k;
    mn[x].va += k;
}
inline void Tree_for_value::pushdown(int x)
{
    if (tag[x])
    {
        get(ls(x), tag[x]);
        get(rs(x), tag[x]);
        tag[x] = 0;
    }
}
inline void Tree_for_value::build(int x, int l, int r)
{
    if (l == r)
    {
        mn[x] = {l, l, l};
        return;
    }
    int mid = l + r;
    mid >>= 1;
    build(ls(x), l, mid);
    build(rs(x), mid + 1, r);
    update(x);
}
inline void Tree_for_value::chg(int x, int l, int r, int Le, int Ri, int k)
{
    if (l >= Le && r <= Ri)
    {
        get(x, k);
        return;
    }
    pushdown(x);
    int mid = l + r;
    mid >>= 1;
    if (Le <= mid)
        chg(ls(x), l, mid, Le, Ri, k);
    if (Ri > mid)
        chg(rs(x), mid + 1, r, Le, Ri, k);
    update(x);
}
inline Round Tree_for_value::ask(int x, int l, int r, int Le, int Ri)
{
    if (l >= Le && r <= Ri)
        return mn[x];
    pushdown(x);
    int mid = l + r;
    mid >>= 1;
    Round ans;
    if (Le > mid)
        ans = ask(rs(x), mid + 1, r, Le, Ri);
    else if (Ri <= mid)
        return ans = ask(ls(x), l, mid, Le, Ri);
    else
    {
        Round lef = ask(ls(x), l, mid, Le, Ri), rig = ask(rs(x), mid + 1, r, Le, Ri);
        if (lef.va < rig.va)
            ans = lef;
        if (lef.va > rig.va)
            ans = rig;
        if (lef.va == rig.va)
        {
            ans.l = lef.l;
            ans.r = rig.r;
            ans.va = lef.va;
        }
    }
    update(x);
    return ans;
}

inline int Tree_for_mintask::ls(int x) { return x << 1; }
inline int Tree_for_mintask::rs(int x) { return x << 1 | 1; }
inline void Tree_for_mintask::update(int x)
{
    if (mn[ls(x)].first <= mn[rs(x)].first)
        mn[x] = mn[ls(x)];
    else
        mn[x] = mn[rs(x)];
}
inline void Tree_for_mintask::build(int x, int l, int r)
{
    if (l == r)
    {
        mn[x] = make_pair(inf, l);
        return;
    }
    int mid = l + r;
    mid >>= 1;
    build(ls(x), l, mid);
    build(rs(x), mid + 1, r);
    update(x);
}
inline void Tree_for_mintask::insert(int x, int l, int r, int ad, int p)
{
    if (l == r)
    {
        st[x].insert(p);
        mn[x].first = min(mn[x].first, p);
        return;
    }
    int mid = l + r;
    mid >>= 1;
    if (ad <= mid)
        insert(ls(x), l, mid, ad, p);
    else
        insert(rs(x), mid + 1, r, ad, p);
    update(x);
}
inline void Tree_for_mintask::del(int x, int l, int r, int ad, int p)
{
    if (l == r)
    {
        st[x].erase(st[x].find(p));
        if (st[x].size())
            mn[x].first = *st[x].begin();
        else
            mn[x].first = inf;
        return;
    }
    int mid = l + r;
    mid >>= 1;
    if (ad <= mid)
        del(ls(x), l, mid, ad, p);
    if (ad > mid)
        del(rs(x), mid + 1, r, ad, p);
    update(x);
}
inline pair<int, int> Tree_for_mintask::ask(int x, int l, int r, int Le, int Ri)
{
    if (l >= Le && r <= Ri)
        return mn[x];
    int mid = l + r;
    mid >>= 1;
    if (Le > mid)
        return ask(rs(x), mid + 1, r, Le, Ri);
    if (Ri <= mid)
        return ask(ls(x), l, mid, Le, Ri);
    pair<int, int> lef = ask(ls(x), l, mid, Le, Ri), rig = ask(rs(x), mid + 1, r, Le, Ri);
    if (lef.first <= rig.first)
        return lef;
    return rig;
}
inline int Tree_for_mintask::have(int x, int l, int r, int ad, int p)
{
    if (l == r)
        return st[x].find(p) != st[x].end();
    int mid = l + r;
    mid >>= 1;
    if (ad <= mid)
        return have(ls(x), l, mid, ad, p);
    else
        return have(rs(x), mid + 1, r, ad, p);
}

inline int Tree_for_maxtask::ls(int x) { return x << 1; }
inline int Tree_for_maxtask::rs(int x) { return x << 1 | 1; }
inline void Tree_for_maxtask::update(int x)
{
    if (mx[ls(x)].first > mx[rs(x)].first)
        mx[x] = mx[ls(x)];
    else
        mx[x] = mx[rs(x)];
}
inline void Tree_for_maxtask::build(int x, int l, int r)
{
    if (l == r)
    {
        mx[x] = make_pair(-inf, l);
        return;
    }
    int mid = l + r;
    mid >>= 1;
    build(ls(x), l, mid);
    build(rs(x), mid + 1, r);
    update(x);
}
inline void Tree_for_maxtask::insert(int x, int l, int r, int ad, int p)
{
    if (l == r)
    {
        st[x].insert(p);
        mx[x].first = max(mx[x].first, p);
        return;
    }
    int mid = l + r;
    mid >>= 1;
    if (ad <= mid)
        insert(ls(x), l, mid, ad, p);
    else
        insert(rs(x), mid + 1, r, ad, p);
    update(x);
}
inline void Tree_for_maxtask::del(int x, int l, int r, int ad, int p)
{
    if (l == r)
    {
        st[x].erase(st[x].find(p));
        if (st[x].size())
        {
            IT it = st[x].end();
            it--;
            mx[x].first = *it;
        }
        else
            mx[x].first = -inf;
        return;
    }
    int mid = l + r;
    mid >>= 1;
    if (ad <= mid)
        del(ls(x), l, mid, ad, p);
    if (ad > mid)
        del(rs(x), mid + 1, r, ad, p);
    update(x);
}
inline pair<int, int> Tree_for_maxtask::ask(int x, int l, int r, int Le, int Ri)
{
    if (l >= Le && r <= Ri)
        return mx[x];
    int mid = l + r;
    mid >>= 1;
    if (Le > mid)
        return ask(rs(x), mid + 1, r, Le, Ri);
    if (Ri <= mid)
        return ask(ls(x), l, mid, Le, Ri);
    pair<int, int> lef = ask(ls(x), l, mid, Le, Ri), rig = ask(rs(x), mid + 1, r, Le, Ri);
    if (lef.first > rig.first)
        return lef;
    return rig;
}

题解 P4511 【[CTSC2015]日程管理】

正题

插入

删除

代码