CCF-CSP认证考试 202303-4 星际网络II 100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202303-4 星际网络II

时间限制： 2.0s
内存限制： 1.0GB

问题描述

随着星际网络的进一步建设和规模的增大，一个新的问题出现在网络工程师面前——地址空间不够用了！原来，星际网络采用了传统的IPv6协议，虽然有 $2^{128}$ 级别的可用地址数量，但面对广袤无垠的宇宙和爆炸式增长的网络用户数，如此庞大的地址空间也面临了用尽的那一天。

新的通信协议的研发工作交给了著名的网络科技圣地——西西艾弗星。最终，经过2333年的不懈努力，西西艾弗星的工程师们设计出了一种新的协议——“西西艾弗IP协议”，又称IPxxaf。

在IPxxaf协议中，一个地址由 $n$ 位二进制位组成，其中 $n$ 是 $16$ 的倍数。日常表示一个地址时，采用类似IPv6协议的十六进制表示法，每 $4$ 位用 : 隔开。如 $n=32$ 时，地址为 2a00:0001 ，即表示一个二进制为 0010 1010 0000 0000 0000 0000 0000 0001 的地址。注意不会出现IPv6中省略每组的前导 0 或用 :: 省略一段 0 的情况。

为方便起见，记 $num(s)$ 为地址 s 按高位在前、低位在后组成的 $n$ 位二进制数，称一段“连续的地址“为 $num(s)$ 成一段连续区间的一系列地址。

西西艾弗星的网络管理员负责地址的分配与管理。最开始，整个地址空间都是未分配的。用户可以随时向管理员申请一些地址：

1 id l r：表示用户 $id$ 申请地址在 $l\sim r$ 范围内（包含 $l$ 和 $r$，下同）的一段连续地址块。

在地址申请操作中，管理员需要先检查地址是否可用。如果用户申请的地址全部未被分配，则检查通过；若地址中存在已经分配给其他用户的地址，则检查失败。

但有一种特殊情况：申请的地址中没有已经分配给其他用户的地址，但含有一些先前已分配给该用户本人的地址。此时可以认为检查通过，但若申请的地址先前已全部分配给该用户则检查失败。

如果上述检查通过，则管理员向用户返回 YES，并将申请的地址分配给该用户；若不通过，则向用户返回 NO，同时不改变现有的地址分配。

网络管理员要定期检查地址的分配情况，具体而言有如下两种操作：

2 s：检查地址 $s$ 被分配给了哪个用户。若未被分配，则结果为 $0$。

3 l r：检查 $l\sim r$ 范围内的所有地址是否完整地分配给了某个用户。若是，回答该用户的编号；若否，回答 $0$。

在整个网络的运行过程中，共出现了 $q$ 次申请地址和检查地址分配的操作。作为西西艾弗星的一名重要的网络技术顾问，你要帮网络管理员依次处理每个操作，并回答相应的结果。

输入格式

从标准输入读入数据。

第一行，$2$ 个正整数 $n,q$。

接下来 $q$ 行，每行一个操作，格式如上所述，其中的 $id$ 为正整数，$l,r,s$ 均为IPxxaf地址串，其中十六进制均用数字和小写字母表示。

输出格式

输出到标准输出。

输出 $q$ 行，每行一个非负整数或字符串，表示此次操作的结果。

其中，对于操作 $1$ ，输出 YES 或 NO；对于操作 $2,3$，输出一个非负整数。

样例输入1

32 12
1 1 0001:8000 0001:ffff
2 0001:a000
3 0001:c000 0001:ffff
1 2 0000:0000 000f:ffff
2 0000:1000
1 1 0001:8000 0001:8fff
1 2 0000:0000 0000:ffff
2 0000:1000
1 1 0002:8000 0002:ffff
3 0001:8000 0002:ffff
1 1 0001:c000 0003:ffff
3 0001:8000 0002:ffff

样例输出1

YES
1
1
NO
0
NO
YES
2
YES
0
YES
1

样例解释

第 $4$ 个操作时，由于用户 $2$ 申请的部分地址已被分配给用户 $1$，因此申请不通过；

第 $6$ 个操作时，由于用户 $1$ 申请的全部地址已被分配给用户 $1$，因此申请不通过；

第 $11$ 个操作时，用户 $1$ 申请的部分地址已被分配给用户 $1$，其余地址尚未被分配，申请通过；

数据范围

对于所有数据，$n\le 512,q\le 5\times 10^4$，$n$ 为 $16$ 的倍数，$id\le q$，对于操作 $1,3$ 保证 $num(l)\le num(r)$。

题解

设计到的地址最多有 $2^{512}$ 个，肯定存不下，将所有涉及到的地址进行离散化。

将所有可能的数放到一个 vector 中，然后运用下列代码将其离散化：

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

离散化后，查询 $id$ 的离散化后的值即可使用：

lower_bound(v.begin(), v.end(), id) - v.begin();

使用线段树维护支持区间赋值和区间查询（$x$ 的单点查询可看成 $[x,x]$ 的区间查询）的计数值 $cnt$（有多少个地址被分配了）、最大值 $mx$（未分配的地址视为 $-\infty$）、最小值 $mn$（未分配的地址视为 $+\infty$）。

对于 1 id l r 操作（操作中的 $l,r$ 均要转换成离散后的值，下同）：

• 查询区间 $[l,r]$ 的 $cnt,mx,mn$；
• 全部未分配，即 $cnt=0$，此时操作成功；
• 余下情况是已经被分配过了（此时 $mx,mn$ 均不为 $\infty$），此时判断是不是仅分配给该用户，即 $mx=mn=id$，否则操作失败；
• 余下情况是已经被分配过了，且仅分配给了该用户，此时判断是否全部分配给了该用户，即 $cnt=r-l+1$，满足则操作失败，否则操作成功；
• 操作成功后给区间 $[l,r]$ 赋值，对于 $cnt$ 来说，区间的值均为 $1$；对于 $mx,mn$ 来说，区间的值均为 $id$。
• 为了防止原先不连续的区间变成了连续的（区间 $[0,1],[3,4]$ 离散化后有可能变为 $[0,1],[2,3]$），要将右端点 $+1$ 的值一并进行离散化。

对于 2 s 操作：仅需要判断区间 $[s,s]$ 的 $cnt$ 值是否为 $1$ 即可知是否分配给了用户，如果分配给了用户，输出 $mx$ 或者 $mn$ 均可，否则输出 $0$。

对于 3 l r 操作：先判断是否全部进行了分配，即区间 $[l,r]$ 的 $cnt$ 是否满足 $cnt=r-l+1$，然后再判断是否分配给了同一个用户，即 $mx=mn$，如果满足输出 $mx$ 或者 $mn$ 均可，否则输出 $0$。

时间复杂度：$\mathcal{O}(nq\log q)$。

参考代码（296ms，54.10MB）

/*
    Created by Pujx on 2024/3/21.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

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

vector<vector<int>> v;
struct query { int op, id; vector<int> l, r; } qu[N];

template <typename T> struct SegmentTree {
    struct TreeNode { int l, r; T st, cnt, mx, mn; } tr[N << 2];
    void pushup(int s) {
        tr[s].cnt = tr[ls].cnt + tr[rs].cnt;
        tr[s].mx = max(tr[ls].mx, tr[rs].mx);
        tr[s].mn = min(tr[ls].mn, tr[rs].mn);
    }
    void pushdown(int s) {
        if (tr[s].st != numeric_limits<T>::min()) {
            tr[ls].st = tr[rs].st = tr[s].st;
            tr[ls].cnt = tr[ls].r - tr[ls].l + 1;
            tr[rs].cnt = tr[rs].r - tr[rs].l + 1;
            tr[ls].mx = tr[rs].mx = tr[s].st;
            tr[ls].mn = tr[rs].mn = tr[s].st;
            tr[s].st = numeric_limits<T>::min();
        }
    }
    void build(int l, int r, int s = 1) {
        tr[s].l = l, tr[s].r = r;
        tr[s].st = numeric_limits<T>::min();
        tr[s].cnt = 0;
        tr[s].mx = numeric_limits<T>::min();
        tr[s].mn = numeric_limits<T>::max();
        if (l == r) return;
        int mid = l + r >> 1;
        if (l <= mid) build(l, mid, ls);
        if (mid < r) build(mid + 1, r, rs);
        pushup(s);
    }
    void modify(int l, int r, T val, int s = 1) {
        if (l <= tr[s].l && tr[s].r <= r) {
            tr[s].st = val;
            tr[s].cnt = tr[s].r - tr[s].l + 1;
            tr[s].mx = tr[s].mn = val;
            return;
        }
        pushdown(s);
        int mid = tr[s].l + tr[s].r >> 1;
        if (l <= mid) modify(l, r, val, ls);
        if (mid < r) modify(l, r, val, rs);
        pushup(s);
    }
    T query(int l, int r, int s = 1) {
        if (l <= tr[s].l && tr[s].r <= r) return tr[s].cnt;
        int mid = tr[s].l + tr[s].r >> 1;
        T ans = T();
        pushdown(s);
        if (l <= mid) ans += query(l, r, ls);
        if (mid < r) ans += query(l, r, rs);
        return ans;
    }
    T queryMax(int l, int r, int s = 1) {
        if (l <= tr[s].l && tr[s].r <= r) return tr[s].mx;
        int mid = tr[s].l + tr[s].r >> 1;
        T ans = numeric_limits<T>::min();
        pushdown(s);
        if (l <= mid) ans = max(ans, queryMax(l, r, ls));
        if (mid < r) ans = max(ans, queryMax(l, r, rs));
        return ans;
    }
    T queryMin(int l, int r, int s = 1) {
        if (l <= tr[s].l && tr[s].r <= r) return tr[s].mn;
        int mid = tr[s].l + tr[s].r >> 1;
        T ans = numeric_limits<T>::max();
        pushdown(s);
        if (l <= mid) ans = min(ans, queryMin(l, r, ls));
        if (mid < r) ans = min(ans, queryMin(l, r, rs));
        return ans;
    }
};
SegmentTree<int> T;

vector<int> read() {
    string s; cin >> s;
    vector<int> ans(n / 16, 0);
    for (int i = 0; i < s.length(); i += 5)
        for (int j = 0; j < 4; j++)
            ans[i / 5] = ans[i / 5] * 16 + s[i + j] - (s[i + j] < 'a' ? '0' : 'a' - 10);
    v.emplace_back(ans);
    return ans;
}

void work() {
    cin >> n >> q;
    v.emplace_back(vector<int>(n / 16, -1));
    for (int i = 1; i <= q; i++) {
        cin >> qu[i].op;
        if (qu[i].op == 1) {
            cin >> qu[i].id, qu[i].l = read(), qu[i].r = read();
            if (qu[i].r != vector<int>(n / 16, 65535)) {
                vector<int> tem = qu[i].r;
                int p = tem.size() - 1;
                while (tem[p] == 65535) tem[p--] = 0;
                tem[p]++;
                v.emplace_back(tem);
            }
        }
        else if (qu[i].op == 2) qu[i].l = qu[i].r = read();
        else qu[i].l = read(), qu[i].r = read();
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    T.build(1, v.size() - 1);
    for (int i = 1; i <= q; i++) {
        int l = lower_bound(all(v), qu[i].l) - v.begin();
        int r = lower_bound(all(v), qu[i].r) - v.begin();
        int cnt = T.query(l, r), mx = T.queryMax(l, r), mn = T.queryMin(l, r);
        if (qu[i].op == 1) {
            bool flag = !cnt || (mx == mn && mx == qu[i].id && cnt < r - l + 1);
            if (flag) T.modify(l, r, qu[i].id);
            YN(flag);
        }
        else if (qu[i].op == 2) cout << (cnt ? mx : 0) << endl;
        else cout << (cnt == r - l + 1 && mx == mn ? mx : 0) << endl;
    }
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

1. 代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
2. #pragma ... 是用来开启 O2、O3 等优化加快代码速度。
3. 中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
4. "debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
5. ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
6. 将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。