[hihoCoder#1034] 毁灭者问题

题目链接

Solution

很好的一道题！坑也很多（呜呜呜～

如果没有 $m_i$ 的限制，就是一道线段树入门题了，但是有了 $m_i$ 我们就会发现线段树很难办到诶……必须要转换思路！

方便起见，先考虑初值都是 $0$ 的情况。

我们依次考虑每一个魔法单位被吸收的时刻序列，那么两个时刻之间的差即是这个魔法单位恢复法力的时间，这个时间 $\Delta t$ 分成两类：

• 大于 $\left\lfloor\frac{m_i}{r_i}\right\rfloor$：魔法单位可恢复至最大值 $m_i$.
• 小于等于 $\left\lfloor\frac{m_i}{r_i}\right\rfloor$：魔法单位可恢复 $\Delta t\cdot r_i$.

所以，假设现在我们已经把所有时间差存在了一个数据结构里，我们希望 $O(\lg n)$ 地查询大于 $\left\lfloor\frac{m_i}{r_i}\right\rfloor$ 的时间差有多少个，以及小于等于 $\left\lfloor\frac{m_i}{r_i}\right\rfloor$ 的时间差的总和，那么答案加上前者乘以 $m_i$ 再加上后者乘以 $r_i$ 即可。

为了维护时间差，我们再引入一个存储时刻的数据结构，那么从第 $i$ 个单位到第 $i+1$ 个单位，减去以第 $i$ 个单位为右端的时间，加上以第 $i+1$ 个单位为左端的时间即可。同时，减掉一个时间 $t$ 时，设其后继为 $suc$，前驱为 $pre$，就需要在维护时间差的那个数据结构里面减掉 $suc-t$ 和 $t-pre$，加上 $suc-pre$；加上一个时间 $t$ 时，在维护时间差的数据结构里加上 $suc-t$ 和 $t-pre$，减掉 $suc-pre$.

综上，我们希望两个数据结构支持：添加、删除、求小于等于某数的所有元素的和、求小于等于某数的元素个数。值域线段树可以，但是离散化不是很方便，所以我用了两个平衡树（Splay）维护。

然后考虑初值 $s_i$ 的处理：其实只需要重新计算一下第一次的吸收值，修正一下答案即可。

坑点：

1. 时间 $t$ 可能相同，如果删除一个 $t$ 后还有相同的 $t$ 存在，或者加入一个 $t$ 之前已经有相同的 $t$ 了，那么在此时不需要更新存储时间差的平衡树；
2. $r_i$ 可能为 $0$，小心发生除 $0$ 错误。

Data

给一些我调试过程中造的数据吧：

input	output
4 0 1 8 0 1 8 0 1 6 0 5 2 6 1 1 3 2 1 1 3 2 2 4 1 1 5 2 3 5 1 4	14
5 6 10 1 0 12 1 6 20 1 0 12 1 0 10 1 2 5 1 5 19 1 5	94

再贴上随机数据生成器：

>folded

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<ctime>
#include<cstdlib>

using namespace std;

int Rand(int l, int r){
    return rand() % (r - l + 1) + l;
}

struct Node{
    int s, m, r;
}node[100005];
struct Opt{
    int t, l, r;
    bool operator < (const Opt &A) const{
        return t < A.t;
    }
}opt[100005];

int main(){
    srand(time(NULL));
    freopen("input.txt", "w", stdout);
    int n = Rand(100000, 100000), m = Rand(100000, 100000);
    printf("%d\n", n);
    for(int i = 1; i <= n; i++){
        node[i].m = Rand(0, 100000);
        node[i].s = Rand(0, m);
        node[i].r = Rand(0, 100000);
        printf("%d %d %d\n", node[i].s, node[i].m, node[i].r);
    }
    printf("%d\n", m);
    for(int i = 1; i <= m; i++){
        opt[i].t = Rand(0, 1000000000);
        opt[i].l = Rand(1, n);
        opt[i].r = Rand(1, n);
        if(opt[i].l > opt[i].r) swap(opt[i].l, opt[i].r);
    }
    sort(opt+1, opt+m+1);
    for(int i = 1; i <= m; i++){
        printf("%d %d %d\n", opt[i].t, opt[i].l, opt[i].r);
    }
    return 0;
}

Code

#include<algorithm>
#include<cstdio>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 100005;
const LL INF = 1e16;

int n, m;
LL ans;

struct Node{
    LL s, m, r;
}a[N];

struct Operation{
    LL t;
    int l, r;
}opt[N];
vector< pair<LL, int> > vec[N];

struct SplayOperations{
    struct Splay{
            int fa, son[2], size, cnt;
            LL val, sum;
    }tr[N<<3];
#define which(x, fa) (tr[fa].son[1] == x)
    int id = 0, root = 0;
    inline void pushup(int x){
        if(x){
            tr[x].size = tr[x].cnt;
            tr[x].sum = tr[x].val * tr[x].cnt;
            if(tr[x].son[0])    tr[x].size += tr[tr[x].son[0]].size, tr[x].sum += tr[tr[x].son[0]].sum;
            if(tr[x].son[1])    tr[x].size += tr[tr[x].son[1]].size, tr[x].sum += tr[tr[x].son[1]].sum;
        }
    }
    inline void rotate(int x, int dir){
        int y = tr[x].fa, z = tr[y].fa, B = tr[x].son[dir];
        tr[z].son[which(y, z)] = x; tr[x].fa = z;
        tr[x].son[dir] = y; tr[y].fa = x;
        tr[y].son[dir^1] = B; tr[B].fa = y;
        pushup(y), pushup(x);
    }
    inline void splay(int x, int goal){
        if(x == goal)	return;
        while(tr[x].fa != goal){
            int y = tr[x].fa, z = tr[y].fa, dir1 = which(x, y)^1, dir2 = which(y, z)^1;
            if(z == goal)	rotate(x, dir1);
            else{
                if(dir1 == dir2)	rotate(y, dir2);
                else	rotate(x, dir1);
                rotate(x, dir2);
            }
        }
        if(goal == 0)	root = x;
    }
    inline int select(LL val){
        int now = root;
        while(now){
            if(tr[now].val == val)	return now;
            else if(tr[now].val > val)	now = tr[now].son[0];
            else if(tr[now].val < val)	now = tr[now].son[1];
        }
        if(!now)	return -1;
        return now;
    }
    inline LL getPre(LL val){
        int now = root;
        LL res = -INF;
        while(now){
            if(tr[now].val < val){
                res = max(res, tr[now].val);
                now = tr[now].son[1];
            }
            else	now = tr[now].son[0];
        }
        return res;
    }
    inline LL getSuc(LL val){
        int now = root;
        LL res = INF;
        while(now){
            if(tr[now].val > val){
                res = min(res, tr[now].val);
                now = tr[now].son[0];
            }
            else	now = tr[now].son[1];
        }
        return res;
    }
    inline int newNode(LL val, int fa){
        id++;
        tr[id].val = tr[id].sum = val;
        tr[id].fa = fa;
        tr[id].son[0] = tr[id].son[1] = 0;
        tr[id].size = tr[id].cnt = 1;
        return id;
    }
    inline void insert(LL val){
        splay(select(getPre(val)), 0);
        splay(select(getSuc(val)), root);
        int &x = tr[tr[root].son[1]].son[0];
        if(x) tr[x].cnt++, tr[x].size++, tr[x].sum += val;
        else	x = newNode(val, tr[root].son[1]);
        pushup(tr[root].son[1]);
        pushup(root);
    }
    inline void del(LL val){
        splay(select(getPre(val)), 0);
        splay(select(getSuc(val)), root);
        int &x = tr[tr[root].son[1]].son[0];
        if(!x || !tr[x].cnt)	return ;
        tr[x].cnt--, tr[x].size--, tr[x].sum -= val;
        if(tr[x].cnt == 0)  x = 0;
        pushup(tr[root].son[1]);
        pushup(root);
    }
}t1, t2;

int main(){
//    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lld%lld%lld", &a[i].s, &a[i].m, &a[i].r);
    scanf("%d", &m);
    for(int i = 1; i <= m; i++){
        scanf("%lld%d%d", &opt[i].t, &opt[i].l, &opt[i].r);
        vec[opt[i].l].push_back(make_pair(opt[i].t, 1));
        vec[opt[i].r+1].push_back(make_pair(opt[i].t, -1));
    }
    t1.root = t1.newNode(-INF, 0);
    t1.tr[t1.root].son[1] = t1.newNode(INF, t1.root);
    t1.pushup(t1.root);
    t2.root = t2.newNode(-INF, 0);
    t2.tr[t2.root].son[1] = t2.newNode(INF, t2.root);
    t2.pushup(t2.root);
    for(int i = 1; i <= n; i++){
        for(int k = 0; k < vec[i].size(); k++){
            if(vec[i][k].second == 1){
                t1.insert(vec[i][k].first);
                if(t1.tr[t1.select(vec[i][k].first)].cnt > 1)   continue;
                LL pre = t1.getPre(vec[i][k].first), suc = t1.getSuc(vec[i][k].first);
                if(suc != INF){
                    if(pre != -INF) t2.del(suc - pre);
                    else    t2.del(suc);
                }
                if(pre != -INF) t2.insert(vec[i][k].first - pre);
                else    t2.insert(vec[i][k].first);
                if(suc != INF)  t2.insert(suc - vec[i][k].first);
            }
            else{
                LL pre = t1.getPre(vec[i][k].first), suc = t1.getSuc(vec[i][k].first);
                t1.del(vec[i][k].first);
                if(t1.select(vec[i][k].first) != -1)  continue;
                if(suc != INF){
                    if(pre != -INF) t2.insert(suc - pre);
                    else    t2.insert(suc);
                }
                if(pre != -INF) t2.del(vec[i][k].first - pre);
                else    t2.del(vec[i][k].first);
                if(suc != INF)  t2.del(suc - vec[i][k].first);
            }
        }
        LL firstTime = t1.getSuc(-INF);
        LL d = a[i].r == 0 ? INF-1 : a[i].m / a[i].r;
        t2.splay(t2.select(-INF), 0);
        t2.splay(t2.select(t2.getSuc(d)), t2.root);
        ans += t2.tr[t2.tr[t2.tr[t2.root].son[1]].son[0]].sum * a[i].r;
        ans += (t2.tr[t2.root].size - t2.tr[t2.tr[t2.tr[t2.root].son[1]].son[0]].size - 2) * a[i].m;
        if(firstTime <= d)
			ans += min(firstTime * a[i].r + a[i].s, a[i].m) - firstTime * a[i].r;
    }
    printf("%lld\n", ans);
    return 0;
}