第35次CCF计算机软件能力认证-5-木板切割-海口c网

原题链接：

TUOJ

我自己写的35分正确但严重超时的代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int n, m, k;cin >> n >> m >> k;vector<unordered_map<int, int>> mp(2);int y;for (int i = 1; i <= n; i++){cin >> y;mp[1][i] = y;}while (k--){int x, l, r;cin >> x >> l >> r;unordered_map<int, int> tmp;int color_num = 0, num = 0;unordered_set<int> color_type;int pos = -1;for (int i = l; i <= r; i++){if (mp[x].count(i)){int color = mp[x][i];tmp[i] = color;color_type.insert(color);if (pos == -1 || tmp[i] != tmp[pos])num++;pos = i;mp[x].erase(i);}}color_num = color_type.size();mp.push_back(tmp);cout << color_num << ' ' << num << endl;}
}

过了7个样例，35分，对于现在的我来说也还行

知道你们肯定不满足35分，特地给出了大佬写的代码，300行+，自己写一个数据结构，我只能说nb，水平有限，不作说明

CCF-CSP第35次认证第五题——木板切割【C++满分题解；平衡树set，线段树，分块预处理，位图；区间合并、懒更新与分治、位运算优化】_csp 木板切割-CSDN博客

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstdint>
using namespace std;// ------------------------
// 线段树部分：支持查询区间内颜色段数、左右端颜色
// ------------------------// 线段树节点结构
struct SegmentTreeNode {int left, right;        // 节点区间 [left, right]int segment_count;      // 该区间内颜色段数（相邻颜色相同视为同一段）int left_color, right_color;  // 区间最左/最右的颜色SegmentTreeNode *left_child, *right_child;SegmentTreeNode(int l, int r): left(l), right(r), segment_count(1), left_color(0), right_color(0),left_child(nullptr), right_child(nullptr) {}
};// 建树：叶节点对应单个位置，其颜色直接取自 colors 数组
SegmentTreeNode* buildTree(const vector<int>& colors, int l, int r) {SegmentTreeNode* node = new SegmentTreeNode(l, r);if (l == r) {node->left_color = node->right_color = colors[l];node->segment_count = 1;return node;}int mid = (l + r) / 2;node->left_child = buildTree(colors, l, mid);node->right_child = buildTree(colors, mid + 1, r);node->left_color = node->left_child->left_color;node->right_color = node->right_child->right_color;// 初步合并左右子区间的段数node->segment_count = node->left_child->segment_count + node->right_child->segment_count;// 如果左右子区间的边界颜色相同，则合并为一段if (node->left_child->right_color == node->right_child->left_color) {node->segment_count--;}return node;
}// 查询区间 [l, r] 的颜色段数以及左右端颜色
void query(SegmentTreeNode* node, int l, int r, int& segment_count, int& first_color, int& last_color) {if (node == nullptr || node->right < l || node->left > r) {segment_count = 0;first_color = -1;last_color = -1;return;}if (l <= node->left && node->right <= r) {segment_count = node->segment_count;first_color = node->left_color;last_color = node->right_color;return;}int left_seg = 0, right_seg = 0;int left_first = -1, left_last = -1;int right_first = -1, right_last = -1;query(node->left_child, l, r, left_seg, left_first, left_last);query(node->right_child, l, r, right_seg, right_first, right_last);if (left_seg == 0) {segment_count = right_seg;first_color = right_first;last_color = right_last;} else if (right_seg == 0) {segment_count = left_seg;first_color = left_first;last_color = left_last;} else {segment_count = left_seg + right_seg;if (left_last == right_first) segment_count--;first_color = left_first;last_color = right_last;}
}// ------------------------
// 块状分解部分：预处理整个颜色数组以快速回答区间内“不同颜色数”查询  
// 用 64 位整数数组模拟 bitset，每一位表示某种颜色是否出现。
// ------------------------int B;            // 块大小（可调）
int numBlocks;    // 总块数
int W;            // 每个 bitset 需要的 64 位整数数量（W = ceil(m/64)）
vector<int> colors;  // 颜色数组（1-indexed）
vector<vector<uint64_t>> blockOR;  // 每块预处理的“或”结果// 查询区间 [L,R] 内颜色的 bitset（即各颜色是否出现的标记），返回大小为 W 的 uint64_t 数组
vector<uint64_t> distinctQuery(int L, int R) {vector<uint64_t> res(W, 0ULL);int startBlock = (L - 1) / B;int endBlock = (R - 1) / B;if (startBlock == endBlock) {// 区间完全落在同一块，直接遍历求或for (int i = L; i <= R; i++) {int col = colors[i];int idx = col - 1;res[idx / 64] |= (1ULL << (idx % 64));}} else {// 处理起始块的部分int blockStartEnd = (startBlock + 1) * B;for (int i = L; i <= blockStartEnd; i++) {int col = colors[i];int idx = col - 1;res[idx / 64] |= (1ULL << (idx % 64));}// 处理中间整块for (int b = startBlock + 1; b < endBlock; b++) {for (int j = 0; j < W; j++) {res[j] |= blockOR[b][j];}}// 处理结束块的部分int endBlockStart = endBlock * B + 1;for (int i = endBlockStart; i <= R; i++) {int col = colors[i];int idx = col - 1;res[idx / 64] |= (1ULL << (idx % 64));}}return res;
}// 将 src 的 bitset 结果“或”到 dest 上
void unionBitset(vector<uint64_t>& dest, const vector<uint64_t>& src) {for (int i = 0; i < W; i++) {dest[i] |= src[i];}
}// 统计 bitset 中 1 的个数，即不同颜色数
int countBits(const vector<uint64_t>& bs) {int cnt = 0;for (auto x : bs) {cnt += __builtin_popcountll(x);}return cnt;
}// ------------------------
// 主函数
// ------------------------
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, k;cin >> n >> m >> k;// colors 数组采用 1-indexed，下标 1~ncolors.resize(n + 1);bool allDistinct = true; // 标记是否所有颜色都不相同（即 c[i] = i 的情况），用于特殊情况优化for (int i = 1; i <= n; i++) {cin >> colors[i];if (colors[i] != i)allDistinct = false;}// 构建线段树（当 allDistinct 为 true 时，本质上不用查询区间信息，但为了代码统一构造）SegmentTreeNode* root = buildTree(colors, 1, n);// ------------------------// 块状分解预处理：构造每块的颜色“或”信息// ------------------------B = 512;  // 块大小（可根据实际情况调节）numBlocks = (n + B - 1) / B;// 每个 bitset 长度为 W = ceil(m/64)W = (m + 63) / 64;blockOR.assign(numBlocks, vector<uint64_t>(W, 0ULL));for (int b = 0; b < numBlocks; b++) {int L = b * B + 1;int R = min(n, (b + 1) * B);for (int i = L; i <= R; i++) {int col = colors[i];int idx = col - 1;blockOR[b][idx / 64] |= (1ULL << (idx % 64));}}// ------------------------// 每块木板维护一个 set，记录当前木板上存在的区间（区间端点均为原数组下标）// 初始时 1 号木板包含整个区间 [1, n]// ------------------------// 用 pair<int, int> 表示一个区间 [first, second]vector<set<pair<int, int>>> boards(k + 2);  // 共 k+1 号木板，编号 1~k+1boards[1].insert({1, n});// 处理 k 次切割操作// 每次输入 x, l, r 表示对木板 x 的区间 [l, r] 进行切割，// 切下来的部分构成新的木板，输出：切下部分的不同颜色数 和 颜色段数（合并相邻颜色相同的段后）for (int op = 1; op <= k; op++) {int x, l, r;cin >> x >> l >> r;set<pair<int, int>>& current = boards[x];// 收集本次切割中，被切下来的区间vector<pair<int, int>> cut_segments;// 在当前木板的区间集合中找到所有与 [l, r] 有交集的区间auto it = current.lower_bound({l, 0});if (it != current.begin()) --it;while (it != current.end()) {int s = it->first, e = it->second;if (s > r) break;  // 后面的区间起点超过 r，无需继续if (e < l) { // 当前区间完全在 [l, r] 之前++it;continue;}// 求交集int a = max(s, l), b = min(e, r);if (a <= b) {cut_segments.push_back({a, b});// 从当前木板中移除该区间，并将剩余部分（若有）重新加入auto temp = it;++it;current.erase(temp);if (s < a) {current.insert({s, a - 1});}if (b < e) {current.insert({b + 1, e});}} else {++it;}}if (cut_segments.empty()) {cout << "0 0\n";boards[op + 1].clear();continue;}// 为了后续合并相邻区间处理，先对切割出的区间按起点排序sort(cut_segments.begin(), cut_segments.end());// 根据是否满足 c[i] = i（即 allDistinct 为 true）分别处理if (allDistinct) {// 在全不相同的情况下，每个区间内不同颜色数和颜色段数均等于区间长度int distinct_count = 0, total_segments = 0;for (auto& seg : cut_segments) {int len = seg.second - seg.first + 1;distinct_count += len;total_segments += len;}cout << distinct_count << " " << total_segments << "\n";} else {// ------------------------// 1. 利用块状分解“distinctQuery”求多个区间中不同颜色的并集// ------------------------vector<uint64_t> union_bs(W, 0ULL);// 统计所有被切区间的颜色（并集）for (auto& seg : cut_segments) {int a = seg.first, b = seg.second;vector<uint64_t> bs = distinctQuery(a, b);unionBitset(union_bs, bs);}int distinct_count = countBits(union_bs);// ------------------------// 2. 利用线段树查询每个被切区间的颜色段数，然后对相邻区间作合并处理// ------------------------int total_segments = 0;for (auto& seg : cut_segments) {int a = seg.first, b = seg.second;int seg_count, first, last;query(root, a, b, seg_count, first, last);total_segments += seg_count;}// 如果相邻两个切割区间原本是连续的且两端颜色相同，则合并后颜色段数减少1int merged = 0;for (int i = 1; i < (int)cut_segments.size(); i++) {int prev_b = cut_segments[i - 1].second;int curr_a = cut_segments[i].first;if (prev_b + 1 == curr_a) {int dummy;int col1, col2;query(root, prev_b, prev_b, dummy, col1, col1);query(root, curr_a, curr_a, dummy, col2, col2);if (col1 == col2) {merged++;}}}total_segments -= merged;cout << distinct_count << " " << total_segments << "\n";}// 新木板编号为 op+1，记录本次切下的所有区间boards[op + 1].clear();for (auto& seg : cut_segments) {boards[op + 1].insert(seg);}}return 0;
}