티스토리 뷰
반응형
solved.ac 티어 : 플래 2
17407번: 괄호 문자열과 쿼리
괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이
www.acmicpc.net
이문제는 딱 봐도 버거운 버거랑 비슷한 문제이다.
버거운 버거를 풀고 오면 거저로 얻는 문제이다.
버거운 버거:joseph0528.tistory.com/8
BOJ 19851(버거운 버거)풀이
세그 레이지를 이용했습니다. solved.ac 티어 : 다이아 5 www.acmicpc.net/problem/19851 19851번: 버거운 버거 드디어 산업기능요원 복무를 마친 키파는 버거운 직장에서 벗어나 새로운 직업에 도전하고자 햄
joseph0528.tistory.com
버거운 버거에서 변경을 index[i]부터 index[i]으로 바꿔놓고 바로 밑에 전체 구간을 돌려서 추가해야 되는 괄호 개수를 더했을 때 0이면 올바른 괄호 문자열이므로 cnt++를 해주면 끝이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nod{
ll l1,r1,l2,r2;
};
vector<ll>l(100001);
nod tree[410000];
vector<ll>lazytree(410000);
ll a;
void seg(ll n,ll s,ll e){
if(s==e){ // 왼쪽 괄호일경우 남는 왼쪽괄호에 1 오른쪽에 0과 반전한 0,1로 해놓고 오른쪽괄호일경우 0 1 1 0으로 하면된다.
if(l[s]==1){tree[n]={1,0,0,1};return;}
else{tree[n]={0,1,1,0};return;}
}
seg(n*2,s,(s+e)/2);
seg(n*2+1,(s+e)/2+1,e);
tree[n]={0,0,0,0};
//두개의 구간에서 왼쪽 구간에서의 남는 (의 개수와 오른쪽 구간에서의 남는 )의 개수를 비교해서 (의 개수가 더 크면 두 수의 차만큼 지금위치 배열의 (위치에 넣고 )의 개수가 더 크면 두수의 차만큼 지금위치 배열의 )위치에 값을 넣는다.
if(tree[n*2].l1>tree[n*2+1].r1){tree[n].l1=tree[n*2].l1-tree[n*2+1].r1;}
else{tree[n].r1=tree[n*2+1].r1-tree[n*2].l1;}
// 오른쪽 구간에서의 왼쪽값을 지금위치 배열의 왼쪽에 넣어주고 왼쪽 구간에서의 오른쪽값을 지금위치 배열의 오른쪽에 넣어준다.
tree[n].l1+=tree[n*2+1].l1;
tree[n].r1+=tree[n*2].r1;
// 위랑 같은 방식은 반전 구간에도 적용해준다.
if(tree[n*2].l2>tree[n*2+1].r2){tree[n].l2=tree[n*2].l2-tree[n*2+1].r2;}
else{tree[n].r2=tree[n*2+1].r2-tree[n*2].l2;}
tree[n].l2+=tree[n*2+1].l2;
tree[n].r2+=tree[n*2].r2;
}
void propagate(ll n,ll s,ll e){
if(lazytree[n]!=0){
if(s!=e){
lazytree[n*2]+=1;
lazytree[n*2+1]+=1;
lazytree[n*2]%=2;
lazytree[n*2+1]%=2;
//트리를 1또는 0으로 바꿔준다.
}
ll io=tree[n].l1,ii=tree[n].r1;
tree[n].l1=tree[n].l2;
tree[n].r1=tree[n].r2;
tree[n].l2=io;
tree[n].r2=ii;
lazytree[n]=0;
}
}
nod sumax(ll n,ll s,ll e,ll left,ll right){
propagate(n,s,e);
if(left>e||right<s){return{0,0,0,0};}
if(left<=s&&e<=right){return tree[n];}
nod le=sumax(n*2,s,(s+e)/2,left,right);
nod ri=sumax(n*2+1,(s+e)/2+1,e,left,right);
nod c;
c={0,0,0,0};
// 여기도 세그트리를 만들때 처럼 해준다.
if(le.l1>ri.r1){c.l1=le.l1-ri.r1;}
else{c.r1=ri.r1-le.l1;}
c.l1+=ri.l1;
c.r1+=le.r1;
if(le.l2>ri.r2){c.l2=le.l2-ri.r2;}
else{c.r2=ri.r2-le.l2;}
c.l2+=ri.l2;
c.r2+=le.r2;
return c;
}
void change(ll n,ll s,ll e,ll s1,ll e1){
propagate(n,s,e);
if(s1<=s&&e<=e1){
lazytree[n]=1;
propagate(n,s,e);return;}
if(e1<s||s1>e){return;}
change(n*2,s,(s+e)/2,s1,e1);
change(n*2+1,(s+e)/2+1,e,s1,e1);
tree[n]={0,0,0,0};
// 여기도 세그트리를 만들때 처럼 해준다.
if(tree[n*2].l1>tree[n*2+1].r1){tree[n].l1=tree[n*2].l1-tree[n*2+1].r1;}
else{tree[n].r1=tree[n*2+1].r1-tree[n*2].l1;}
tree[n].l1+=tree[n*2+1].l1;
tree[n].r1+=tree[n*2].r1;
if(tree[n*2].l2>tree[n*2+1].r2){tree[n].l2=tree[n*2].l2-tree[n*2+1].r2;}
else{tree[n].r2=tree[n*2+1].r2-tree[n*2].l2;}
tree[n].l2+=tree[n*2+1].l2;
tree[n].r2+=tree[n*2].r2;
}
int main()
{
ll b,c,d,q,k,gh,gk,cnt=0;
scanf("%lld",&a);
int i;
char yu[1000005];
scanf("%s",yu);
a=strlen(yu);
for(i=0;i<a;i++){
if(yu[i]=='('){l[i]=1;}
else{l[i]=-1;}
}
seg(1,0,a-1);
scanf("%lld",&b);
for(i=0;i<b;i++){
scanf("%lld",&q);
change(1,0,a-1,q-1,q-1);
nod cn=sumax(1,0,a-1,0,a-1);
if(cn.l1+cn.r1==0){cnt++;}
}
printf("%lld\n",cnt);
}
반응형
'ps' 카테고리의 다른 글
BOJ 2352(반도체 설계)풀이 (0) | 2021.01.23 |
---|---|
BOJ 20052(괄호 문자열 ?)풀이 (0) | 2021.01.22 |
BOJ 11670(초등 수학) 풀이 (0) | 2021.01.19 |
BOJ 8895(막대 배치) 풀이 (0) | 2021.01.18 |
BOJ 7894(큰 수)풀이 (0) | 2021.01.17 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 완전 탐색
- 알고리즘
- 자료구조
- 이분매칭
- Python
- 깊이 우선 탐색
- 트리
- 자료 구조
- discord bot
- KOI
- 그리디 알고리즘
- 느리게 갱신되는 세그먼트 트리
- 세그먼트 트리
- 선분 교차 판정
- 트리에서의 다이나믹 프로그래밍
- 잡봇
- 정렬
- 구현
- C++
- 그래프 탐색
- 수학
- BOJ
- 최소 스패닝 트리
- 이분 탐색
- A Dance of Fire and Ice
- 누적 합
- 그래프 이론
- codeforces
- 다이나믹 프로그래밍
- 개발
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함