第29次CCFCSP题4解题报告

2024-08-14

2.6k字 | 预计阅读时长: 11min

阅读量: 次

本次报告撰写人：WilliamZH
题目：202303-4，第29次CCFCSP
使用语言：C++

202303-4 星际网络 II

题目描述：

地址分配采用类似 IPv6的十六进制表示法，每 $4$ 位用”: “隔开。地址长度 $n$ 是 $16$ 的倍数，每个地址由 $n$ 位二进制位组成。
三种操作：

1 id l r：表示用户 $id$ 申请地址在 $l∼r$ 范围内（包含 $l$ 和 $r$）的一段连续地址块。
若申请的地址全部未被分配，则检查通过；若地址中存在已分配给其他用户的地址，则检查失败。
特殊情况：申请地址中没有已分配给其他用户的地址，但含有已分配给该用户的地址。此时认为检查通过，但若申请的地址先前已全部分配给该用户则检查失败。
如果检查通过，则返回 YES，并将申请地址分配给该用户；若不通过，返回 NO，不改变现有地址分配。
2 s：检查地址 $s$ 被分配给了哪个用户。若未被分配，则结果为 $0$。
3 l r：检查 $l∼r$ 范围内的所有地址是否完整分配给了某用户。若是，回答用户编号；若否，回答 $0$。
输入格式：
第一行，$2$ 个正整数 $n,q$。接下来 $q$ 行，每行一个操作，格式如上所述。
输出格式：
输出 $q$ 行，每行一个非负整数或字符串，表示此次操作的结果。
$n≤512,id≤q≤5×10^4$

题解：

线段树。

存储数据：
定义一个结构体 node，用来处理每个操作的信息：op 表示操作类型，id 表示用户编号，l，r 表示左边界和右边界。
1. 对于操作 1：
  将左右边界分别存到一个数组里，并计算右边界+1 后的地址，也存到数组里（将地址范围变成一个左闭右开的区间，方便进行地址分配和范围的比较）。
2. 对于操作 2：仅读取地址并将其添加到数组。
3. 对于操作 3：读取左边界和右边界，并将它们和右边界的下一个地址添加到数组。
处理数据：
最大值和最小值存储地址分配 id 的最大值和最小值，和值存储当前地址块已经有多少地址被分配。
1. 对数组进行排序并删去重复的元素。
2. 构造线段树：build 函数使用递归方式构建线段树。初始化每个节点的属性，将范围分为两半，并在每一半上调用自身以构建子节点。最后，调用 pushup 函数更新当前节点的值。
  build 函数三个参数：id 表示当前节点，L 表示当前节点区间的左边界，R 表示当前节点区间的右边界。首先为当前节点设置左边界 l[id]、右边界 r[id]、最小值 mn[id] 和最大值 mx[id] 初始值。如果当前节点的左边界大于等于右边界（即区间只有一个元素），则直接返回，当前节点为叶子节点。否则，计算当前区间的中间位置 mid，然后递归地构建左子树和右子树。左子树的索引为 id << 1；右子树的索引为 id << 1 | 1。
  pushup 函数利用左子节点和右子节点的索引访问对应的子节点的值。然后，通过 max 函数更新当前节点的最大值，通过 min 函数更新当前节点的最小值，通过加法操作更新当前节点的和值。
进行操作 1：
先查询该区间内地址编号的最小值，如果最小值是初始值，说明没有进行分配，直接全部赋值为 id。如果发现最小值不是初始值，查最大值，如果最小值和最大值不同，说明这块地址多人分配，无需操作；如果最小值和最大值相同，那么地址分配给了一个人，然后用区间和来查询是否全部地址都分配给了这个人，如果区间和等于区间长度，说明这段地址空间全部分配给了一个人，否则判断所查询值与待分配编号是否相同。
1. 先通过 find 函数查询左右边界在数组中的位置。**(使用 lower_bound 函数查找，时间复杂度 $O(log\ n)$，若直接遍历查找会超时)**
2. 查询当前区间地址是否被分配：
  1. judgemin(int id, int L, int R) 函数: 如果当前节点的区间完全包含在目标区间内，则直接返回当前节点的最小值。否则，调用 pushdown 函数将延迟标记向下传递，并通过递归调用查询左右子节点的最小值，并返回其中的较小值。
  2. pushdown(int id): 如果当前节点的延迟标记 lazy[id] 不等于预设值，则将节点的子节点进行更新。最后将当前节点的延迟标记重新设置为预设值。
3. 如果未被分配，输出 YES 并调用 update 函数，将该区间内的节点信息更新。
4. 如果只分配给了一个人
  1. 通过函数 judgesum 判断是否全部分配给了当前 id。
    首先，检查当前节点是否完全位于查询区间内，如果是，则直接返回该节点的和值 sum[id]。否则，调用 pushdown 函数将当前节点的懒惰标记进行推送，然后计算当前节点的中点 mid。接着，根据 mid 和查询区间的关系，递归调用 judgesum 函数在左子节点或右子节点上进行查询，并将两者的结果累加到 ans 变量中。最后，返回 ans。
  2. 如果全部分配，则输出 NO，否则输出 YES并更新信息。
5. 如果分配给其他人，输出 NO
进行操作 2：
单点查询。
进行操作 3；
与操作 1 类似。

#include<iostream>
#include<map>
#include<vector>
#include<string>
#include<algorithm>
#define ls(o) (o << 1)
#define rs(o) (ls(o) | 1)
#define ini 0x3f3f3f3f
using namespace std;

const int N = 1e6 + 10;
int n, q;
vector<string> saveadds;
struct node {
    int op, id;
    string l, r;
}act[N];
int l[N], r[N], mx[N], mn[N], lazy[N], sum[N];

void pushup(int id) {
    mx[id] = max(mx[ls(id)], mx[rs(id)]);
    mn[id] = min(mn[ls(id)], mn[rs(id)]);
    sum[id] = sum[ls(id)] + sum[rs(id)];
}
//建树
void build(int id, int L, int R) {
    l[id] = L;
    r[id] = R;
    mn[id] = ini;
    mx[id] = -ini;
    lazy[id] = ini;
    if (L >= R) 
        return;
    int mid = L + R >> 1;
    build(ls(id), L, mid);
    build(rs(id), mid + 1, R);
    pushup(id);
}

void pushdown(int id) {
    if (lazy[id] != ini) {
        sum[ls(id)] = r[ls(id)] - l[ls(id)] + 1;
        sum[rs(id)] = r[rs(id)] - l[rs(id)] + 1;
        mx[ls(id)] = lazy[id];
        mx[rs(id)] = lazy[id];
        mn[ls(id)] = lazy[id];
        mn[rs(id)] = lazy[id];
        lazy[ls(id)] = lazy[id];
        lazy[rs(id)] = lazy[id];
        lazy[id] = ini;
    }
}
//查找数组中出现s的位置
int find(string s) {
    return lower_bound(saveadds.begin(), saveadds.end(), s) - saveadds.begin() + 1;
}

int judgemin(int id, int L, int R) {
    if (l[id] >= L && r[id] <= R) 
        return mn[id];
    pushdown(id);
    int mid = l[id] + r[id] >> 1;
    int ans = ini;
    if (mid >= L) 
        ans = judgemin(ls(id), L, R);
    if (mid + 1 <= R) 
        ans = min(ans, judgemin(rs(id), L, R));
    return ans;
}
//更新节点信息
void update(int id, int L, int R, int val) {
    if (l[id] >= L && r[id] <= R) {
        sum[id] = r[id] - l[id] + 1;
        mx[id] = val;
        mn[id] = val;
        lazy[id] = val;
        return;
    }
    pushdown(id);
    int mid = l[id] + r[id] >> 1;
    if (mid >= L) 
        update(ls(id), L, R, val);
    if (mid + 1 <= R) 
        update(rs(id), L, R, val);
    pushup(id);
}
//判断该地址是否已经全部分配给id 
int judgesum(int id, int L, int R) {
    if (l[id] >= L && r[id] <= R) 
        return sum[id];
    pushdown(id);
    int mid = l[id] + r[id] >> 1;
    long long ans = 0;
    if (mid >= L) 
        ans += judgesum(ls(id), L, R);
    if (mid + 1 <= R) 
        ans += judgesum(rs(id), L, R);
    return ans;
}

int judgemax(int id, int L, int R) {
    if (l[id] >= L && r[id] <= R) 
        return mx[id];
    pushdown(id);
    int mid = l[id] + r[id] >> 1;
    int ans = -ini;
    if (mid >= L) 
        ans = judgemax(ls(id), L, R);
    if (mid + 1 <= R) 
        ans = max(ans, judgemax(rs(id), L, R));
    return ans;
}
//计算右边界的下一个地址
string next(string s) {
    string result = s;
    bool carry = true;
    for (int i = s.size() - 1; i >= 0; i--) {
        if (s[i] == ':')
            continue;
        else if (s[i] == 'f' && carry)
            result[i] = '0';
        else if (s[i] == '9') {
            result[i] = 'a';
            carry = false;
            break;
        }
        else {
            result[i] = s[i] + 1;
            carry = false;
            break;
        }
    }
    return result;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> q;
	for (int i = 1; i <= q; i++) {
		cin >> act[i].op;
		if (act[i].op == 1) {
			cin >> act[i].id >> act[i].l >> act[i].r;
			saveadds.push_back(act[i].l);
			saveadds.push_back(act[i].r);
			saveadds.push_back(next(act[i].r));
		}
        else if (act[i].op == 2) {
            cin >> act[i].l;
            saveadds.push_back(act[i].l);
        }
        else {
            cin >> act[i].l >> act[i].r;
            saveadds.push_back(act[i].l);
            saveadds.push_back(act[i].r);
            saveadds.push_back(next(act[i].r));
        }
	}
    sort(saveadds.begin(), saveadds.end());
    //去除数组中的重复元素
    vector<string> unique_values;  // 用于存储去重后的唯一元素
    for (int i = 0; i < saveadds.size(); i++)
        if (i == 0 || saveadds[i] != saveadds[i - 1])
            unique_values.push_back(saveadds[i]);
    saveadds = unique_values;  // 将原容器替换为去重后的结果
    //建树
    build(1, 1, saveadds.size());
    for (int i = 1; i <= q; i++) {
        if (act[i].op == 1) {
            int ll = find(act[i].l), rr = find(act[i].r);
            //该地址全部未被分配
            if (judgemin(1, ll, rr) == ini) {   
                cout << "YES\n";
                update(1, ll, rr, act[i].id);
            }
            //该地址是否只分配给了一个人 
            else if (judgemin(1, ll, rr) == act[i].id && judgemax(1, ll, rr) == act[i].id) {
                //该地址本来就已经全部分配给了id 
                if (judgesum(1, ll, rr) == (rr - ll + 1))
                    cout << "NO\n";
                else {
                    cout << "YES\n";
                    update(1, ll, rr, act[i].id);
                }
            }
            //该地址分配给了其他人
            else
                cout << "NO\n";
        }
        else if (act[i].op == 2) {
            int ll = find(act[i].l);
            int t = judgemax(1, ll, ll);
            if (t != -ini)
                cout << t << "\n";
            else
                cout << "0\n";
        }
        else {
            int ll = find(act[i].l), rr = find(act[i].r);
            int id = judgemin(1, ll, rr);
            //该地址是否只分配给了一个人 
            if (id == judgemax(1, ll, rr) && judgesum(1, ll, rr) == (rr - ll + 1))
                cout << id << "\n";
            else
                cout << "0\n";
        }
    }
    return 0;
}