Description

Luogu传送门

Solution

先对物品按照品质从大到小排序，相同品质的按价格从小到大排序。

依次枚举每一个物品，考虑对于一个物品，其价格为 \(c\)，品质为 \(q\)：

• 拥有钱数小于 \(c\) 的人买不起，不用管。
• 拥有钱数大于等于 \(c\) 的人买得起，也必须买（物品是按品质从大到小排序的），所以这些人钱数减去 \(c\)，答案（购买的衣服数）加 1。

上述这两种情况用 \(fhq-treap\) 维护一下即可快速解决。

但是我们不能直接合并，因为钱数减去 \(c\) 之后和钱数原本就小于 \(c\) 的树的大小关系就不确定了，所以不能直接合并。

那该如何合并呢？

其实没有特别复杂，直接暴力重构这棵树即可。

具体地说，枚举钱数原本在 \(c \sim 2 \times c - 1\) 的树中的每一个点，在原本钱数为 \(0 \sim c - 1\) 的树中查找一下，然后暴力插进去即可。

原本钱数 \(\geq 2 \times c\) 的点减去 \(c\) 之后照样满足大小关系，可以直接合并。

Code

（有注释）

#include <bits/stdc++.h>
#define ls(x) t[x].l
#define rs(x) t[x].r

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;

struct fhq_treap{
    int siz, val, sum, wei, l, r;
    int lazy, sub;// lazy: 答案增加数   sub: 钱减少数
}t[N];
int root, tot, a, b, c;

inline void pushup(int x){
    t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1;
}

inline void pushdown(int x){
    if(t[x].lazy){
        if(ls(x)) t[ls(x)].lazy += t[x].lazy, t[ls(x)].sum += t[x].lazy;
        if(rs(x)) t[rs(x)].lazy += t[x].lazy, t[rs(x)].sum += t[x].lazy;
        t[x].lazy = 0;
    }
    if(t[x].sub){
        if(ls(x)) t[ls(x)].sub += t[x].sub, t[ls(x)].val -= t[x].sub;
        if(rs(x)) t[rs(x)].sub += t[x].sub, t[rs(x)].val -= t[x].sub;
        t[x].sub = 0;
    }
}

inline void split_val(int x, int k, int &a, int &b){
    if(!x) return a = b = 0, void();
    pushdown(x);
    if(k >= t[x].val) a = x, split_val(rs(x), k, rs(x), b);
    else b = x, split_val(ls(x), k, a, ls(x));
    pushup(x);
}

inline void split_siz(int x, int k, int &a, int &b){
    if(!x) return a = b = 0, void();
    pushdown(x);
    if(k >= t[ls(x)].siz + 1) a = x, split_siz(rs(x), k - t[ls(x)].siz - 1, rs(x), b);
    else b = x, split_siz(ls(x), k, a, ls(x));
    pushup(x);
}

inline int merge(int x, int y){
    if(!x || !y) return x | y;
    pushdown(x), pushup(x);
    pushdown(y), pushup(y);
    if(t[x].wei < t[y].wei){
        rs(x) = merge(rs(x), y);
        return pushup(x), x;
    }else{
        ls(y) = merge(x, ls(y));
        return pushup(y), y;
    }
}

inline int newnode(int k){
    t[++tot].val = k, t[tot].wei = rand(), t[tot].siz = 1;
    t[tot].l = t[tot].r = t[tot].sum = t[tot].lazy = t[tot].sub = 0;
    return tot;
}

inline void insert(int k){
    int a, b;
    split_val(root, k, a, b);
    root = merge(merge(a, newnode(k)), b);
}
//-------------------------------------------上面都是 fhq-treap 基本操作不解释。

//最后统计答案前全都 pushdown 一下。
inline void update(int x){
    if(!x) return;
    pushdown(x);
    update(ls(x)), update(rs(x));
}

int n, m;
struct node{
    int c, q;
    bool operator < (const node &b) const{
        return q != b.q ? q > b.q : c < b.c;
    }
}p[N];
int v[N];
queue <int> q;

//暴力重构树
inline void build(int &r1, int r2, int i){// r1 为原本在 0 ~ c-1 的树地根， r2 为 c ~ 2c-1 的根
    int a, b;
    while(!q.empty()) q.pop();
    q.push(r2);
    while(!q.empty()){//暴力枚举 r2
        int x = q.front(); q.pop();
        pushdown(x);
        if(ls(x)) q.push(ls(x));
        if(rs(x)) q.push(rs(x));
        split_val(r1, t[x].val - p[i].c, a, b);//在 r1 中查找
        ls(x) = rs(x) = t[x].lazy = t[x].sub = 0;//赋上初值
        t[x].val -= p[i].c;
        t[x].siz = 1, t[x].sum++;
        r1 = merge(merge(a, x), b);//合并进去
    }
}

inline void solve(int i){
    int a, b, c;
    split_val(root, p[i].c - 1, a, b);//把 0 ~ c-1 分裂出来
    split_val(b, (p[i].c << 1) - 1, b, c);//把 c ~ 2c-1 分裂出来，>= 2c 的减去 c 之后照样满足大小关系直接合并即可。
    t[c].sub += p[i].c, t[c].val -= p[i].c;
    t[c].sum++, t[c].lazy++;
    build(a, b, i);//重建树
    root = merge(a, c);//把 >= 2c 的树合并上去
}

int main(){
    n = read();
    for(int i = 1; i <= n; ++i) p[i].c = read(), p[i].q = read();
    sort(p + 1, p + 1 + n);
    m = read();
    for(int i = 1; i <= m; ++i) insert(read());
    for(int i = 1; i <= n; ++i) solve(i);
    update(root);//统计答案前 pushdown
    for(int i = 1; i <= m; ++i) write(t[i].sum), putchar(' ');
    return puts(""), 0;
}

\[\_EOF\_ \]