#include #include // 演算法 / Algorithm: // 把 s 切成交替的 0/1 段;對每個「被 0 包圍的 1 段」淨收益 = 左0段長 + 右0段長。 // Split s into alternating runs; a trade's net gain = leftZeroLen + rightZeroLen. // 內部段用線段樹做區間最大查詢;兩端被截斷的段單獨處理。 // Use a segment tree for interior runs; handle the two clamped boundary runs specially. // ---- 線段樹全域變數 / segment-tree globals ---- static int *g_tree; // 線段樹儲存陣列 / the tree array static int *g_ans; // 每個段的淨收益候選值 / per-run gain values // 建樹:把 g_ans[lo..hi] 的最大值填進 g_tree / build max-tree over run range [lo,hi] static void build(int node, int lo, int hi) { if (lo == hi) { g_tree[node] = g_ans[lo]; return; } // 葉子:直接存該段的值 / leaf holds one run's value int mid = (lo + hi) / 2; // 對半切 / split in half build(node * 2, lo, mid); // 建左子樹 / left child build(node * 2 + 1, mid + 1, hi); // 建右子樹 / right child int L = g_tree[node * 2], R = g_tree[node * 2 + 1]; // 取兩子結果 / children results g_tree[node] = L > R ? L : R; // 父結點存較大者 / parent = max of children } // 區間最大查詢:回傳 g_ans 在下標 [ql,qr] 內的最大值 / range-max over [ql,qr] static int query(int node, int lo, int hi, int ql, int qr) { if (qr < lo || hi < ql) return 0; // 此結點與查詢無交集 / no overlap if (ql <= lo && hi <= qr) return g_tree[node]; // 此結點被查詢完全包含 / fully covered int mid = (lo + hi) / 2; // 否則往下分 / otherwise recurse int L = query(node * 2, lo, mid, ql, qr); // 查左半 / query left int R = query(node * 2 + 1, mid + 1, hi, ql, qr); // 查右半 / query right return L > R ? L : R; // 合併取最大 / combine by max } int* maxActiveSectionsAfterTrade(char* s, int** queries, int queriesSize, int* queriesColSize, int* returnSize) { int n = (int)strlen(s); // 字串長度 / string length // 為每個段分配空間;段數最多 n 個 / at most n runs int *rs = malloc(sizeof(int) * n); // 每段起點 / run start index int *re = malloc(sizeof(int) * n); // 每段終點 / run end index int *rv = malloc(sizeof(int) * n); // 每段的值 0 或 1 / run value int *segId = malloc(sizeof(int) * n); // 位置 -> 所屬段編號 / position to run id int m = 0; // 段的總數 / number of runs int onesTotal = 0; // 整串 1 的個數 / total ones in s for (int i = 0; i < n; ) { // 掃描整串切段 / scan and cut into runs int j = i; // j 找出這一段的結尾 / j finds the run end while (j < n && s[j] == s[i]) j++; // 只要字元相同就延伸 / extend while equal rs[m] = i; re[m] = j - 1; rv[m] = s[i] - '0'; // 記錄這一段 / record this run ('0'->0,'1'->1) if (rv[m] == 1) onesTotal += (j - i); // 若是 1 段就累加長度 / count ones for (int k = i; k < j; k++) segId[k] = m; // 標記此段內每個位置 / label positions m++; // 段數 +1 / next run i = j; // 從下一段開始 / move to next run } // 預算每個 1 段的淨收益 ans[i] = len[i-1] + len[i+1] / precompute gains g_ans = malloc(sizeof(int) * m); for (int i = 0; i < m; i++) { if (rv[i] == 1 && i > 0 && i < m - 1) // 必須是內部的 1 段 / interior 1-run only g_ans[i] = (re[i-1] - rs[i-1] + 1) + (re[i+1] - rs[i+1] + 1); // 左段長 + 右段長 / two neighbor lengths else g_ans[i] = 0; // 0 段或邊界段無收益 / no gain otherwise } g_tree = malloc(sizeof(int) * 4 * m); // 線段樹需要約 4m 空間 / tree needs ~4m nodes build(1, 0, m - 1); // 從根結點 1 建樹 / build from root node 1 int *res = malloc(sizeof(int) * queriesSize); // 答案陣列 / result array for (int q = 0; q < queriesSize; q++) { int l = queries[q][0], r = queries[q][1]; // 這個查詢的區間 / this query's range int a = segId[l], b = segId[r]; // 左右端所在的段 / runs containing l and r int best = 0; // 目前最大淨收益 / best gain so far if (a != b) { // a==b 表示整段同字元,無法交易 / single run: no trade // loIdx/hiIdx 是「完全落在範圍內」的最小/最大段編號 / smallest & largest fully-inside runs int loIdx = (rs[a] == l) ? a : a + 1; // 段 a 只有從 l 起才算完整 / run a is full only if it starts at l int hiIdx = (re[b] == r) ? b : b - 1; // 段 b 只有在 r 結束才算完整 / run b is full only if it ends at r // 內部 1 段:左右鄰居都完整 -> 用線段樹 / interior runs with both neighbors inside if (loIdx + 1 <= hiIdx - 1) { // 該範圍非空才查 / query only if range non-empty int v = query(1, 0, m - 1, loIdx + 1, hiIdx - 1); if (v > best) best = v; } // 左邊界候選:l 落在 0 段裡,右邊第一個 1 段的左 0 段被截斷 / left clamped candidate if (rv[a] == 0) { // l 在 0 段內 / l sits in a 0-run int i = a + 1; // 下一段必是 1 段 / next run is a 1-run if (re[i] <= r && // 該 1 段完整落在範圍內 / 1-run fully inside i + 1 <= m - 1 && rs[i+1] <= r) { // 且右側範圍內還有 0 / and a 0 exists to its right int rz = (re[i+1] < r ? re[i+1] : r) - rs[i+1] + 1; // 右 0 段長(必要時截斷) / right zero length, clamped int lz = rs[i] - l; // 左 0 段長:從 l 到 1 段前 / left zeros from l if (lz + rz > best) best = lz + rz; // 更新最大 / update best } } // 右邊界候選:r 落在 0 段裡,左邊最後一個 1 段的右 0 段被截斷 / right clamped candidate if (rv[b] == 0) { // r 在 0 段內 / r sits in a 0-run int i = b - 1; // 前一段必是 1 段 / previous run is a 1-run if (rs[i] >= l && // 該 1 段完整落在範圍內 / 1-run fully inside i - 1 >= 0 && re[i-1] >= l) { // 且左側範圍內還有 0 / and a 0 exists to its left int lz = re[i-1] - (rs[i-1] > l ? rs[i-1] : l) + 1; // 左 0 段長(必要時截斷) / left zeros, clamped int rz = r - re[i]; // 右 0 段長:從 1 段後到 r / right zeros up to r if (lz + rz > best) best = lz + rz; // 更新最大 / update best } } } res[q] = onesTotal + best; // 答案 = 全串 1 數 + 最佳收益 / total ones + best gain } *returnSize = queriesSize; // 告訴呼叫者答案長度 / set output length free(rs); free(re); free(rv); free(segId); // 釋放暫存 / free scratch arrays free(g_ans); free(g_tree); // 釋放線段樹 / free tree return res; // 交還答案(呼叫者負責釋放) / caller frees res }