跳转至

260115 模拟赛

T1

有 \(n\) 个盒子，第 \(i\) 个盒子容量为 \(c_i\)，初始有 \(a_i\) 个蓝糖果和 \(b_i\) 个红糖果，保证 \(a_i+b_i\le c_i\)，\(c_i\) 是偶数。定义一次操作为向某个盒子中放入一个糖果，然后检查总数是否超过 \(c_i\)，若超过，则取出两种糖果中数量更多的一种中的一个，对下一个盒子递归进行放入操作。保证 \(c_n=+\infty\)。

你需要处理 \(q\) 次操作：

  • 向第 \(p\) 个盒子加入 \(v\) 个红色糖果；
  • 向第 \(p\) 个盒子加入 \(v\) 个蓝色糖果；
  • 查询第 \(p\) 个盒子中的红蓝糖果数量；

\(n,q\le 2\times 10^5,~a_i,b_i,c_i\le 10^9\)

发现盒子内的糖果数量平衡之后，可以直接删去该盒子。因此可以维护盒子没满/没平衡/已平衡的三种状态，状态的转化是 \(O(n)\) 级别的，可以用线段树做到在线。

然而上面这种做法非常难写。考虑离线，对序列扫描线，用线段树维护时间轴上的操作。发现形如把一段前缀删除，中间一段区间推平，一段后缀不管。于是写一个线段树上二分和区间操作 tag 就做完了。

如果线段树有清空 tag，一定要注意叶子节点处的清空 tag 可能失效导致别的 tag 打不上。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct res_type {
    ll s0, s1;
    inline res_type operator+(const res_type &oth) const {
        return (res_type){s0 + oth.s0, s1 + oth.s1};
    }
};
struct Op {
    int tp, x, v, tm;
    inline bool operator<(const Op &b) const {
        if(x != b.x) return x < b.x;
        return tp < b.tp;
    }
} q[N];

int n, m, nq;
ll a[N][2], c[N];
res_type ans[N];

namespace SegT {
    struct Node {
        ll s0, s1; int tag;
        inline Node() : s0(), s1(), tag(-2) {}
    } tr[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) {
        tr[p].s0 = tr[lc(p)].s0 + tr[rc(p)].s0;
        tr[p].s1 = tr[lc(p)].s1 + tr[rc(p)].s1;
    }
    inline void spread(int p, int tg) {
        if(tr[p].tag == -1) return; tr[p].tag = tg;
        if(tg == -1) tr[p].s0 = tr[p].s1 = 0;
        else if(tg == 0) tr[p].s0 += tr[p].s1, tr[p].s1 = 0;
        else tr[p].s1 += tr[p].s0, tr[p].s0 = 0;
    }
    inline void push_down(int p) {
        if(tr[p].tag != -2) spread(lc(p), tr[p].tag), spread(rc(p), tr[p].tag);
        tr[p].tag = -2;
    }
    void insert(int p, int l, int r, int q, int col, int cnt) {
        col ? tr[p].s1 += cnt : tr[p].s0 += cnt;
        if(l == r) return tr[p].tag = -2, void();
        int mid = (l + r) >> 1; push_down(p);
        if(q <= mid) insert(lc(p), l, mid, q, col, cnt);
        else insert(rc(p), mid + 1, r, q, col, cnt);
    }
    res_type query(int p, int l, int r, int qr) {
        if(r <= qr) return (res_type){tr[p].s0, tr[p].s1};
        int mid = (l + r) >> 1; push_down(p);
        if(mid < qr) return (res_type){tr[lc(p)].s0, tr[lc(p)].s1} + query(rc(p), mid + 1, r, qr);
        return query(lc(p), l, mid, qr);
    }
    res_type query1(int p, int l, int r, ll tar) {
        if(l == r) return (tar <= tr[p].s0) ? (res_type){tar, 0} : (res_type){tr[p].s0, tar - tr[p].s0};
        int mid = (l + r) >> 1; push_down(p);
        if(tar <= tr[lc(p)].s0 + tr[lc(p)].s1) return query1(lc(p), l, mid, tar);
        else return (res_type){tr[lc(p)].s0, tr[lc(p)].s1} + query1(rc(p), mid + 1, r, tar - tr[lc(p)].s0 - tr[lc(p)].s1);
    }
    void remove(int p, int l, int r, ll tar) {
        if(l == r) return (tar <= tr[p].s0) ? (tr[p].s0 -= tar) : (tr[p].s1 -= (tar - tr[p].s0), tr[p].s0 = 0), void();
        int mid = (l + r) >> 1; push_down(p);
        if(tar <= tr[lc(p)].s0 + tr[lc(p)].s1) remove(lc(p), l, mid, tar);
        else remove(rc(p), mid + 1, r, tar - tr[lc(p)].s0 - tr[lc(p)].s1), spread(lc(p), -1);
        push_up(p);
    }
    void modify0(int p, int l, int r, ll tar) {
        if(l == r) return tr[p].s0 -= tar, tr[p].s1 += tar, void();
        int mid = (l + r) >> 1; push_down(p);
        if(tar <= tr[lc(p)].s0) modify0(lc(p), l, mid, tar);
        else modify0(rc(p), mid + 1, r, tar - tr[lc(p)].s0), spread(lc(p), 1);
        push_up(p);
    }
    void modify1(int p, int l, int r, ll tar) {
        if(l == r) return tr[p].s1 -= tar, tr[p].s0 += tar, void();
        int mid = (l + r) >> 1; push_down(p);
        if(tar <= tr[lc(p)].s1) modify1(lc(p), l, mid, tar);
        else modify1(rc(p), mid + 1, r, tar - tr[lc(p)].s1), spread(lc(p), 0);
        push_up(p);
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 1; i < n; i++) cin >> a[i][0] >> a[i][1] >> c[i]; cin >> a[n][0] >> a[n][1];
    for(int i = 1; i <= m; i++) {
        cin >> q[i].tp;
        if(q[i].tp <= 2) cin >> q[i].x >> q[i].v;
        else cin >> q[i].x, q[i].v = ++nq;
        q[i].tm = i;
    }
    sort(q + 1, q + 1 + m);

    c[n] = INF;
    for(int i = 1, j = 1; i <= n; i++) {
        while(j <= m && q[j].x == i && q[j].tp <= 2) SegT::insert(1, 1, m, q[j].tm, q[j].tp - 1, q[j].v), j++;
        ll tmp = min(SegT::tr[1].s0 + SegT::tr[1].s1, c[i] - a[i][0] - a[i][1]);
        res_type l1 = SegT::query1(1, 1, m, tmp);
        ll delta;
        if(l1.s0 + a[i][0] >= l1.s1 + a[i][1]) {
            delta = (l1.s0 + a[i][0] - l1.s1 - a[i][1]) / 2;
            while(j <= m && q[j].x == i && q[j].tp == 3) {
                res_type res = SegT::query(1, 1, m, q[j].tm);
                res.s0 = min(res.s0, l1.s0);
                if(res.s1 <= l1.s1 || i == n) {
                    ans[q[j].v] = res + (res_type){a[i][0], a[i][1]};
                } else if(res.s1 <= l1.s1 + delta) {
                    ll tmp = res.s1 - l1.s1;
                    ans[q[j].v] = l1 + (res_type){-tmp, tmp} + (res_type){a[i][0], a[i][1]};
                } else {
                    ans[q[j].v] = (res_type){c[i] / 2, c[i] / 2};
                }
                j++;
            }
            SegT::remove(1, 1, m, tmp);
            if(a[i][0] + a[i][1] + tmp == c[i]) SegT::modify1(1, 1, m, min(SegT::tr[1].s1, delta));
        } else {
            delta = (l1.s1 + a[i][1] - l1.s0 - a[i][0]) / 2;
            while(j <= m && q[j].x == i && q[j].tp == 3) {
                res_type res = SegT::query(1, 1, m, q[j].tm);
                res.s1 = min(res.s1, l1.s1);
                if(res.s0 <= l1.s0 || i == n) {
                    ans[q[j].v] = res + (res_type){a[i][0], a[i][1]};
                } else if(res.s0 <= l1.s0 + delta) {
                    ll tmp = res.s0 - l1.s0;
                    ans[q[j].v] = l1 + (res_type){tmp, -tmp} + (res_type){a[i][0], a[i][1]};
                } else {
                    ans[q[j].v] = (res_type){c[i] / 2, c[i] / 2};
                }
                j++;
            }
            SegT::remove(1, 1, m, tmp);
            if(a[i][0] + a[i][1] + tmp == c[i]) SegT::modify0(1, 1, m, min(SegT::tr[1].s0, delta));
        }
    }

    for(int i = 1; i <= nq; i++) cout << ans[i].s0 << ' ' << ans[i].s1 << '\n';

    return 0;
}

T2

平面上有 \(k\) 个点，每个点的横纵坐标都是 \([1,n]\) 之间的正整数。每次你可以询问平面上一个点（\(0\le x,y\le n+1\)），交互库回答所有点到该点的切比雪夫距离之和。

你需要在时间限制之内确定 \(k\) 个点的坐标，初始你不知道 \(k\)。由于通过交互不一定能全部确定，因此你可以返回任意一组可行解。

\(2\le n\le 5\times 10^5,~1\le k\le 5\times 10^5\)

首先旋转 45° 转化成曼哈顿距离。接下来考虑询问 \((x,y)\) 和 \((x,y+2)\) 并作差，发现可以得到 \(y\) 下面点的数量减去 \(y-2\) 上面点的数量之差。发现可以递推得到每一行和每一列点的数量。

接下来有一个关键的观察：通过每一行和每一列点的数量可以唯一确定每次交互的答案，因此构造任意一个符合行列点数的方案都是合法的。

考虑如何根据行列点数构造方案。由于点必须构造在一个菱形之内，因此考虑贪心，将行按照覆盖列的数量从小到大取，每次取出覆盖的列中剩余点数前 \(sx[i]\) 大的列匹配，容易通过调整法证明该策略的正确性。

从限制紧的往限制宽的考虑，因为限制宽的可能不知道如何操作才能使后面限制紧的更优，对吗？

T3

给定一棵树，第 \(i\) 个点有 \(b_i\) 个权值为 \(a_i\) 的棋子。每次你可以匹配两个具有祖先关系的棋子，设 \(x\) 是 \(y\) 的祖先，那么获得 \(a_y-a_x\) 的价值。请你对每个 \(k\in[1,n]\)，计算出以 \(k\) 为根节点时的最大价值。

\(n\le 2\times 10^5\)

首先，对于单个根，可以模拟费用流（反悔贪心）用可并堆做到 \(O(n\log n)\)。也可以考虑 dp，设 \(f_{u,i}\) 表示子树内还剩 \(i\) 个节点没有匹配的最大价值。考虑转移，注意到转移形如把所有儿子的 dp 数组卷起来（闵可夫斯基和），然后再 \(f_{i}+ka_i\to f_{i+k}\)。发现具有凸性也可以用可并堆维护，应该跟上面的反贪是等价的。

具体一点，就是先向可并堆中插入 \(2b_u\) 个 \(a_u\)，然后和所有儿子合并，再删去前 \(b_u\) 大。考虑如何对这个过程进行换根，发现用可持久化线段树合并加上各种神秘的线段树上二分其实是可以做的。具体的，在第一次 dfs 的时候把删去 \(b_u\) 个 \(a_u\) 之前的线段树记为 \(q[u]\)，删去之后的记为 \(p[u]\)，删掉的部分记为 \(d[u]\)。考虑 \(u\to v\) 的换根，在 \(q[u]-p[v]\) 上线段树上二分前 \(b_u\) 大，然后删去这个后缀并接上 \(p[v]\)，然后再插入 \(d[u]\) 就能得到 \(q[v]\)。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<iostream>
typedef __int128 lll;
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
const int V = 1e9;

template<typename _Tp>
inline void read(_Tp &x) {
    char ch; x = 0;
    while(!isdigit(ch = getchar()));
    x = ch - '0';
    while(isdigit(ch = getchar())) x = x * 10 + ch - '0';
}

template<typename _Tp>
inline void write(_Tp x) {
    char buf[64], top = 0;
    do buf[++top] = x % 10 + '0', x /= 10; while(x);
    while(top) putchar(buf[top--]);
    putchar('\n');
}

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];
inline void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, T;
int a[N], b[N];

namespace SegT {
    const int LOGN = 33;
    struct Node {
        lll val; ll cnt; int lc, rc;
        inline Node() : val(), cnt(), lc(), rc() {}
    } tr[8 * N * LOGN]; int nn;
    inline int &lc(int x) { return tr[x].lc; }
    inline int &rc(int x) { return tr[x].rc; }
    inline int addNode() { return ++nn; }
    inline void push_up(int p) {
        tr[p].val = tr[lc(p)].val + tr[rc(p)].val;
        tr[p].cnt = tr[lc(p)].cnt + tr[rc(p)].cnt;
    }
    int insert(int p, int l, int r, int val, int cnt) {
        int cur = addNode(); tr[cur] = tr[p];
        tr[cur].val += (ll)val * cnt; tr[cur].cnt += cnt;
        if(l == r) return cur;
        int mid = (l + r) >> 1;
        if(val <= mid) lc(cur) = insert(lc(p), l, mid, val, cnt);
        else rc(cur) = insert(rc(p), mid + 1, r, val, cnt);
        return cur;
    }
    int merge(int p1, int p2, int l, int r) {
        if(!p1 || !p2) return p1 | p2;
        int cur = addNode();
        if(l == r) return tr[cur].val = tr[p1].val + tr[p2].val, tr[cur].cnt = tr[p1].cnt + tr[p2].cnt, cur;
        int mid = (l + r) >> 1;
        lc(cur) = merge(lc(p1), lc(p2), l, mid);
        rc(cur) = merge(rc(p1), rc(p2), mid + 1, r);
        push_up(cur);
        return cur;
    }
    void split(int p, int l, int r, ll k, int &x, int &y) {
        x = addNode(), y = addNode();
        if(l == r) {
            tr[y].cnt = k, tr[y].val = (lll)k * l;
            tr[x].cnt = tr[p].cnt - k, tr[x].val = (lll)tr[x].cnt * l;
            return;
        }
        int mid = (l + r) >> 1;
        if(k <= tr[rc(p)].cnt) {
            lc(x) = lc(p);
            split(rc(p), mid + 1, r, k, rc(x), rc(y));
        } else {
            rc(y) = rc(p);
            split(lc(p), l, mid, k - tr[rc(p)].cnt, lc(x), lc(y));
        }
        push_up(x), push_up(y);
    }
    void split2(int p1, int p2, int l, int r, ll k, int &x) {
        x = addNode();
        if(l == r) {
            tr[x].cnt = tr[p1].cnt - k, tr[x].val = (lll)tr[x].cnt * l;
            return;
        }
        int mid = (l + r) >> 1;
        if(k <= tr[rc(p1)].cnt - tr[rc(p2)].cnt) {
            lc(x) = lc(p1);
            split2(rc(p1), rc(p2), mid + 1, r, k, rc(x));
        } else {
            rc(x) = rc(p2);
            split2(lc(p1), lc(p2), l, mid, k - (tr[rc(p1)].cnt - tr[rc(p2)].cnt), lc(x));
        }
        push_up(x);
    }
    lll query(int p, int l, int r, ll k) {
        if(l == r) return l * k;
        int mid = (l + r) >> 1;
        if(k <= tr[rc(p)].cnt) return query(rc(p), mid + 1, r, k);
        else return tr[rc(p)].val + query(lc(p), l, mid, k - tr[rc(p)].cnt);
    }
}

int p[N], q[N], d[N];
lll f[N], g[N], ans[N];

void dfs1(int u, int fa) {
    q[u] = SegT::insert(0, 1, V, a[u], 2 * b[u]);
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs1(v, u);
        g[u] += f[v];
        q[u] = SegT::merge(q[u], p[v], 1, V);
    }
    SegT::split(q[u], 1, V, b[u], p[u], d[u]);
    g[u] -= (ll)a[u] * b[u];
    f[u] = g[u] + SegT::tr[d[u]].val;
}

void dfs2(int u, int fa) {
    ans[u] = g[u] + SegT::query(q[u], 1, V, b[u]);
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        int res = 0;
        SegT::split2(q[u], p[v], 1, V, b[u], res);
        g[v] += g[u] - f[v] + (SegT::tr[q[u]].val - SegT::tr[res].val);
        q[v] = SegT::merge(res, d[v], 1, V);
        dfs2(v, u);
    }
}

int main() {

    read(n), read(T);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= n; i++) read(b[i]);
    for(int i = 1; i <= n - 1; i++) {
        int u, v; read(u), read(v);
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs1(1, 0);
    dfs2(1, 0);

    if(T == 1) write(ans[1]);
    else for(int i = 1; i <= n; i++) write(ans[i]);

    return 0;
}