Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <string.h>
- using namespace std;
- struct node {
- int left,right,parent,next;
- bool hai,done;
- };
- int current;
- node tree[10000000]={0};
- int index1;
- int make_tree(int c,int current)
- {
- if (current-c<=1){index1=c;return 0;}
- int lenori(current);
- for (;c<lenori;c++)
- {
- if (tree[c].done==true)continue;
- if (c<lenori-1){
- tree[current].left=max(tree[c].left-tree[c+1].right,0)+tree[c+1].left;
- tree[current].right=max(0,tree[c+1].right-tree[c].left)+tree[c].right;
- tree[c].done=tree[c+1].done=true;
- tree[c].parent=tree[c+1].parent=current;
- tree[c].next=c+1;
- tree[c+1].next=c;
- }
- else
- {
- tree[current].left=tree[c].left;
- tree[current].right=tree[c].right;
- tree[c].parent=current;
- tree[c].next=c;
- }
- current++;
- }
- make_tree(lenori,current);
- return 0;
- }
- int update_tree(int index1)
- {
- swap(tree[index1].left,tree[index1].right);
- for (;tree[index1].parent!=0;index1=tree[index1].parent)
- {
- if (tree[index1].next<index1)
- {
- tree[tree[index1].parent].left=max(tree[tree[index1].next].left-tree[index1].right,0)+tree[index1].left;
- tree[tree[index1].parent].right=max(0,tree[index1].right-tree[tree[index1].next].left)+tree[tree[index1].next].right;
- }
- else
- {
- tree[tree[index1].parent].left=max(tree[index1].left+tree[index1+1].left-tree[index1+1].right,0);
- tree[tree[index1].parent].right=max(0,tree[index1].right+tree[index1+1].right-tree[index1].left);
- }
- }
- }
- int main()
- {
- for (int io(0);io<10;io++){
- memset(tree,0,sizeof(tree[0])*10000000);
- int dum;scanf("%d",&dum);
- char a[30001];
- scanf("%s",a);
- int n;
- scanf("%d",&n);
- for (int c(0);c<strlen(a);c++,current=c)
- {
- if (a[c]==')'){tree[c].right=1;tree[c].hai=true;}
- else {tree[c].left=1;tree[c].hai=true;}
- }
- make_tree(0,strlen(a));
- for (int c(0);c<n;c++)
- {
- int ab;
- scanf("%d",&ab);
- if (ab==0){if (tree[index1].left==tree[index1].right&&tree[index1].left==0)printf("YES\n") ; else printf("NO\n") ;}
- else
- {
- update_tree(ab-1);
- //print();
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement