题目背景
妖梦是住在白玉楼的半人半灵，拥有使用剑术程度的能力。
题目描述
有一天，妖梦正在练习剑术。地面上摆放了一支非常长的木棒，妖梦把它们切成了等长的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，输出一行一个整数，表示对应询问的答案。
输入输出样例
4 4
2 1 4
2 2 4
1 2 (
2 2 4
1
0
1
说明
对于30%的数据，1<=n,m<=1000
对于100%的数据，1<=n,m<=200000
by-orangebird
十分可爱的线段树题啊QAQ
造一棵线段树，维护
1.有几段完整的木棍，
2.左边是否有向右边的开口，
3.右边是否有向左边的开口，
4.以及是否完全无开口（全为'X'）（便于区间合并）。
区间合并想得有点乱，但是不用下传标记的单点修改还是很exciting的。
一开始想特判一下n=1的情况来着，后来想想算了吧。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; inline int rint(){
char ch;
int re=;
bool flag=;
while((ch=getchar())!='-'&&(ch<''||ch>''));
ch=='-'?flag=:re=ch-'';
while((ch=getchar())>=''&&ch<='') re=re*+ch-'';
return flag?-re:re;
} inline char rchar(){
char ch;
while((ch=getchar())!='X'&&ch!='('&&ch!=')');
return ch;
} struct segment{
int l,r,num;
bool ll,rr,xx;
segment(){ num=; ll=; rr=; xx=; }
}; const int maxn=; segment tre[maxn<<];
int n,m; segment merge(const segment &tl,const segment &tr){
segment tx;
tx.l=tl.l; tx.r=tr.r;
tx.xx=tl.xx&tr.xx;
tx.ll=tr.xx?tl.ll:tr.ll;
tx.rr=tl.xx?tr.rr:tl.rr;
tx.num=tl.num+tr.num+((tl.ll&tr.rr)?:);
return tx;
} void push_up(int x){
tre[x]=merge(tre[x<<],tre[x<<|]);
} void build(int x,int l,int r){
tre[x].l=l; tre[x].r=r;
if(l==r){
if(l==) tre[x].ll=;
else if(r==n) tre[x].rr=;
else tre[x].xx=;
return;
}
int mid=(l+r)>>;
build(x<<,l,mid); build(x<<|,mid+,r);
push_up(x);
} void change(int x,int pos,int chaa){
if(tre[x].l==tre[x].r){
if(chaa==){
tre[x].ll=;
tre[x].rr=;
tre[x].xx=;
}
else if(chaa==){
tre[x].ll=;
tre[x].rr=;
tre[x].xx=;
}
else{
tre[x].ll=;
tre[x].rr=;
tre[x].xx=;
}
return;
}
int mid=(tre[x].l+tre[x].r)>>;
if(pos<=mid) change(x<<,pos,chaa);
else change(x<<|,pos,chaa);
push_up(x);
} segment query(int x,int L,int R){
if(L<=tre[x].l&&tre[x].r<=R) return tre[x];
int mid=(tre[x].l+tre[x].r)>>;
if(R<=mid) return query(x<<,L,R);
if(L>mid) return query(x<<|,L,R);
return merge(query(x<<,L,mid),query(x<<|,mid+,R));
} int main(){
//freopen("temp.in","r",stdin);
n=rint(); m=rint();
build(,,n);
int opt,pos,left,right,chaa;
char cha;
for(int i=;i<m;i++){
opt=rint();
switch(opt){
case :{
pos=rint(); cha=rchar();
if(cha=='X') chaa=;
else if(cha=='(') chaa=;
else chaa=;
change(,pos,chaa);
break;
}
case :{
left=rint(); right=rint();
printf("%d\n",query(,left,right).num);
break;
}
}
}
return ;
}