题目链接:Codeforces 380C Sereja and Brackets
题目大意:给出一串括号,然后m次询问,问说a,b之间有多少个括号匹配。
解题思路:首先遍历一遍,将每个位置的从1到当前位置的有效右括号数和没有用到的左括号数记录下来;然后每次查询a,b区间,即为t = r[b] - r[a-1](有效右括号数),但是要注意,这些有效右括号的匹配左括号可能不在区间上,所以要减去l[a-1](未用到的左括号数),但是又有可能[1,a-1]中未用到的左括号和[b+1,len]中的右括号相匹配,所以要加上min(l[a~b]),这不用到线段树查询最小值。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1000005;
struct node {
int dl, dr, v;
}s[N*3];
int n, r[N], l[N], len;
char str[N];
int build (int x, int y, int f) {
s[f].dl = x, s[f].dr = y;
if (x == y) return s[f].v = l[x];
int mid = (x + y) / 2;
return s[f].v = min(build(x, mid, 2 * f), build(mid+1, y, 2*f+1));
}
int query(int x, int y, int f) {
if (x == s[f].dl && y == s[f].dr) return s[f].v;
int mid = (s[f].dl + s[f].dr) / 2;
if (mid >= x && mid < y) return min(query(x, mid, 2*f), query(mid+1, y, 2*f+1));
else if (mid >= x && mid >= y) return query(x, y, 2*f);
else return query(x, y, 2*f+1);
}
void solve () {
memset(r, 0, sizeof(r));
memset(l, 0, sizeof(l));
len = strlen(str);
int tmp = 0;
for (int i = 1; i <= len; i++) {
r[i] = r[i-1];
if (str[i-1] == '(') tmp++;
else if (tmp) {
r[i]++; tmp--;
}
l[i] = tmp;
}
build(1, len, 1);
}
int main () {
gets(str);
solve ();
int a, b;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &a, &b);
a = min(len, a); b = min(len, b);
printf("%d\n", (r[b] - r[a-1] - max(l[a-1] - query(a, b, 1), 0)) * 2);
}
return 0;
}
分享到:
相关推荐
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
这题如果没有输出2个解就很简单。 是个之前做过的类型: 把所有限制按R排序, 然后每次取出R最小的,然后从其L开始选,尽量选能选的中最小的。 这样选如果能选完,就说明有解。 贪心正确性显然:R大的至少可以选则R...
Codeforces 149 D-Coloring Brackets,动态规划求解
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
codeforces每日一练。 题意: 给一棵树,每个点有一个点权,每条边有一个边权,求一条链使得点权和-边权和最大。 思路: 由于我没看清楚题意,以为是求联通子图的点权和-边权和最大,用link-cut-tree写换根,wa10了两...
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
Codeforces round 678 D2_Codeforces_源码
打codeforces的神器
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
codeforces-js Codeforces JS
Codeforces Round #723 (Div. 2).md