【20.95%】【UESTC 94】Bracket Squence
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Status
There is a sequence of brackets, which supports two kinds of operations.
- we can choose a interval [l,r][l,r],
and set all the elements range in this interval to left bracket or right bracket. - we can reverse a interval, which means that for all the elements range in [l,r][l,r],
if it's left bracket at that time, we change it into right bracket, vice versa.
Fish is fond of Regular Bracket
, so he want to know whether a interval [l,r][l,r] of
Sequence
the sequence is regular or not after doing some operations.
Let us define a regular brackets sequence in the following way:
- Empty sequence is a regular sequence.
- If
S
is a regular sequence, then(S)
is
also a regular sequences. - If
A
andB
are
regular sequences, thenAB
is a regular sequence.
Input
In the first line there is an integer TT (T≤10T≤10),
indicates the number of test cases. Each case begins with a line containing an integers NN (N≤100,000N≤100,000 and NN is
a even number), the size of the initial brackets sequence. The next line contains a string whose length is NN consisting
of (
and )
.
In the third of each test case, there is an integer MM(M≤100,000M≤100,000)
indicates the number of queries. Each of the following MM lines
contains one operation as mentioned below. The index of the bracket sequence is labeled from 00to N−1N−1.
Three operation description:
set l r c
: change all the elements range in [l,r][l,r] into(
or)
.(cc is(
or)
)reverse l r
: reverse the interval [l,r][l,r]query l,r
: you should answer that interval [l,r][l,r] is
regular or not
Output
For each test case, print a line containing the test case number (beginning with 11)
on its own line, then the answer for each query
operation, if the interval
is regular, print YES
, otherwise print NO
,
one on each line.
Print a blank line after each test case.
Sample input and output
Sample Input | Sample Output |
---|---|
1 |
Case 1: |
Hint
Huge input, use scanf
instead
of cin
.
Source
【题解】
给你一段括号序列。
1.set操作 把[l,r]区间内的所有括号都置为相同的括号;
2.reverse操作 把[l,r]区间内的所有括号都置为相反。
3.询问操作。询问[l,r]这个区间的括号是否匹配了。
要用到栈的思想。
左括号是加1,右括号是减1.
累加器一开始为0;
当我们从左往右判断括号是否匹配的时候,就按照这个规则给累加器累加值。如果中间某个时刻累加的值小于0了。那就说明不匹配。因为右括号在某个时刻比前面的所有左括号的数目都多。这个时候就算最后的累加器值为0也没用。
用线段树来做。(一开始就把括号序列按照括号和数字对应的规则改成1,-1序列)
我们要记录某段区间内的累加值sum,还要记录这段区间从左往右一直按顺序逐个累加出现的最小值minlx。
当输入的询问l,r。满足sum[l..r]==0,且minlx[l..r]>=0,则这段是匹配的。
如果是单纯的整个区间的替换操作。sum值是比较好维护的。就是区间长度乘替换值。
从左到右按顺序累加值的最小值也可以根据替换的值的正负得出。是正就取1个,是反就取区间长度的个数。
但是如果要进行取反操作该怎么办呢??
可以动手实验一下。
设未取反之前,从左到右按顺序累加出现过的最大值和最小值为max,min
取反过后的则是max',min'
则满足max'=-min,min'=-max;
可以这样想。
max->a0+a1+a2+a3..+ax;
min'->-a0-a1-a2-a3..-ax;
因为max是从左往右加最大的。
那么取一个相反数。那么就变成从左往右加最小的了。
如果再加上一个a(x+1);
那么max值不会比原来大。
那么相应的-max也就不会比原来小了;
少掉最后一个元素ax也是同理,max值不会比原来大,对应-max也就不会比原来小了。
综上直接取-max就好了。
max'从min推出的原理也可以这样用类似方法想。
然后你只要知道set操作是可以覆盖取反操作就可以了。即不论你之前怎样取反。我都直接给你浇一桶冷水全部变成某个值。
在push_up的时候,你要明确,maxlx,minlx这两个值都是从区间的最左端不断往右加到一个合适的位置得到的。
这点在最后输出询问的时候也用到了。
每个测试点后面要多输出一个空行。你看到了吗?
另外我的代码在输入数据的时候把区间左右端点都加了1。这样整个区间就是[1..n]了。
【代码】
#include <cstdio>
#include <algorithm>
#define lson begin,m,rt<<1
#define rson m+1,end,rt<<1|1 using namespace std; const int MAXN = 100101; int n,m,a[MAXN],maxlx[MAXN*4],minlx[MAXN*4],sum[MAXN*4];
int af[MAXN * 4], as[MAXN * 4];
char s[MAXN]; void push_up(int rt)//想理解max和min的更新需要明确这两个值是从左往右一直累加到一个合适位置获得的
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
maxlx[rt] = max(maxlx[rt << 1], sum[rt << 1] + maxlx[rt << 1 | 1]);
minlx[rt] = min(minlx[rt << 1], sum[rt << 1] + minlx[rt << 1 | 1]);
} void build(int begin, int end, int rt)//建树。
{
as[rt] = 0;
af[rt] = 0;
maxlx[rt] = minlx[rt] = sum[rt] = 0;
if (begin == end)
{
maxlx[rt] = minlx[rt] = sum[rt] = a[begin];
return;
}
int m = (begin + end) >> 1;
build(lson);
build(rson);
push_up(rt);
} void input_data()
{
scanf("%d", &n);
scanf("%s", s);
for (int i = 1; i <= n; i++)
if (s[i-1] == '(')
a[i] = 1;
else
a[i] = -1;
build(1, n, 1);
scanf("%d", &m);
} void qufan(int &t)
{
if (t == 1)
t = -1;
else
t = 1;
} void tihuan(int rt,int len,int num)
{
sum[rt] = len*num;
if (num == 1)
{
maxlx[rt] = len;
minlx[rt] = 1;
}
else
{
maxlx[rt] = -1;
minlx[rt] = -len;
}
} void push_down(int rt,int len)
{
if (as[rt] != 0) //需要替换
{
as[rt << 1] = as[rt << 1 | 1] = as[rt];
af[rt << 1] = af[rt << 1 | 1] = 0; sum[rt << 1] = (len - (len >> 1))*as[rt];
tihuan(rt << 1, (len - (len >> 1)), as[rt]); sum[rt << 1 | 1] = (len >> 1)*as[rt];
tihuan(rt << 1 | 1, len >> 1, as[rt]); as[rt] = 0;
}
else //如果存在替换操作就不可能存在取反操作(可以想想为什么);
if (af[rt] != 0)
{
if (as[rt << 1] != 0)
{
qufan(as[rt << 1]);
tihuan(rt<<1, (len-(len>>1)), as[rt<<1]);
}
else
{
af[rt<<1] = 1 - af[rt<<1];
sum[rt<<1] = -sum[rt<<1];
int temp = maxlx[rt<<1];
maxlx[rt<<1] = -minlx[rt<<1];
minlx[rt<<1] = -temp;
} if (as[rt << 1|1] != 0)
{
qufan(as[rt << 1|1]);
tihuan(rt << 1|1,len >> 1, as[rt << 1|1]);
}
else
{
af[rt << 1|1] = 1 - af[rt << 1|1];
sum[rt << 1|1] = -sum[rt << 1|1];
int temp = maxlx[rt << 1|1];
maxlx[rt << 1|1] = -minlx[rt << 1|1];
minlx[rt << 1|1] = -temp;
}
af[rt] = 0;
}
} void up_data(int op, int l, int r, int num, int begin, int end, int rt)
{
if (l <= begin && end <= r)
{
if (op == 1) //all the same
{
tihuan(rt, end - begin + 1, num);
as[rt] = num;
af[rt] = 0;
}
else
if (op == 2) //all "fan"(pinyin)
{
if (as[rt] != 0)//如果之前有替换操作 就把替换的值取反就可以了
{
qufan(as[rt]);
tihuan(rt, end - begin + 1, as[rt]);
}
else
{
af[rt] = 1 - af[rt];
sum[rt] = -sum[rt];
int temp = maxlx[rt];
maxlx[rt] = -minlx[rt];
minlx[rt] = -temp;
}
}
return;
}
push_down(rt,end-begin+1);
int m = (begin + end) >> 1;
if (l <= m)
up_data(op, l, r, num, lson);
if (m < r)
up_data(op, l, r, num, rson);
push_up(rt);
} int query_sum(int l, int r, int begin, int end, int rt)//求l..r的区间和。
{
if (l <= begin && end <= r)
return sum[rt];
push_down(rt,end-begin+1);
int m = (begin + end) >> 1;
int dd = 0;
if (l <= m)
dd += query_sum(l, r, lson);
if (m < r)
dd += query_sum(l, r, rson);
return dd;
} int query_min(int l, int r, int begin, int end, int rt) //求得l..r这个区间从最左往右加出现过的最小值。
{
if (l == begin && r == end)
return minlx[rt];
push_down(rt, end - begin + 1);
int m = (begin + end) >> 1;
if (r <= m)//所求区间在这个端点所代表的区间的左边。
return query_min(l, r, lson);
else
if (m + 1 <= l)
return query_min(l, r, rson);
else //明确min的值是从最左往右加到一个合适的位置的。知道了之后就不难理解。
return min(query_min(l, m, lson), query_sum(l, m, lson) + query_min(m + 1, r, rson));
//min里面的前者相当于不管右区间了。直接求左区间的minlx
//后者则是认为从左区间一直累加到右区间了
} void get_ans()
{
for (int i = 1; i <= m; i++)
{
char op[10];
scanf("%s", op);
int x, y;
char key[5];
if (op[0] == 's')
{
scanf("%d%d%s", &x, &y, key);
x++; y++;
int temp;
if (key[0] == '(')
temp = 1;
else
temp = -1;
up_data(1, x, y, temp, 1, n, 1);
}
else
if (op[0] == 'r')
{
scanf("%d%d", &x, &y);
x++; y++;
up_data(2, x, y, 0, 1, n, 1);
}
else
{
scanf("%d%d", &x, &y);
x++; y++;
int leijia = query_sum(x, y, 1, n, 1);
if (leijia != 0)
printf("NO\n");
else
{
int mi = query_min(x, y, 1, n, 1);
if (mi >= 0)
printf("YES\n");
else
printf("NO\n");
}
}
}
} int main()
{
//freopen("F:\\rush.txt", "r", stdin);
//freopen("F:\\rush_out.txt", "w", stdout);
int t;
scanf("%d", &t);
for (int ii = 1;ii <= t;ii++)
{
printf("Case %d:\n", ii);
input_data();
get_ans();
printf("\n");
}
return 0;
}
最新文章
- ASP.NET Core 中文文档 第五章 测试(5.2)集成测试
- ViewPager+PagerTabStrip实现页面的切换
- JSONP的小示例
- 我的第一个Node web程序
- Java GC系列(2):Java垃圾回收是如何工作的?
- Move Zeroes——Leetcode
- 使用html,JavaScript,ajax写一个小型实例
- DateUtils时间工具类探究
- Air Raid
- JQ简单实现无缝滚动
- Gradle构建Java工程配置详解
- VScode中python环境配置
- php进阶--菜鸟之路
- golang-generate-1pixel-image
- 进程间通信(IPC)
- flask框架詳解
- 记在Archlinux中安装python的pymssql模块过程中遇到的问题
- Python操作MySql --Python3
- (实用)Ubuntu 开启NFS服务
- IdUDPServer 收到4次重复的数据
热门文章
- Kernal Panic - Not syncing : VFS: unable to mount root fs on unknown-block
- select筛选用户数据
- Python基础:12函数细节
- LeetCode63 Unique Paths II
- Libev源码分析06:异步信号同步化--sigwait、sigwaitinfo、sigtimedwait和signalfd
- laravel 5.5 登录验证码 captcha 引入
- MySQL_连表查询
- 中国剩余定理(SCAUOJ 1077)
- python开启GPU加速
- 三种查看MySQL数据库版本的方法