简要题意
给定长度为 $n$ 的仅含有小括号和中括号的括号序列.
规定花费 $0$ 的代价改变括号方向, 花费 $1$ 的代价变换括号种类. 有 $m$ 次询问, 每次询问区间 $[l,r]$ 的子串至少需要花费多少的代价才能使括号序列合法.
多组数据.
$t \leqslant 100, n \leqslant 10^6, \sum{n} \leqslant 10^6,q \leqslant 2 \times 10^5 ,\sum{q} \leqslant 2 \times 10^5$ .
题解
因为同种括号变换花费为 $0$ , 所以可以考虑把所有括号全部变为中括号, 再看有哪些括号本是不必要变的.
再考虑到一对合法的括号, 必然一个在奇数位上, 一个在偶数位上.
我们把在奇数位上的设为 $1$ , 偶数位上的设为 $-1$ , 做前缀和, 求解时答案为 $sum_r-sum_{l-1}$ .
考虑这样为什么是对的, 一对合法的括号匹配相加会抵消掉, 剩下没被抵消的就是需要变换种类的.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
#define DEBUG(x) cout << #x << " = " << x << endl
template <typename T>
inline bool read(T &x) {
int f = 1,c = getchar();x = 0;
while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
return read(x) && read(args...);
}
namespace run {
const int maxn = 1e6+10;
int a[maxn];
char str[maxn];
int n,m;
inline void main() {
scanf("%s",str+1);
n = strlen(str+1);
read(m);
for (register int i = 1;i <= n;++i) {
a[i] = a[i-1];
if (str[i] == '(' || str[i] == ')')a[i] += i&1 ? 1 : -1;
}
for (register int i = 1,l,r;i <= m;++i) {
read(l,r);
printf("%d\n",abs(a[r]-a[l-1]));
}
cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return;
}
}
#define demonlover
int main() {
#ifdef demonlover
freopen("CF1593G.in","r",stdin);
freopen("CF1593G.out","w",stdout);
#endif
int T;read(T);
while (T--)run :: main();
return 0;
}
|