?原題鏈接：
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;
}
![[概率論基本概念4]什么是無偏估計](http://pic.xiahunao.cn/[概率論基本概念4]什么是無偏估計)
