首页 > 代码库 > [luogu P3797] 妖梦斩木棒 [线段树]
[luogu 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，输出一行一个整数，表示对应询问的答案。
输入输出样例
4 42 1 42 2 41 2 (2 2 4
101
说明
对于30%的数据，1<=n,m<=1000
对于100%的数据，1<=n,m<=200000
by-orangebird
十分可爱的线段树题啊QAQ
造一棵线段树，维护
1.有几段完整的木棍，
2.左边是否有向右边的开口，
3.右边是否有向左边的开口，
4.以及是否完全无开口（全为‘X‘）（便于区间合并）。
区间合并想得有点乱，但是不用下传标记的单点修改还是很exciting的。
一开始想特判一下n=1的情况来着，后来想想算了吧。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 inline int rint(){ 7 char ch; 8 int re=0; 9 bool flag=0; 10 while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘)); 11 ch==‘-‘?flag=1:re=ch-‘0‘; 12 while((ch=getchar())>=‘0‘&&ch<=‘9‘) re=re*10+ch-‘0‘; 13 return flag?-re:re; 14 } 15 16 inline char rchar(){ 17 char ch; 18 while((ch=getchar())!=‘X‘&&ch!=‘(‘&&ch!=‘)‘); 19 return ch; 20 } 21 22 struct segment{ 23 int l,r,num; 24 bool ll,rr,xx; 25 segment(){ num=0; ll=0; rr=0; xx=0; } 26 }; 27 28 const int maxn=200001; 29 30 segment tre[maxn<<2]; 31 int n,m; 32 33 segment merge(const segment &tl,const segment &tr){ 34 segment tx; 35 tx.l=tl.l; tx.r=tr.r; 36 tx.xx=tl.xx&tr.xx; 37 tx.ll=tr.xx?tl.ll:tr.ll; 38 tx.rr=tl.xx?tr.rr:tl.rr; 39 tx.num=tl.num+tr.num+((tl.ll&tr.rr)?1:0); 40 return tx; 41 } 42 43 void push_up(int x){ 44 tre[x]=merge(tre[x<<1],tre[x<<1|1]); 45 } 46 47 void build(int x,int l,int r){ 48 tre[x].l=l; tre[x].r=r; 49 if(l==r){ 50 if(l==1) tre[x].ll=1; 51 else if(r==n) tre[x].rr=1; 52 else tre[x].xx=1; 53 return; 54 } 55 int mid=(l+r)>>1; 56 build(x<<1,l,mid); build(x<<1|1,mid+1,r); 57 push_up(x); 58 } 59 60 void change(int x,int pos,int chaa){ 61 if(tre[x].l==tre[x].r){ 62 if(chaa==0){ 63 tre[x].ll=0; 64 tre[x].rr=0; 65 tre[x].xx=1; 66 } 67 else if(chaa==1){ 68 tre[x].ll=1; 69 tre[x].rr=0; 70 tre[x].xx=0; 71 } 72 else{ 73 tre[x].ll=0; 74 tre[x].rr=1; 75 tre[x].xx=0; 76 } 77 return; 78 } 79 int mid=(tre[x].l+tre[x].r)>>1; 80 if(pos<=mid) change(x<<1,pos,chaa); 81 else change(x<<1|1,pos,chaa); 82 push_up(x); 83 } 84 85 segment query(int x,int L,int R){ 86 if(L<=tre[x].l&&tre[x].r<=R) return tre[x]; 87 int mid=(tre[x].l+tre[x].r)>>1; 88 if(R<=mid) return query(x<<1,L,R); 89 if(L>mid) return query(x<<1|1,L,R); 90 return merge(query(x<<1,L,mid),query(x<<1|1,mid+1,R)); 91 } 92 93 int main(){ 94 //freopen("temp.in","r",stdin); 95 n=rint(); m=rint(); 96 build(1,1,n); 97 int opt,pos,left,right,chaa; 98 char cha; 99 for(int i=0;i<m;i++){100 opt=rint();101 switch(opt){102 case 1:{103 pos=rint(); cha=rchar();104 if(cha==‘X‘) chaa=0;105 else if(cha==‘(‘) chaa=1;106 else chaa=2;107 change(1,pos,chaa);108 break;109 }110 case 2:{111 left=rint(); right=rint();112 printf("%d\n",query(1,left,right).num);113 break;114 }115 }116 }117 return 0;118 }
[luogu P3797] 妖梦斩木棒 [线段树]