CodeForces - 240F TorCoder

Description

给一个长度为 \(n(n\le10^5)\) 的字符串， \(m\) 次操作，每次给出一个区间 \([l,r]\) ，将 \([l,r]\) 中的字符串重排列成一个回文串，如无法排列则忽略此操作，如有多种方案取字典序最小的一种。

Solution

我的做法比较蠢，开 \(26\) 个线段树，每个记录区间内字符的出现次数。

那么每次对区间内每个字符进行统计，如果是偶数长度区间却有字符出现了奇数次，或者奇数长度区间有超过一个字符出现了奇数次，那么该操作不合法。

考虑如何修改。先将区间清零，然后按字典序插入，前后都要处理。若出现了奇数次，则在 \(mid\) 处单点更新。

如果你 Wrong answer on test 7 ，那么请试试这一组样例：

19 1
hhhhhllllllqqqqqqvv
1 19

正确答案应该是

hhlllqqqvhvqqqlllhh

细节略多。

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

template <class T> void read(T &x) {
    x = 0; bool flag = 0; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == 45) flag = 1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; if (flag) x = -x;
}

#define N 100010
#define rep(i, a, b) for (int i = (a); i <= (b); i++)

struct segmentTree {
    int sum[N << 2], tag[N << 2], a[N];
#define mid (l + r >> 1)
#define ls rt << 1
#define rs ls | 1
    inline void pushUp(int rt) { sum[rt] = sum[ls] + sum[rs]; }
    void build(int rt, int l, int r) {
        tag[rt] = -1;
        if (l == r) { sum[rt] = a[l]; return; }
        build(ls, l, mid), build(rs, mid + 1, r);
        pushUp(rt);
    }
    inline void pushDown(int rt, int l, int r) {
        if (tag[rt] != -1) {
            tag[ls] = tag[rs] = tag[rt];
            sum[ls] = (mid - l + 1) * tag[ls], sum[rs] = (r - mid) * tag[rs];
            tag[rt] = -1;
        }
    }
    int query(int rt, int l, int r, int L, int R) {
        if (L <= l && r <= R) return sum[rt];
        pushDown(rt, l, r);
        int ret = 0;
        if (L <= mid) ret += query(ls, l, mid, L, R);
        if (R > mid) ret += query(rs, mid + 1, r, L, R);
        return ret;
    }
    void update(int rt, int l, int r, int L, int R, int v) {
        if (L <= l && r <= R) {
            tag[rt] = v, sum[rt] = (r - l + 1) * v;
            return;
        }
        pushDown(rt, l, r);
        if (L <= mid) update(ls, l, mid, L, R, v);
        if (R > mid) update(rs, mid + 1, r, L, R, v);
        pushUp(rt);
    }
}T[26];

char s[N];
int occurCnt[26];

int main() {
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int n, m; read(n), read(m);
    scanf("%s", s + 1);
    rep(i, 1, n) T[s[i] - 'a'].a[i] = 1;
    rep(i, 0, 25) T[i].build(1, 1, n);
    while (m--) {
        int l, r, oddCnt = 0, oddChar; read(l), read(r);
        rep(i, 0, 25) {
            occurCnt[i] = T[i].query(1, 1, n, l, r);
            if (occurCnt[i] & 1) oddCnt++, oddChar = i;
        }
        if ((r - l + 1) % 2 == 0 && oddCnt) continue;
        if ((r - l + 1) % 2 == 1 && oddCnt > 1) continue;
        rep(i, 0, 25) T[i].update(1, 1, n, l, r, 0);
        int cur = 0;
        rep(i, 0, 25) if (occurCnt[i]) {
            T[i].update(1, 1, n, l, l + occurCnt[i] / 2 - 1, 1);
            T[i].update(1, 1, n, r - occurCnt[i] / 2 + 1, r, 1);
            l += occurCnt[i] / 2, r -= occurCnt[i] / 2;
            if (occurCnt[i] & 1) T[i].update(1, 1, n, mid, mid, 1);
        }
    }
    rep(p, 1, n) rep(i, 0, 25) if (T[i].query(1, 1, n, p, p)) { putchar('a' + i); break; }
    return 0;
}

CodeForces - 240F TorCoder

原文：https://www.cnblogs.com/aziint/p/9482706.html