P3797 妖梦斩木棒
题目背景
妖梦是住在白玉楼的半人半灵，拥有使用剑术程度的能力。
题目描述
有一天，妖梦正在练习剑术。地面上摆放了一支非常长的木棒，妖梦把它们切成了等长的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
/*
线段树维护一段区间向左有没有开口，向右有没有开口，以及是否贯通(全是X),包含几段完整木棒
如XXX)XXX，就只有向左开口，没有向右开口
然后单点修改，区间查询即可。
与普通线段树的区别就在于多了合并操作
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
struct node{
int num;
bool l,r,p;
node(){}
node(int l_,int r_,int p_){
l=l_;r=r_;p=p_;num=;
}
}tr[];
node merge(node a,node b){
node res;
res.p=a.p&b.p;
res.l=a.p?b.l:a.l;
res.r=b.p?a.r:b.r;
res.num=a.num+b.num;
if(a.r&&b.l&&!a.p&&!b.p)res.num++;
return res;
}
void pushup(int k){
tr[k]=merge(tr[k<<],tr[k<<|]);
}
node query(int k,int l,int r,int L,int R){
if(l>=L&&r<=R)return tr[k];
int mid=(l+r)>>;
if(mid+>R)return query(k<<,l,mid,L,R);
if(L>mid)return query(k<<|,mid+,r,L,R);
return merge(query(k<<,l,mid,L,R),query(k<<|,mid+,r,L,R));
}
void build(int l,int r,int k){
if(l==r){
if(l==)tr[k]=node(,,);
else if(l==n)tr[k]=node(,,);
else tr[k]=node(,,);
tr[k].num=;
return;
}
int mid=(l+r)>>;
build(l,mid,k<<);
build(mid+,r,k<<|);
pushup(k);
}
void modify(int k,int l,int r,int x,int type){
if(l==r){
if(type==)tr[k]=node(,,);
else if(type==)tr[k]=node(,,);
else tr[k]=node(,,);
return;
}
int mid=(l+r)>>;
if(x<=mid)modify(k<<,l,mid,x,type);
else modify(k<<|,mid+,r,x,type);
pushup(k);
}
int main(){
freopen("Cola.txt","r",stdin);
scanf("%d%d",&n,&m);
build(,n,);
while(m--){
int type;
scanf("%d",&type);
if(type==){
int x,t;char c;
scanf("%d %c",&x,&c);
if(c=='X')t=;
else if(c==')')t=;
else t=;
modify(,,n,x,t);
}
else {
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(,,n,l,r).num);
}
}
return ;
}