给定一个括号序列,每次交换两个括号并询问当前括号序列对应的树的直径。N, Q \leq 10^5

这题可以不用维护树的形态而是直接利用线段树维护括号序列直接求出树的直径。

考虑一个比较暴力的维护方法,给定每个左括号的权值为 1,右括号的权值为 -1。那么一堆可以匹配的括号的权值和等于 0

对于一条直径,先考虑一个朴素的情况:

((((((((((((((()))))))))))))((((((((()))))))))))
| |           L            ||       R        | |
               |     A     ||   B   |

LR 构成的直径长度,可以由区间 A 的和的相反值加上区间 B 的和得到。

如果在其中加入一些分支但并不选择的话,他们对答案的贡献显然为 0

\displaystyle{s_n = \sum_{i=1}^n} a_i ,那么题意转化为求 \displaystyle{\max_{0 \leq i \leq j \leq k \leq n} (s_i + s_k - 2 s_j)}。考虑放到线段树上,每个线段只处理 L \leq i \leq j \leq k \leq R 的情况,这里把 s_i 重新定义为 \displaystyle{s_n = \sum_{i=L}^n a_i} 显然对答案并没有影响,然后分类讨论。

定义 \displaystyle{M = \frac {L + R} 2},考虑可能对答案产生贡献的情况:

  1. L \leq i \leq j \leq k \leq M \Rightarrow 直接取左孩子的答案
  2. M < i \leq j \leq k \leq R \Rightarrow 直接取右孩子的答案
  3. L \leq i \leq j \leq M < k \leq R 左边维护 \displaystyle{\max_{L \leq i \leq j \leq M}} s_i - 2 s_j 然后和右边的最大值合并
  4. L \leq i \leq M < j \leq k \leq R 右边维护 \displaystyle{\max_{M < j \leq k \leq R}} s_k - 2 s_j 然后和左边的最大值合并。

\displaystyle{\max_{L \leq i \leq j \leq M}} s_i - 2 s_j\displaystyle{\max_{M < j \leq k \leq R}} s_k - 2 s_j 可以用类似的方法分配给左右孩子维护。

这样就巧妙利用了线段树的性质保证了 i, j, k 的位置关系。

代码:

// =================================
//   author: memset0
//   date: 2019.04.30 14:25:19
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define debug(...) ((void)0)
#ifndef debug
#define debug(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace ringo {
template <class T> inline void read(T &x) {
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 2e5 + 10;
int n, m;
char s[N];

#define U p[u]
#define L p[u << 1]
#define R p[u << 1 | 1]
struct node {
    int l, r, mid;
    int sum, ans, max, min, max1, max2;
    inline void init(int k, int w) {
        sum = w == '(' ? 1 : -1;
        max = min = sum;
        max1 = max2 = -sum;
        ans = -1e9;
    }
} p[N << 2];
// a, b, c => max(s_a + s_c - 2 s_b)

inline void maintain(int u) {
    U.sum = L.sum + R.sum;
    U.max = std::max(L.max, L.sum + R.max);
    U.min = std::min(L.min, L.sum + R.min);
    U.max1 = std::max(std::max(L.max1, R.max1 - L.sum), L.max - ((R.min + L.sum) << 1));
    U.max2 = std::max(std::max(L.max2, R.max2 - L.sum), R.max + L.sum - (L.min << 1));
    U.ans = std::max(std::max(L.ans, R.ans), std::max(L.max1 + R.max + L.sum, R.max2 - L.sum + L.max));
}

void build(int u, int l, int r) {
    p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
    if (l == r) return p[u].init(l, s[l]);
    build(u << 1, l, p[u].mid);
    build(u << 1 | 1, p[u].mid + 1, r);
    maintain(u);
}

void modify(int u, int k, int w) {
    if (p[u].l == p[u].r) return p[u].init(k, w);
    modify(k <= p[u].mid ? u << 1 : u << 1 | 1, k, w);
    maintain(u);
}

void main() {
    read(n), read(m), scanf("%s", s + 1);
    build(1, 1, (n - 1) << 1);
    print(p[1].ans, '\n');
    for (int l, r, i = 1; i <= m; i++) {
        read(l), read(r), std::swap(s[l], s[r]);
        modify(1, l, s[l]);
        modify(1, r, s[r]);
        // for (int i = 1; i <= (n - 1) << 1; i++)
        //  putchar(s[i]);
        // putchar('\n');
        print(p[1].ans, '\n');
    }
}

} signed main() {
#ifdef MEMSET0_LOCAL_ENVIRONMENT
    freopen("1.in", "r", stdin);
#endif
    return ringo::main(), 0;
}

巧妙的思路 线段树 括号序列

CF1149D Abandoning Roads
上一篇 «
好看的颜文字收藏夹
» 下一篇