题目背景
妖梦是住在白玉楼的半人半灵，拥有使用剑术程度的能力。
题目描述
有一天，妖梦正在练习剑术。地面上摆放了一支非常长的木棒，妖梦把它们切成了等长的n段。现在这个木棒可以看做由三种小段构成，中间的n-2段都是左右都被切断的断头，我们记做’X’，最左边的一段和最右边的一段各有一个圆头，记做’（‘和’）’。幽幽子吃饱后闲来无事，决定戏弄一下妖梦。她拿来了许多这样的三种小段木棒，来替换掉妖梦切下来的n段中的一部分，然后问妖梦一些问题。这些操作可以这样描述:
1 x C 将第x个小段的木棒替换成C型，C只会是’X’,’(‘,’)’中的一种
2 l r 询问妖梦从第l段到第r段之间(含l,r)，有多少个完整的木棒
完整的木棒左右两端必须分别为’(‘和’)’，并且中间要么什么都没有，要么只能有’X’。
虽然妖梦能够数清楚这些问题，但幽幽子觉得她回答得太慢了，你能教给妖梦一个更快的办法吗？
输入输出格式
输入格式：
第一行两个整数n，m，n表示共有n段木棒，m表示有m次操作。
木棒的初始形状为(XXXXXX......XXXXXX)。
接下来m行，每行三个整数/字符，用空格隔开。第一个整数为1或2，表示操作的类型，若类型为1，则接下来一个整数x，一个字符C。若类型为2，接下来两个整数l,r。含义见题目描述。
输出格式：
对于每一个操作2，输出一行一个整数，表示对应询问的答案。
输入输出样例
输入样例#1：
4 4
2 1 4
2 2 4
1 2 (
2 2 4
输出样例#1：
1
0
1
说明
对于30%的数据，1<=n,m<=1000
对于100%的数据，1<=n,m<=200000
by-orangebird
调了3个小时无果。
弃疗了。
留下代码以后调。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
#define reg register
inline int read() {
int res = ;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) res=(res<<)+(res<<)+(ch^), ch=getchar();
return res;
}
#define N 200005
int n, m; int L1[N<<], R1[N<<], dat[N<<], L2[N<<], R2[N<<];
#define ls(o) o << 1
#define rs(o) o << 1 | 1 inline void pushup(int o)
{
dat[o] = dat[ls(o)] + dat[rs(o)];
if (L2[ls(o)] > R1[ls(o)] and R2[rs(o)] < L1[rs(o)]) dat[o]++;
L1[o] = min(L1[ls(o)], L1[rs(o)]);
L2[o] = max(L2[ls(o)], L2[rs(o)]);
R1[o] = max(R1[ls(o)], R1[rs(o)]);
R2[o] = min(R2[ls(o)], R2[rs(o)]);
} void Build(int l, int r, int o)
{
if (l == r) {
if (l == ) L1[o] = , L2[o] = , R1[o] = , R2[o] = 1e9;
else if (l == n) R1[o] = n, L1[o] = 1e9, L2[o] = , R2[o] = n;
else L1[o] = 1e9, L2[o] = , R1[o] = , R2[o] = 1e9;
return ;
}
int mid = l + r >> ;
Build(l, mid, ls(o));
Build(mid + , r, rs(o));
pushup(o);
} void change(int l, int r, int o, int pos, char c)
{
if (l == r)
{
if (c == '(') L1[o] = pos, L2[o] = pos, R1[o] = , R2[o] = 1e9;
else if (c = ')') R1[o] = pos, R2[o] = pos, L1[o] = 1e9, L2[o] = ;
else L1[o] = 1e9, L2[o] = , R1[o] = , R2[o] = 1e9;
return ;
}
int mid = l + r >> ;
if (pos <= mid) change(l, mid, ls(o), pos, c);
else change(mid + , r, rs(o), pos, c);
pushup(o);
} int query(int l, int r, int o, int ql, int qr)
{
if (l >= ql and r <= qr) return dat[o];
int res = ;
int mid = l + r >> ;
if (ql <= mid) res += query(l, mid, ls(o), ql, qr);
if (qr > mid) res += query(mid + , r, rs(o), ql, qr);
if (ql <= mid and qr > mid and L2[ls(o)] > R1[ls(o)] and R2[rs(o)] < L1[rs(o)] and L2[ls(o)] >= ql and R2[rs(o)] <= qr) res++;
return res;
} int main()
{
//freopen("testdatain.txt", "r", stdin);
//freopen("ym.ans", "w", stdout);
n = read(), m = read();
Build(, n, );
while(m--)
{
int opt = read();
if (opt == ) {
int x = read();
char y;
cin >> y;
change(, n, , x, y);
} else {
int x = read(), y = read();
printf("%d\n", query(, n, , x, y));
}
}
return ;
}