CF240F (26颗线段树计数)

题目链接：Topcoder----洛谷

题目大意：

　　给定一个长为n的由a到z组成的字符串,有m次操作，每次操作将[l,r]这些位置的字符进行重排，得到字典序最小的回文字符串，如果无法操作就不进行。

思路：

　　用26颗线段树分别统计在每个位置上是否有对应的字母

　　每次操作：

　　　　1.有出现次数为奇数的字母：

　　　　　　大于1，不可能回文，无法操作。

　　　　　　等于1，放到中间

　　　　2.全是偶数次数：

　　　　　　分别放两端

  1 # include<bits/stdc++.h>

  2 using namespace std;

  3 #define endl "\n"

  4 # define int long long

  5 # define ls u<<1

  6 # define rs u<<1|1

  7 const int N = 1e5 + 10;

  8 char a[N], p;

  9 int n, m;

 10 struct segtree {

 11     int sum[4 * N], lazy[4 * N];

 12     void pushup(int u) {

 13         sum[u] = (sum[ls] + sum[rs]);

 14     }

 15

 16     void build(int tr, int u, int l, int r) {

 17         lazy[u] = -1;

 18         if (l == r) {

 19             sum[u] = ((a[l] - 'a' ) == tr);

 20             return;

 21         }

 22         int mid = l + r >> 1;

 23         build(tr, ls, l, mid);

 24         build(tr, rs, mid + 1, r);

 25         pushup(u);

 26     }

 27

 28     void pushdown(int u, int l, int r) {

 29         int mid = l + r >> 1;

 30         if (lazy[u] != -1) {

 31             sum[ls] = (mid - l + 1) * lazy[u];

 32             sum[rs] = (r - mid) * lazy[u];

 33

 34             lazy[ls] = lazy[u];

 35             lazy[rs] = lazy[u];

 36             lazy[u] = -1;

 37         }

 38

 39     }

 40

 41     void modify(int u, int l, int r, int L, int R, int c) {

 42         if (l > r || l > R || r < L) return;

 43         if (L <= l && r <= R) {

 44             sum[u] = (r - l + 1) * c;

 45             lazy[u] = c;

 46             return;

 47         }

 48         int mid = l + r >> 1;

 49         pushdown(u, l, r);

 50         if (L <= mid) modify(ls, l, mid, L, R, c);

 51         if (mid + 1 <= R) modify(rs, mid + 1, r, L, R, c);

 52         pushup(u);

 53     }

 54

 55     int query(int u, int l, int r, int L, int R) {

 56         if (l > r || l > R || r < L) return 0;

 57         if (l >= L && r <= R) {

 58             return sum[u];

 59         }

 60         pushdown(u, l, r);

 61         int mid = l + r >> 1;

 62         int ans = 0;

 63         if (L <= mid) ans += query(ls, l, mid, L, R);

 64         if (R > mid) ans += query(rs, mid + 1, r, L, R);

 65         return ans;

 66     }

 67 } tr[26];

 68

 69 signed main() {

 70     ios::sync_with_stdio(false);

 71     cin.tie(0);

 72     cout.tie(0);

 73     freopen("input.txt", "r", stdin);

 74     freopen("output.txt", "w", stdout);

 75     cin >> n >> m;

 76     string s;

 77     cin >> s;

 78     for (int i = 1; i <= n; ++i) a[i] = s[i - 1];

 79     for (int i = 0; i < 26; ++i) tr[i].build(i, 1, 1, n);

 80     for (int t = 1; t <= m; ++t) {

 81         int l, r;

 82         cin >> l >> r;

 83         int odd = 0;

 84         int tmp[26] = {0}, key;

 85         for (int i = 0; i < 26; ++i) tmp[i] = tr[i].query(1, 1, n, l, r);//记录在区间[l,r]中每个字母出现的次数

 86         for (int i = 0; i < 26; ++i) if (tmp[i] & 1) odd++, key = i;

 87         if (odd > 1) continue;

 88         for (int i = 0; i < 26; ++i) tr[i].modify(1, 1, n, l, r, 0);

 89         if (odd) {

 90             --tmp[key];

 91             tr[key].modify(1, 1, n, (l + r) / 2, (l + r) / 2, 1);//奇数置中

 92         }

 93         int nl = l, nr = r;

 94         for (int i = 0; i < 26; ++i) {//偶数分两边放

 95             if (tmp[i]) {

 96                 tr[i].modify(1, 1, n, nl, nl + tmp[i] / 2 - 1, 1);

 97                 nl += tmp[i] / 2;

 98                 tr[i].modify(1, 1, n, nr - tmp[i] / 2 + 1, nr, 1);

 99                 nr -= tmp[i] / 2;

100             }

101         }

102     }

103     for (int i = 1; i <= n; ++i) {

104         for (int j = 0; j < 26; ++j) {

105             if (tr[j].query(1, 1, n, i, i)) {

106                 cout << (char)(j + 'a');

107             }

108         }

109     }

110     return 0;

111 }

巴特西

CF240F (26颗线段树计数)

最新文章

热门文章