线段树-Sereja and Brackets
题面翻译
- 本题中「合法括号串」的定义如下：
- 空串是「合法括号串」。
- 若 $s$ 是「合法括号串」，则 $(s)$ 是「合法括号串」。
- 若 $s,t$ 是「合法括号串」，则 $st$ 是「合法括号串」。
- 有一个括号串 $s$。$m$ 次操作。操作有一种：
l r：求字符串 $t=s_ls_{l+1}\cdots s_r$ 的所有 子序列 中，长度最长的「合法括号串」，输出长度即可。
- $1\le |s|\le 10^6$，$1\le m\le 10^5$。
题目描述
Sereja has a bracket sequence $ s_{1},s_{2},...,s_{n} $ , or, in other words, a string $ s $ of length $ n $ , consisting of characters "(" and ")".
Sereja needs to answer $ m $ queries, each of them is described by two integers $ l_{i},r_{i} $ $ (1<=l_{i}<=r_{i}<=n) $ . The answer to the $ i $ -th query is the length of the maximum correct bracket subsequence of sequence $ s_{li},s_{li}+1,...,s_{ri} $ . Help Sereja answer all queries.
You can find the definitions for a subsequence and a correct bracket sequence in the notes.
输入格式
The first line contains a sequence of characters $ s_{1},s_{2},...,s_{n} $ $ (1<=n<=10^{6}) $ without any spaces. Each character is either a "(" or a ")". The second line contains integer $ m $ $ (1<=m<=10^{5}) $ — the number of queries. Each of the next $ m $ lines contains a pair of integers. The $ i $ -th line contains integers $ l_{i},r_{i} $ $ (1<=l_{i}<=r_{i}<=n) $ — the description of the $ i $ -th query.
输出格式
Print the answer to each question on a single line. Print the answers in the order they go in the input.
样例 #1
样例输入 #1
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10
样例输出 #1
0
0
2
10
4
6
6
提示
A subsequence of length $ |x| $ of string $ s=s_{1}s_{2}...\ s_{|s|} $ (where $ |s| $ is the length of string $ s $ ) is string $ x=s_{k1}s_{k2}...\ s_{k|x|} $ $ (1<=k_{1}
A correct bracket sequence is a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.
For the third query required sequence will be «()».
For the fourth query required sequence will be «()(())(())».
思路
线段树：
区间未匹配到左括号和未匹配的右括号会产生贡献。
- sum:当前区间已经产生的贡献
- vl:左区间未匹配的左括号
- vr:右区间未匹配的右括号
合并后的总贡献为：$tr[l].sum+tr[r].sum+2min(tr[l].vl,tr[r].vr)$
代码
#include <bits/stdc++.h>
#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;
const int N = 1e6 + 10;
#define lc p<<1
#define rc p<<1|1
string s;
int n;
struct node {
int l, r;
int sum, vl, vr;
//sum为贡献，vl未匹配的左括号数量 rl为未匹配的右括号数量
} tr[N * 4];
void pushup(node &p, node &l, node &r) {
int t = min(l.vl, r.vr);
p.sum = l.sum + r.sum + 2 * t;
p.vl = l.vl + r.vl - t;
p.vr = l.vr + r.vr - t;
}
void pushup(int p) {
pushup(tr[p], tr[lc], tr[rc]);
}
void build(int p, int l, int r) {
tr[p] = {
l, r, 0, s[l] == '(', s[l] == ')'};
if (l == r) return;
int mid = (l + r) >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
pushup(p);
}
auto ask(int p, int l, int r) {
if (l <= tr[p].l and tr[p].r <= r) return tr[p];
int mid = (tr[p].l + tr[p].r) >> 1;
if (r <= mid) return ask(lc, l, r);
if (l > mid) return ask(rc, l, r);
node left = ask(lc, l, r), right = ask(rc, l, r);
node res = {
0, 0, 0, 0, 0};
pushup(res, left, right);
return res;
}
void solve() {
cin >> s;
n = s.size();
s = " " + s;
build(1, 1, n);
int m;
cin >> m;
while (m--) {
int l, r;
cin >> l >> r;
cout << ask(1, l, r).sum << endl;
}
}
signed main() {
IOS
#ifndef ONLINE_JUDGE
freopen("../test.in", "r", stdin);
freopen("../test.out", "w", stdout);
#endif
int _ = 1;
while (_--) solve();
return 0;
}
线段树-Xenia and Bit Operations
题面翻译
有$2^n$个数，有$m$个操作，每次修改一个数，然后你要输出$\ \ \ \ \ $( (a1|a2)xor(a3|a4) )|( (a5|a6)xor(a7|a8) )....
即$\ or\ \ \ xor\ $交替计算。
第一行两个数字$n,m$。
第二行$2^n$个数字。
下面$m$行，每行两个数字$x,y$，将第$x$个数字改为$y$。
保证$1\le n \le 17\ , \ 1\le m \le 10^5$，数字任意时刻满足$0\le y \le 2^{30}$
共$m$行，输出每次改完数字后上述表达式的值。
题目描述
Xenia the beginner programmer has a sequence $ a $ , consisting of $ 2^{n} $ non-negative integers: $ a_{1},a_{2},...,a_{2^{n}} $ . Xenia is currently studying bit operations. To better understand how they work, Xenia decided to calculate some value $ v $ for $ a $ .
Namely, it takes several iterations to calculate value $ v $ . At the first iteration, Xenia writes a new sequence $ a_{1} or a_{2},a_{3} or a_{4},...,a_{2^{n}-1} or a_{2^{n}} $ , consisting of $ 2^{n-1} $ elements. In other words, she writes down the bit-wise OR of adjacent elements of sequence $ a $ . At the second iteration, Xenia writes the bitwise exclusive OR of adjacent elements of the sequence obtained after the first iteration. At the third iteration Xenia writes the bitwise OR of the adjacent elements of the sequence obtained after the second iteration. And so on; the operations of bitwise exclusive OR and bitwise OR alternate. In the end, she obtains a sequence consisting of one element, and that element is $ v $ .
Let's consider an example. Suppose that sequence $ a=(1,2,3,4) $ . Then let's write down all the transformations $ (1,2,3,4) $ $ → $ $ (1 or 2=3,3 or 4=7) $ $ → $ $ (3 xor 7=4) $ . The result is $ v=4 $ .
You are given Xenia's initial sequence. But to calculate value $ v $ for a given sequence would be too easy, so you are given additional $ m $ queries. Each query is a pair of integers $ p,b $ . Query $ p,b $ means that you need to perform the assignment $ a_{p}=b $ . After each query, you need to print the new value $ v $ for the new sequence $ a $ .
输入格式
The first line contains two integers $ n $ and $ m $ $ (1<=n<=17,1<=m<=10^{5}) $ . The next line contains $ 2^{n} $ integers $ a_{1},a_{2},...,a_{2^{n}} $ $ (0<=a_{i}<2^{30}) $ . Each of the next $ m $ lines contains queries. The $ i $ -th line contains integers $ p_{i},b_{i} $ $ (1<=p_{i}<=2^{n},0<=b_{i}<2^{30}) $ — the $ i $ -th query.
输出格式
Print $ m $ integers — the $ i $ -th integer denotes value $ v $ for sequence $ a $ after the $ i $ -th query.
样例 #1
样例输入 #1
2 4
1 6 3 5
1 4
3 4
1 2
1 2
样例输出 #1
1
3
3
3
提示
For more information on the bit operations, you can follow this link: http://en.wikipedia.org/wiki/Bitwise\_operation
思路
线段树：
因为这个线段树要维护的节点为$2^n$个，因此他一定是一颗完全二叉树
1 [1-16]
/ \
2 [1-8] 3 [9-16]
/ \ / \
4 [1-4] 5 [5-8] 6 [9-12] 7 [13-16]
/ \ / \ / \ / \
8[1-2] 9[3-4] 10[5-6] 11[7-8] 12[9-10] 13[11-12]
/ \ / \ / \ / \ / \
14 15 16 17 18 19 20 21 22 23 24 25 26 27
最下面的一层不用管，因为l==r的时候会return
然后从倒数第二层开始，记录每层的层数，显然是一层执行或运算，一层执行与运算
代码
#include <bits/stdc++.h>
#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;
const int N = (1 << 18) + 10;
#define lc p<<1
#define rc p<<1|1
struct node {
int l, r, value;
} tr[N * 4];
int a[N], deep[N];
void pushup(int p) {
if (deep[p] & 1) tr[p].value = tr[lc].value | tr[rc].value;
else tr[p].value = tr[lc].value ^ tr[rc].value;
}
void build(int p, int l, int r) {
tr[p] = {
l, r, a[l]};
if (l == r) return;
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
deep[p] = deep[lc] + 1;
pushup(p);
}
void update(int p, int pos, int k) {
if (tr[p].l == pos && tr[p].r == pos) {
tr[p].value = k;
return;
}
int mid = (tr[p].l + tr[p].r) >> 1;
if (pos <= mid) update(lc, pos, k);
else update(rc, pos, k);
pushup(p);
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= (1 << n); i++) cin >> a[i];
build(1, 1, 1 << n);
while (m--) {
int x, y;
cin >> x >> y;
update(1, x, y);
cout << tr[1].value << endl;
}
}
signed main() {
IOS
#ifndef ONLINE_JUDGE
freopen("../test.in", "r", stdin);
freopen("../test.out", "w", stdout);
#endif
int _ = 1;
while (_--) solve();
return 0;
}
