C - 字符串区间跳跃

题目要求对字符串进行操作：输出时，把第k段移动到第k-1段的末尾。关键是要定位三个位置：第k-1段的结束位置、第k段的起始和结束。

遍历字符串时，我们维护当前段的左边界lb和右边界rb。当遇到'1'且前一个字符是'0'（或位于开头）时，开始一个新段；遇到'1'时更新当前段右边界；遇到'0'时，将lb设为当前位置+1，rb设为当前位置，这样下一段起点正确，避免多余计数。

遍历过程中记录第k-1段的右边界prev_end，以及第k段的起止l和r。输出时，当指针到达prev_end时，先输出一段连续的'1'（长度为第k段），然后跳到第k段的结尾r后面继续输出。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    char s[500005];
    cin >> n >> k >> s + 1;

    int prevEnd = 0, segL = 0, segR = 0, segCnt = 0;
    int lb = 1, rb = 0;
    for (int i = 1; i <= n && segCnt <= k; ++i) {
        if (s[i] == '1') {
            if (s[i - 1] != '1') segCnt++;
            rb++;
            if (segCnt == k - 1) prevEnd = rb;
            if (segCnt == k) segL = lb, segR = rb;
        } else {
            lb = i + 1;
            rb = i;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i == segL) {
            i = segR;
            continue;
        }
        cout << s[i];
        if (i == prevEnd)
            for (int j = segL; j <= segR; ++j) cout << '1';
    }
    return 0;
}

D - 序列翻转与优化

给定一个序列，每次操作后序列长度加倍（前半复制，后半翻转大小写）。要查询第k个字符。

思路是逆向定位：不断将k减半直到第一段。每次判断当前字符是否在后半段，如果是则减去前半长度并记录翻转次数，最后根据翻转奇偶性决定是否转换大小写。

实现时，先确定k所在的块号g = (k + n - 1) / n，块内位置pos = k % n（若为0则pos = n）。然后递减块号直到1，每次检查g是否大于当前层长度的一半，若大于则翻转，并减去一半长度。翻转次数对2取模决定最终字符大小写。

#include <bits/stdc++.h>
#define int long long
using namespace std;

char s[200005];
int q, n;

char toggleCase(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a' + 'A';
    else return c - 'A' + 'a';
}

signed main() {
    cin >> s + 1 >> q;
    n = strlen(s + 1);
    while (q--) {
        int k;
        cin >> k;
        int block = (k + n - 1) / n;
        int pos = k % n;
        if (pos == 0) pos = n;

        int flip = 0;
        while (block > 1) {
            int half = 1;
            while (half * 2 <= block) half <<= 1;
            if (block > half) {
                block -= half;
                flip++;
            }
            block >>= 1;
        }
        flip %= 2;
        if (flip) cout << toggleCase(s[pos]) << " ";
        else cout << s[pos] << " ";
    }
    return 0;
}

E - 区间颜色合并与查询

使用并查集维护颜色块。每个并查集节点存储：l[i]（左端点）、r[i]（右端点）、col[i]（颜色）。另外用数组cnt[c]记录颜色c的总个数。

操作1：将x所在块染成颜色c。先找到x的根，更新cnt数组：原颜色减去块长，新颜色加上块长，然后修改根的颜色。之后检查左右邻块：若邻块颜色与新颜色一致，则合并（调用merge合并两个根，并更新根的区间端点）。

操作2：直接输出cnt[c]。

#include <bits/stdc++.h>
using namespace std;

int n, q;
int fa[500005], l[500005], r[500005], col[500005], cnt[500005];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        fa[x] = y;
        l[y] = min(l[y], l[x]);
        r[y] = max(r[y], r[x]);
    }
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        fa[i] = l[i] = r[i] = col[i] = i;
        cnt[i] = 1;
    }

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, c;
            cin >> x >> c;
            x = find(x);
            int len = r[x] - l[x] + 1;
            cnt[col[x]] -= len;
            cnt[c] += len;
            col[x] = c;

            if (l[x] > 1 && col[find(l[x] - 1)] == c)
                merge(l[x] - 1, x);
            if (r[x] < n && col[find(r[x] + 1)] == c)
                merge(r[x] + 1, x);
        } else {
            int c;
            cin >> c;
            cout << cnt[c] << "\n";
        }
    }
    return 0;
}