CF Round #556 (Div.2)

B - Tiling Challenge

$n \times n$的地面有部分格子已经被占用了，问是否能用$+$形状的木板填满剩余部分。

C - Prefix Sum Primes

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

class Tree {
public:
class Node {
public:
int delta;
int mind, maxd;
int maxlm, maxmr, maxlmr;

static Node empty() { return {0, 0, 0, 0, 0, 0}; }
static Node character(char ch) {
if (ch == '(') {
return { 1,  0, 1, 0, 1, 1};
} else {
return {-1, -1, 0, 2, 1, 1};
}
}
Node shift(int d) const {
return {delta + d, mind + d,  maxd + d,
maxlm - d, maxmr - d, maxlmr};
}
static Node merge(const Node &l, const Node &r) {
Node shifted = r.shift(l.delta);
Node ret = empty();
ret.delta = shifted.delta;
ret.mind = min(l.mind, shifted.mind);
ret.maxd = max(l.maxd, shifted.maxd);
ret.maxlm = max({l.maxlm, shifted.maxlm, l.maxd - 2 * shifted.mind});
ret.maxmr = max({l.maxmr, shifted.maxmr, shifted.maxd - 2 * l.mind});
ret.maxlmr = max({
l.maxlmr, shifted.maxlmr,
l.maxlm + shifted.maxd, shifted.maxmr + l.maxd
});
return ret;
}
};

vector<Node> data;
int Base;

Tree (int N) : Base(1) {
while (Base < N + 1) { Base *= 2; }
data.resize(Base * 2, Node::empty());
}

void replace(int pos, char ch) {
pos += Base;
data[pos] = Node::character(ch);

do {
pos >>= 1;
data[pos] = Node::merge(data[pos << 1], data[pos << 1 | 1]);
} while (pos > 1);
}

int getAns() const {
return data[1].maxlmr;
}
};

int n, q;
string s;

int main() {
cin.sync_with_stdio(false);
cin.tie(NULL);

cin >> n >> q >> s;
--n;

Tree tree(n << 1);
for (int i = 0; i < (n << 1); ++i) {
tree.replace(i, s[i]);
}
cout << tree.getAns() << endl;

int u = 0, v = 0;
for (int i = 0; i < q; ++i) {
cin >> u >> v;
--u, --v;

swap(s[u], s[v]);
tree.replace(u, s[u]);
tree.replace(v, s[v]);

cout << tree.getAns() << endl;
}
}