「CF702F」T-Shirts

    「CF702F」T-Shirts

    CF702F

    有 nn 个 T 恤。每个 T 恤都有一个价格 cic_i 和品质 pip_i。

    有 mm 个人要购买 T 恤,第 ii 个人有 viv_i 元。

    每个人每次购买 T 恤都会在可以买得起的 T 恤中选一件品质最高的 T 恤,若有多个品质最高的 T 恤,则选择其中最便宜的那一件 T 恤。

    请你求出这 mm 个人各买了多少件 T 恤,注意每次询问都是独立的。

    数据范围:1≤n,m≤2×1051 \leq n, m \leq 2 \times 10^5,1≤ci,pi≤1091 \leq c_i, p_i \leq 10^9。

    时空限制:44s / 10241024MiB。

    Solution

    首先,将所有的 T 恤按照品质从大到小排序,品质相同的情况按价格小到大排序。

    考虑使用平衡树维护每一个人的金钱数,本题解使用的是 fhq treap。

    依次处理每一个 T 恤,考虑该 T 恤可以贡献给哪些人。设当前处理到的 T 恤的价格为 cc。

    显然,金钱数在区间 [0,c)[0, c) 内的人不需要购买该 T 恤,金钱数在区间 [c,+∞)[c, +\infty) 内的人必须购买该 T 恤。

    那么,对应到平衡树上,我们需要将平衡树中权值 ≥c\geq c 的所有点的权值减去 cc,T 恤件数加上 11。

    使用 fhq treap 打打标记可以很轻松的做到这些事情。

    关键在于 merge 上,我们的操作是要将平衡树 split 成 [0,c),[c,2c),[2c,+∞)[0, c), [c, 2c), [2c, +\infty) 三部分。

    其中第一部分不需要被操作,第二、三部分必须被操作。

    并且注意到,第二部分被操作后,其值域从 [c,2c)[c, 2c) 被修改为了 [0,c)[0, c),与第一部分发生了重合。
    而正常的 fhq treap 是不支持任意权值合并的。

    考虑第二部分里任意一个点的 “ 操作前权值 “ 与 “ 操作后权值 “ 的比值:

    x−cx=1−cx\frac{x - c}{x} = 1 - \frac{c}{x}

    注意到该比值随着 xx 的增大而增大,当 x=2c−1x = 2c - 1 时该比值取到最大,不难得出该比值的取值范围:

    0≤x−cx<12x−c<x20 \leq \frac{x - c}{x} < \frac{1}{2} \\x - c < \frac{x}{2}

    观察上式,我们可以知道:第二部分的点被操作之后,权值至少缩小一半。
    也就是说,每个点被分到第二部分的次数至多是 log⁡2size\log_2 \text{size},其中 size\text{size} 表示值域的大小。

    那么在合并操作的时候,我们只需要遍历第二部分中的所有点,将其直接插入第一部分,最后再将第一部分和第三部分合并即可。

    依次考虑完了每个 T 恤之后,再遍历一遍整棵树,将答案存下来后输出即可,注意要标记下放。

    时间复杂度 O(nlog⁡nlog⁡size)\mathcal{O}(n \log n \log \text{size})。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int N = 200100;
    
    int m, n;
    
    struct article {
        int p, c;
    } seq[N];
    
    bool cmp(article a, article b) {
        if (a.p != b.p) return a.p > b.p;
        else return a.c < b.c;
    }
    
    int cT, root;
    struct Treap {
        int lc, rc;
        int val, dat, id;
        int money;
        int tagV, tagM;
    } t[N];
    
    int New(int val, int id) {
        cT ++;
        t[cT].lc = t[cT].rc = 0;
        t[cT].val = val, t[cT].dat = rand(), t[cT].id = id;
        t[cT].money = 0;
        t[cT].tagV = t[cT].tagM = 0;
        return cT;
    }
    
    void spread(int p) {
        int lc = t[p].lc, rc = t[p].rc;
        if (t[p].tagV) {
            if (lc) t[lc].val += t[p].tagV, t[lc].tagV += t[p].tagV;
            if (rc) t[rc].val += t[p].tagV, t[rc].tagV += t[p].tagV;
            t[p].tagV = 0;
        }
        if (t[p].tagM) {
            if (lc) t[lc].money += t[p].tagM, t[lc].tagM += t[p].tagM;
            if (rc) t[rc].money += t[p].tagM, t[rc].tagM += t[p].tagM;
            t[p].tagM = 0;
        }
    }
    
    void split_v(int p, int val, int &x, int &y) {
        if (!p)
            x = y = 0;
        else {
            spread(p);
            if (t[p].val <= val)
                x = p, split_v(t[p].rc, val, t[x].rc, y);
            else
                y = p, split_v(t[p].lc, val, x, t[y].lc); 
        }
    }
    
    int merge(int p, int q) {
        if (!p || !q) return p ^ q;
        spread(p), spread(q);
        if (t[p].dat > t[q].dat) {
            t[p].rc = merge(t[p].rc, q);
            return p;
        } else {
            t[q].lc = merge(p, t[q].lc);
            return q;
        }
    }
    
    void insert(int &rt, int p) {
        int X, Z;
        split_v(rt, t[p].val, X, Z);
        rt = merge(X, p), rt = merge(rt, Z); 
    }
    
    void search(int p, int &rt) {
        if (!p) return;
        spread(p);
        search(t[p].lc, rt), search(t[p].rc, rt);
        t[p].lc = t[p].rc = 0;
        insert(rt, p);
    }
    
    int ans[N];
    
    void solve(int p) {
        if (!p) return;
        spread(p);
        solve(t[p].lc), solve(t[p].rc);
        ans[t[p].id] = t[p].money; 
    }
    
    int main() {
        m = read();
    
        for (int i = 1; i <= m; i ++)
            seq[i].c = read(), seq[i].p = read();
    
        sort(seq + 1, seq + 1 + m, cmp);
    
        n = read();
    
        for (int i = 1; i <= n; i ++) {
            int x = read();
            int p = New(x, i);
            insert(root, p);
        }
    
        for (int i = 1; i <= m; i ++) {
            int c = seq[i].c, p = seq[i].p;
    
            int X, Y, Z;
            split_v(root, c - 1, X, Y);
            split_v(Y, 2 * c - 1, Y, Z);
    
            if (Z) {
                t[Z].val -= c, t[Z].tagV -= c;
                t[Z].money ++, t[Z].tagM ++; 
            }
    
            if (Y) {
                t[Y].val -= c, t[Y].tagV -= c;
                t[Y].money ++, t[Y].tagM ++;
                search(Y, X);
            }
    
            root = merge(X, Z);
        }
    
        solve(root);
    
        for (int i = 1; i <= n; i ++)
            printf("%d ", ans[i]);
        puts("");
    
        return 0;
    }