250708 模拟赛

P9910 [COCI 2023/2024 #2] Dizalo

\(n\) 个人坐电梯，第 \(i\) 个人在第 \(a_i\) 层下电梯，\(a_{1\sim n}\) 构成一个排列。

电梯是长条形的，所以 \(n\) 个人初始时按编号顺序在电梯里列成一列，电梯会从下往上依次经过第 \(1\sim n\) 层。

当一个人要下电梯时，所有在他前面的人也必须暂时下电梯，然后可以以任意顺序返回电梯。在他后面的人不需要也不会下电梯。

如果每次临时下电梯的人总是以最优策略来决定返回电梯的顺序，请你求出所有人下电梯的总次数最少是多少。

给定 \(q\) 次操作，每次给定 \(x_i\) 表示移除编号为 \(x_i\) 的人，你需要在第一次操作前以及每次操作之后求出答案。

\(0\le q<n\le 10^5\)

考虑电梯序列 \(a_i\) 的后缀最小值序列，不难发现只有它们会对答案产生贡献，因此称它们为关键点。每个后缀最小值位置 \(i\) 产生的贡献为 \(cnt(j<i\wedge a[j]>a[i])\)。因此我们用 set 维护后缀最小值序列，然后考虑每次插入后的边际收益，可以用 cdq 或树套树解决。时间复杂度 \(O(n\log^2 n)\)，足以通过。

实际上我们有 \(O(n\log n)\) 的做法。注意到由于关键点的右侧不存在更小的 \(a[j]\)，因此 \(cnt(j<i\wedge a[j]>a[i])=cnt(a[j]>a[i])-cnt(j>i)\)。用四个 BIT 即可简单做到 \(O(n\log n)\)。

注意，在两种方法中，一个关键点 \(i\) 的加入只会统计到时间在它前面的数字贡献；因此每当我们加入一个非关键点，再查询一下其右下方有多少个关键点，也作为当前时刻的边际贡献。因此法一中 cdq 需要跑两遍，法二中维护两个信息需要四个 BIT。

二维偏序的特殊情况

对于简单二位数点，如果能保证每个查询操作 \((x,y)\) 的一个 \(1/4\) 平面内固定没有点，那么二维偏序可以转化为一维偏序。

cdq 代码

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 10;

struct Op {
    int tp, x, y, w, tm;
    inline bool operator<(const Op &b) const {
        if(tm != b.tm) return tm < b.tm;
        return tp > b.tp;
    }
};

inline bool cmp1(const Op &a, const Op &b) {
    if(a.tm != b.tm) return a.tm < b.tm;
    return a.tp > b.tp;
}

inline bool cmp2(const Op &a, const Op &b) {
    if(a.tm != b.tm) return a.tm < b.tm;
    return a.tp < b.tp;
}

int n, t;
int a[N], q[N];

ll cnt, ans[N], ca[N];

namespace BIT {
    int sum[N];
    inline int lowbit(int x) { return x & -x; }
    inline void clear(int p) {
        for(int i = p; i <= n; i += lowbit(i)) sum[i] = 0;
    }
    inline void add(int p, int v) {
        for(int i = p; i <= n; i += lowbit(i)) sum[i] += v;
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) res += sum[i];
        return res;
    }
    inline int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}

void cdq1(int l, int r, vector<Op> &op) {
    if(l == r) {
        for(Op &o : op) {
            if(o.tp == 1) BIT::add(o.y, o.w);
            else ans[o.tm] += BIT::query(o.y, n) * o.w;
        }
        for(Op &o : op) {
            if(o.tp == 1) BIT::clear(o.y);
        }
        return;
    }
    int mid = (l + r) >> 1;
    for(Op &o : op) {
        if(o.x <= mid && o.tp == 1) {
            BIT::add(o.y, o.w);
        }
        else if(o.x > mid && o.tp == 0) {
            ans[o.tm] += BIT::query(o.y, n) * o.w;
        }
    }
    for(Op &o : op) {
        if(o.x <= mid && o.tp == 1) BIT::clear(o.y);
    }
    vector<Op> lop, rop;
    for(Op &o : op) {
        if(o.x <= mid) lop.push_back(o);
        else rop.push_back(o);
    }
    cdq1(l, mid, lop);
    cdq1(mid + 1, r, rop);
}

void cdq2(int l, int r, vector<Op> &op) {
    if(l == r) {
        for(Op &o : op) {
            if(o.tp == 1) BIT::add(o.y, o.w);
            else ans[o.tm] += BIT::query(1, o.y) * o.w;
        }
        for(Op &o : op) {
            if(o.tp == 1) BIT::clear(o.y);
        }
        return;
    }
    int mid = (l + r) >> 1;
    for(Op &o : op) {
        if(o.x > mid && o.tp == 1) {
            BIT::add(o.y, o.w);
        }
        else if(o.x <= mid && o.tp == 0) {
            ans[o.tm] += BIT::query(1, o.y) * o.w;
        }
    }
    for(Op &o : op) {
        if(o.x > mid && o.tp == 1) BIT::clear(o.y);
    }
    vector<Op> lop, rop;
    for(Op &o : op) {
        if(o.x <= mid) lop.push_back(o);
        else rop.push_back(o);
    }
    cdq2(l, mid, lop);
    cdq2(mid + 1, r, rop);
}

vector<Op> op;

void add_Qr(int x, int y, int tm, int w) {
    op.push_back({0, x, y, w, tm});
}

void add_Pt(int x, int y, int tm, int w) {
    op.push_back({1, x, y, w, tm});
}

set<int> st;
void insert(int p, int v, int tm) {
    ++cnt;
    if(st.empty()) {
        add_Qr(p, v, tm, 1); // 查询左上方有多少个，边际收益
        st.insert(p);
        return;
    }
    auto it = st.upper_bound(p);
    if(it == st.end() || a[*it] > v) {
        add_Qr(p, v, tm, 1);
        st.insert(p);
    } else {
        add_Pt(p, v, tm, 1);
        return;
    }
    while((it = st.lower_bound(p)) != st.begin()) {
        --it;
        if(a[*it] > v) {
            add_Qr(*it, a[*it], tm, -1);
            add_Pt(*it, a[*it], tm, 1);
            st.erase(it);
        } else break;
    }
}

void calc() {

    sort(op.begin(), op.end(), cmp1);
    cdq1(1, n, op);

    for(Op &o : op) o.tp ^= 1;

    sort(op.begin(), op.end(), cmp2);
    cdq2(1, n, op);

    for(int i = 1; i <= t + 1; i++) ans[i] += ans[i - 1];

}

int main() {

    cin >> n >> t;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= t; i++) cin >> q[i];

    {
        static int vis[N];
        for(int i = 1; i <= t; i++) vis[q[i]] = 1;
        for(int i = 1; i <= n; i++) if(!vis[i]) insert(i, a[i], 1);
    }

    ca[1] = cnt;

    for(int i = t; i >= 1; i--) {
        insert(q[i], a[q[i]], t - i + 2);
        ca[t - i + 2] = cnt;
    }

    calc();

    for(int i = t + 1; i >= 1; i--) cout << ans[i] + ca[i] << ' ';
    cout << '\n';

    return 0;
}

BIT 代码

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 10;

struct Op {
    int tp, x, y, w, tm;
    inline bool operator<(const Op &b) const {
        if(tm != b.tm) return tm < b.tm;
        return tp > b.tp;
    }
};

int n, t;
int a[N], q[N];

int k;
ll ans[N], c_ans1, c_ans2;

namespace BIT1 {
    int sum[N];
    inline int lowbit(int x) { return x & -x; }
    inline void insert(int p) {
        for(int i = p; i <= n; i += lowbit(i)) ++sum[i];
    }
    inline void erase(int p) {
        for(int i = p; i <= n; i += lowbit(i)) --sum[i];
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) res += sum[i];
        return res;
    }
}

namespace BIT2 {
    int sum[N];
    inline int lowbit(int x) { return x & -x; }
    inline void insert(int p) {
        for(int i = n - p + 1; i <= n; i += lowbit(i)) ++sum[i];
    }
    inline int query(int p) {
        int res = 0;
        for(int i = n - p + 1; i > 0; i -= lowbit(i)) res += sum[i];
        return res;
    }
}

namespace BIT3 {
    int sum[N];
    inline int lowbit(int x) { return x & -x; }
    inline void insert(int p) {
        for(int i = p; i <= n; i += lowbit(i)) ++sum[i];
    }
    inline void erase(int p) {
        for(int i = p; i <= n; i += lowbit(i)) --sum[i];
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) res += sum[i];
        return res;
    }
}

namespace BIT4 {
    int sum[N];
    inline int lowbit(int x) { return x & -x; }
    inline void insert(int p) {
        for(int i = n - p + 1; i <= n; i += lowbit(i)) ++sum[i];
    }
    inline int query(int p) {
        int res = 0;
        for(int i = n - p + 1; i > 0; i -= lowbit(i)) res += sum[i];
        return res;
    }
}

set<int> st;
void insert(int p, int v, int tm) {
    ++k;
    if(st.empty()) {
        st.insert(p);
        c_ans1 += BIT1::query(a[p]);
        BIT1::insert(a[p]);
        BIT2::insert(a[p]);
        c_ans1 += BIT2::query(a[p]);
        c_ans2 += BIT3::query(p);
        BIT3::insert(p);
        BIT4::insert(p);
        c_ans2 += BIT4::query(p);
        return;
    }
    auto it = st.upper_bound(p);
    if(it == st.end() || a[*it] > v) {
        st.insert(p);
        c_ans1 += BIT1::query(a[p]);
        BIT1::insert(a[p]);
        BIT2::insert(a[p]);
        c_ans1 += BIT2::query(a[p]);
        c_ans2 += BIT3::query(p);
        BIT3::insert(p);
        BIT4::insert(p);
        c_ans2 += BIT4::query(p);
    } else {
        c_ans1 += BIT1::query(a[p]);
        BIT2::insert(a[p]);
        c_ans2 += BIT3::query(p);
        BIT4::insert(p);
        return;
    }
    while((it = st.lower_bound(p)) != st.begin()) {
        --it;
        if(a[*it] > v) {
            c_ans1 -= BIT2::query(a[*it]);
            BIT1::erase(a[*it]);
            c_ans2 -= BIT4::query(*it);
            BIT3::erase(*it);
            st.erase(it);
        } else break;
    }
}

int main() {

    cin >> n >> t;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= t; i++) cin >> q[i];

    {
        static int vis[N];
        for(int i = 1; i <= t; i++) vis[q[i]] = 1;
        for(int i = 1; i <= n; i++) if(!vis[i]) insert(i, a[i], 1);
    }

    ans[1] = k + c_ans1 - c_ans2;

    for(int i = t; i >= 1; i--) {
        insert(q[i], a[q[i]], t - i + 2);
        ans[t - i + 2] = k + c_ans1 - c_ans2;
    }

    for(int i = t + 1; i >= 1; i--) cout << ans[i] << ' ';
    cout << '\n';

    return 0;
}

P9911 [COCI 2023/2024 #2] Kuglice

一个双端队列里面有 \(n\) 个球，每个球有一个颜色。\(A\) 和 \(B\) 玩一个游戏：

\(A\) 先手，两个人轮流操作，每次从队列的最左端或者最右端拿出一个球，如果这种颜色的球是第一次被拿出，拿出它的人获得 \(1\) 分。所有球都拿完后游戏结束。

假设 \(A\) 和 \(B\) 都以最优策略操作，请求出最终得分是多少。

\(n\le 3000\)

不难发现每种颜色只有在第一次出现和最后一次出现时可能会产生贡献。由于局面始终是一个连续段，因此考虑区间 dp，设 \(f_{i,j}\) 表示区间 \([i,j]\)，先手比后手多得多少分。考虑转移，在 \([i,j]\) 区间中，先手只有两种不同的选择：拿走 \(i\) 或拿走 \(j\)；而他会选择更优的一种进行操作。因此这样从 \(f_{i+1,j}\) 和 \(f_{i,j-1}\) 转移即可。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 3010;
const int INF = 0x3f3f3f3f;

int n, m;
int a[N];

void lisanhua() {
    static int num[N];
    for(int i = 1; i <= n; i++) num[++m] = a[i];
    sort(num + 1, num + 1 + m);
    m = unique(num + 1, num + 1 + m) - (num + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + m, a[i]) - num;
}

int mnp[N], mxp[N], col[N];

int f[N][N];

bool check(int i, int j, bool d) {
    int c = d ? a[j] : a[i];
    return mnp[c] >= i && mxp[c] <= j;
}

int main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    lisanhua();

    for(int i = 1; i <= m; i++) mnp[i] = INF;
    for(int i = n; i >= 1; i--) mnp[a[i]] = i;
    for(int i = 1; i <= n; i++) mxp[a[i]] = i;

    for(int i = 1; i <= m; i++) col[mnp[i]] = col[mxp[i]] = i;

    for(int i = 1; i <= n; i++) f[i][i] = check(i, i, 0);

    for(int len = 2; len <= n; len++) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            f[i][j] = max(-f[i + 1][j] + check(i, j, 0), -f[i][j - 1] + check(i, j, 1));
        }
    }

    cout << (m + f[1][n]) / 2 << ':' << (m - f[1][n]) / 2 << '\n';

    return 0;
}