hiho 1034 毀滅者問題(treap)

因為有m[i]的限制，不能用 線段樹搞。考慮每個魔法機關，因為d = m[i] / r[i]是固定的，當一段時間間隔 t 大于d時，答案加上m[i]，否則就是t * r[i]，是以變成考慮怎麼維護每個魔法機關的所有時間間隔t。

離線所有操作，儲存在a 和 b數組裡面，a 按照 l 排序，b 按照 r 排序，L指針是a數組的，R指針是b數組的。從左到右枚舉每個魔法機關，用treap維護時間間隔。插入删除的時候注意。另外還要注意r[i] == 0的情況(RE了好多發 -_-|| )

看這裡

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

#pragma comment(linxer, "/STACK:102400000,102400000")
#define LL long long 
#define pii pair<int, int>
#define MP make_pair
#define ls i << 1
#define rs ls | 1
#define md (ll + rr >> 1)
#define lson ll, md, ls
#define rson md + 1, rr, rs
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 2000010
#define M 200020

int getint(){
    char c = getchar(); int ret = ;
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') ret = ret* + c - '0', c = getchar();
    return ret;
}
struct node{
    int t, l, r, id;
    void input(){
        t = getint(); l = getint(); r = getint();
    }
};
bool cmp1(const node &a, const node &b){
    return a.l < b.l || (a.l == b.l && a.r < b.r);
}
bool cmp2(const node &a, const node &b){
    return a.r < b.r || (a.r == b.r && a.l < b.l);
}

node a[M], b[M];
int ch[N][], rand_val[N], sz[N], key[N], tot;
LL sum[N];
int s[M], mi[M], r[M];
set<pii > S;
set<pii >::iterator it, itt;
queue<int> q;

int creat(int val){
    tot = q.front(); q.pop();
    ch[tot][] = ch[tot][] = ;
    rand_val[tot] = rand();
    key[tot] = val;
    sum[tot] = val;
    sz[tot] = ;
    return tot;
}
int cmp(int x, int val){
    if(key[x] == val) return -;
    return val < key[x] ?  : ;
}
void push_up(int x){
    sz[x] = sz[ch[x][]] + sz[ch[x][]] + ;
    sum[x] = sum[ch[x][]] + sum[ch[x][]] + key[x];
}
void rot(int &x, int d){
    int k = ch[x][!d];
    ch[x][!d] = ch[k][d];
    ch[k][d] = x;
    push_up(x);
    push_up(k);
    x = k;
}
void insert(int &x, int val){
    if(x == ){
        x = creat(val);
        return ;
    }
    int d = cmp(x, val);
    if(d == -)
        d = ;
    insert(ch[x][d], val);
    if(rand_val[ch[x][d]] > rand_val[x]) rot(x, d ^ );
    push_up(x);
}
void del(int &x, int val) {
    if(x == ) return;
    int d = cmp(x, val);
    if(d == -) {
        if(!ch[x][]) q.push(x), x = ch[x][];
        else if(!ch[x][]) q.push(x), x = ch[x][];
        else {
            int d2 = rand_val[ch[x][]] > rand_val[ch[x][]]? : ;
            rot(x, d2);
            del(ch[x][d2], val);
        }
    }
    else del(ch[x][d], val);
    if(x) push_up(x);
}
LL query1(int x, int val){        //查詢小于等于val的sum值
    if(!x) return ;
    int d = cmp(x, val);
    if(d == )
        return query1(ch[x][], val);
    else
        return sum[ch[x][]] + key[x] + query1(ch[x][], val);
}
int query2(int x, int val){       //查詢大于val的sz值
    if(!x) return ;
    int d = cmp(x, val);
    if(d == )
        return sz[ch[x][]] +  + query2(ch[x][], val);
    else
        return query2(ch[x][], val);
}
void output(int x){
    if(!x) return ;
    output(ch[x][]);
    printf("%d ", key[x]);
    output(ch[x][]);
}
int main(){
    for(int i = ; i < N; ++i)
        q.push(i);
    int n;
    n = getint();
    for(int i = ; i <= n; ++i){
        s[i] = getint(), mi[i] = getint(), r[i] = getint();
    }
    int m, pre = ;
    m = getint();
    for(int i = ; i <= m; ++i){
        a[i].input();
        a[i].id = i;
        pre = a[i].t;
        b[i] = a[i];
    }
    sort(a + , a +  + m, cmp1);
    sort(b + , b +  + m, cmp2);
    int L = , R = , rt = ;
    LL ans = ;
    S.insert(MP(, ));
    for(int i = ; i <= n; ++i){
    //  if(i == n){
    //      output(rt); puts("");
    //  }
        while(L <= m && a[L].l <= i){
            it = S.lower_bound(MP(a[L].t, a[L].id));
            itt = it;
            --it;
            if(itt != S.end()){
                int tmp = (*itt).first - (*it).first;
                del(rt, tmp);
                insert(rt, (*itt).first - a[L].t);
            }
            insert(rt, a[L].t - (*it).first);
            S.insert(MP(a[L].t, a[L].id));
            L++;
        }
        while(R <= m && b[R].r < i){
            itt = S.lower_bound(MP(b[R].t, b[R].id));
            it = itt;
            ++itt;
            --it;
            if(itt == S.end()){
                del(rt, b[R].t - (*it).first);
                S.erase(MP(b[R].t, b[R].id));
                R++; 
                continue;
            }
            else{
                del(rt, (*itt).first - b[R].t);
                del(rt, b[R].t - (*it).first);
                insert(rt, (*itt).first - (*it).first);
            }
            S.erase(MP(b[R].t, b[R].id));
            R++;
        }
        int tmp = -;
        if(S.size() > ){
            it = S.begin();
            ++it;
            tmp = (*it).first;
            ans += min((LL)mi[i], L * tmp * r[i] + s[i]);
            del(rt, tmp);
            if(r[i] > )
                ans += L * query1(rt, mi[i] / r[i]) * r[i] + L * query2(rt, mi[i] / r[i]) * mi[i];
            insert(rt, tmp);
        }
    }
    printf("%lld\n", ans);
    return ;
}