CF380C Sereja and Brackets
2022/4/3 23:19:29
本文主要是介绍CF380C Sereja and Brackets,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
洛谷题面
线段树模板题。
题目分析
给定一个括号串和 \(m\) 次操作,每次操作求区间 \([l,r]\) 内最长合法括号子序列的长度。
题目分析
我们可以在普通线段树上再记录两个变量 \(lnum,rnum\),分别表示区间内未匹配的左括号的数量和未匹配的右括号的数量。
于是有:
inline void pushup(int p) { node[p].lnum = node[lson].lnum + node[rson].lnum - min(node[lson].lnum,node[rson].rnum); node[p].rnum = node[lson].rnum + node[rson].rnum - min(node[lson].lnum,node[rson].rnum); }
对于左括号的统计:
设一非叶子节点为 \(p\),其左儿子为 \(ls\),右儿子为 \(rs\),那么 \(lnum_p=lnum_{ls}+lnum_{rs}\),但是我们会发现,如果两个区间合并到一起,这两个区间中没有合并成功的括号可能会再次合并成功。
举个例子:\(ls\) 代表的区间子串为 ()((
,\(rs\) 代表的区间子串为 ))()
,那么两个区间合并在一起后会变成 ()(())()
,会发现此时没有匹配失败的括号了,所以我们应该再减去能够匹配的括号数,显然只要有两个不同方向的括号就能匹配成功,所以应减去 \(\min\{lnum_{ls},rnum_{rs}\}\)。
右括号的统计同理。
代码
//2022/2/12 //2022/4/3 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <climits>//need "INT_MAX","INT_MIN" #include <cstring>//need "memset" #include <numeric> #include <algorithm> #define enter putchar(10) #define debug(c,que) cerr << #c << " = " << c << que #define cek(c) puts(c) #define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) cout << arr[i] << w; #define speed_up() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define mst(a,k) memset(a,k,sizeof(a)) #define Abs(x) ((x) > 0 ? (x) : -(x)) #define stop return(0) const int mod = 1e9 + 7; inline int MOD(int x) { if(x < 0) x += mod; return x % mod; } namespace Newstd { char buf[1 << 21],*p1 = buf,*p2 = buf; inline int getc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1 ++; } inline int read() { int ret = 0,f = 0;char ch = getc(); while (!isdigit(ch)) { if(ch == '-') f = 1; ch = getc(); } while (isdigit(ch)) { ret = (ret << 3) + (ret << 1) + ch - 48; ch = getc(); } return f ? -ret : ret; } inline void write(int x) { if(x < 0) { putchar('-'); x = -x; } if(x > 9) write(x / 10); putchar(x % 10 + '0'); } } using namespace Newstd; using namespace std; const int N = 1e6 + 5; char str[N]; int n,m; struct Segment_Tree { struct Node { int l,r; int lnum,rnum; //lnum:左括号多余的数量,rnum:有括号多余的数量 } node[N << 2]; #define lson (p << 1) #define rson (p << 1 | 1) inline void pushup(int p) { node[p].lnum = node[lson].lnum + node[rson].lnum - min(node[lson].lnum,node[rson].rnum); node[p].rnum = node[lson].rnum + node[rson].rnum - min(node[lson].lnum,node[rson].rnum); } inline void build(int p,int l,int r) { node[p].l = l,node[p].r = r; if (l == r) { if (str[l] == '(') { node[p].lnum = 1,node[p].rnum = 0; } else { node[p].lnum = 0,node[p].rnum = 1; } return; } int mid = l + r >> 1; build(lson,l,mid),build(rson,mid + 1,r); pushup(p); } inline Node query(int x,int y,int p) { if (x <= node[p].l && node[p].r <= y) { return node[p]; } int mid = node[p].l + node[p].r >> 1; if (x <= mid && mid < y) { Node lans = query(x,y,lson),rans = query(x,y,rson),ans; ans.lnum = lans.lnum + rans.lnum - min(lans.lnum,rans.rnum); ans.rnum = lans.rnum + rans.rnum - min(lans.lnum,rans.rnum); return ans; } if (x <= mid) return query(x,y,lson); if (y > mid) return query(x,y,rson); } inline int getans(int l,int r) { Node ans = query(l,r,1); return r - l + 1 - ans.lnum - ans.rnum; } #undef lson #undef rson } seg; int main(void) { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif cin >> str + 1 >> m; n = strlen(str + 1); seg.build(1,1,n); while (m -- ) { int l,r; cin >> l >> r; cout << seg.getans(l,r) << "\n"; } return 0; }
这篇关于CF380C Sereja and Brackets的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验