這題網上結題報告應該很多了，我也不想多寫什么，但是寫完這題后，我對延遲標記的更新策略有了更新的理解
這題節點的結構應該算復雜的了
1 struct tree
2 {
3 int s,e;
4 char cover,del,turn,sta;
5 }st[65540*8];
其中除了狀態域，總共有3個延遲標記。合法的節點應該是至多存在一個延遲標記。所以我們在push_down的時候，當前節點至多有1個延遲標記，我們也要保證將該標記傳遞下去以后，兒子節點也要滿足至多存在一個延遲的約束，否則我們將無法處理木有優先級的多個標志重疊的情況。例如這題：
1 void push(int pos)
2 {
3 if(st[pos].turn)
4 {
5 st[pos].sta=!st[pos].sta;
6 st[pos].turn=0;
7 if(st[pos].e!=st[pos].s)
8 {
9 if(st[L].cover) st[L].cover=0,st[L].del=1;
10 else if(st[L].del) st[L].cover=1,st[L].del=0;
11 else st[L].turn=!st[L].turn;
12 if(st[R].cover) st[R].cover=0,st[R].del=1;
13 else if(st[R].del) st[R].cover=1,st[R].del=0;
14 else st[R].turn=!st[R].turn;
15 }
16 }
17 else if(st[pos].cover)
18 {
19 st[pos].cover=0;
20 st[pos].sta=1;
21 if(st[pos].e!=st[pos].s)
22 {
23 st[L].cover=1;
24 st[L].del=0;
25 st[L].turn=0;
26 st[R].cover=1;
27 st[R].del=0;
28 st[R].turn=0;
29 }
30 }
31 else if(st[pos].del)
32 {
33 st[pos].del=0;
34 st[pos].sta=0;
35 if(st[pos].e!=st[pos].s)
36 {
37 st[L].cover=0;
38 st[L].turn=0;
39 st[L].del=1;
40 st[R].cover=0;
41 st[R].del=1;
42 st[R].turn=0;
43 }
44 }
45 }
所有操作函數的結構都應該是這樣的
1 void insert(int s,int e,int pos)
2 {
3 push(pos);
4 if(st[pos].s==s&&st[pos].e==e) st[pos].cover=1;
5 else if(e<=M) insert(s,e,L);
6 else if(s>=M+1) insert(s,e,R);
7 else insert(s,M,L),insert(M+1,e,R);
8 }
因為這題木有向上維護的過程，如果有的話，末尾要加上
push(L),push(R),update(pos);
所有線段樹的結構都是如此，更新策略也亦是如此，只要保證節點至多1個延遲標記 的性質，題目就不會錯。
最后，附上本題得完整代碼，感覺我寫的算清楚的了
1 # include <stdio.h>
2 # include <string.h>
3 # include <stdlib.h>
4 struct tree
5 {
6 int s,e;
7 char cover,del,turn,sta;
8 }st[65540*8];
9 # define M ((st[pos].s+st[pos].e)>>1)
10 # define L (pos<<1)
11 # define R ((pos<<1)+1)
12 void init(int s,int e,int pos)
13 {
14 st[pos].s=s;
15 st[pos].e=e;
16 st[pos].cover=st[pos].del=st[pos].turn=st[pos].sta=0;
17 if(e!=s)
18 init(s,M,L),init(M+1,e,R);
19 }
20 void push(int pos)
21 {
22 if(st[pos].turn)
23 {
24 st[pos].sta=!st[pos].sta;
25 st[pos].turn=0;
26 if(st[pos].e!=st[pos].s)
27 {
28 if(st[L].cover) st[L].cover=0,st[L].del=1;
29 else if(st[L].del) st[L].cover=1,st[L].del=0;
30 else st[L].turn=!st[L].turn;
31 if(st[R].cover) st[R].cover=0,st[R].del=1;
32 else if(st[R].del) st[R].cover=1,st[R].del=0;
33 else st[R].turn=!st[R].turn;
34 }
35 }
36 else if(st[pos].cover)
37 {
38 st[pos].cover=0;
39 st[pos].sta=1;
40 if(st[pos].e!=st[pos].s)
41 {
42 st[L].cover=1;
43 st[L].del=0;
44 st[L].turn=0;
45 st[R].cover=1;
46 st[R].del=0;
47 st[R].turn=0;
48 }
49 }
50 else if(st[pos].del)
51 {
52 st[pos].del=0;
53 st[pos].sta=0;
54 if(st[pos].e!=st[pos].s)
55 {
56 st[L].cover=0;
57 st[L].turn=0;
58 st[L].del=1;
59 st[R].cover=0;
60 st[R].del=1;
61 st[R].turn=0;
62 }
63 }
64 }
65 void insert(int s,int e,int pos)
66 {
67 push(pos);
68 if(st[pos].s==s&&st[pos].e==e) st[pos].cover=1;
69 else if(e<=M) insert(s,e,L);
70 else if(s>=M+1) insert(s,e,R);
71 else insert(s,M,L),insert(M+1,e,R);
72 }
73 void clear(int s,int e,int pos)
74 {
75 push(pos);
76 if(st[pos].s==s&&st[pos].e==e) st[pos].del=1;
77 else if(e<=M) clear(s,e,L);
78 else if(s>=M+1) clear(s,e,R);
79 else clear(s,M,L),clear(M+1,e,R);
80 }
81 void turn(int s,int e,int pos)
82 {
83 push(pos);
84 if(st[pos].s==s&&st[pos].e==e) st[pos].turn=!st[pos].turn;
85 else if(e<=M) turn(s,e,L);
86 else if(s>=M+1) turn(s,e,R);
87 else turn(s,M,L),turn(M+1,e,R);
88 }
89 int quarry(int pos,int target)
90 {
91 push(pos);
92 if(st[pos].s==target&&st[pos].e==target)
93 return st[pos].turn?!st[pos].sta:st[pos].sta;
94 else if(target>M) return st[pos].turn?!quarry(R,target):quarry(R,target);
95 else return st[pos].turn?!quarry(L,target):quarry(L,target);
96 }
97 void print()
98 {
99 int i,last=-1,used=0;
100 for(i=0;i<=65540*2;i++)
101 {
102 if(quarry(1,i))
103 {
104 if(last==-1) last=i;
105 used=1;
106 }
107 else
108 {
109 if(last!=-1)
110 {
111 printf("%c%d,%d%c ",last%2?'(':'[',last/2,(i-1)%2?(i-1)/2+1:(i-1)/2,(i-1)%2?')':']');
112 last=-1;
113 }
114 }
115 }
116 if(!used) printf("empty set");
117 printf("\n");
118 }
119 int main()
120 {
121
122 char jud[5];
123 init(0,65540*2,1);
124 while(scanf("%s",jud)!=EOF)
125 {
126 char str[128],type1,type2;
127 int num1,num2;
128 scanf("%s",str);
129 type1=(*str=='(');
130 type2=(str[strlen(str)-1]==')');
131 str[strlen(str)-1]='\0';
132 num1=atoi(strtok(str+1,","));
133 num2=atoi(strtok(NULL," "));
134 if(type1) num1=num1*2+1;
135 else num1=num1*2;
136 if(type2) num2=num2*2-1;
137 else num2=num2*2;
138 switch(jud[0])
139 {
140 case 'U':
141 if(num1<=num2)
142 insert(num1,num2,1);
143 break;
144 case 'I':
145 if(num1<=num2)
146 {
147 if(0<=num1-1) clear(0,num1-1,1);
148 if(num2+1<=65540*2) clear(num2+1,65540*2,1);
149 }
150 else clear(0,65540*2,1);
151 break;
152 case 'D':
153 if(num1<=num2)
154 clear(num1,num2,1);
155 break;
156 case 'C':
157 if(num1<=num2)
158 {
159 if(0<=num1-1) clear(0,num1-1,1);
160 if(num2+1<=65540*2) clear(num2+1,65540*2,1);
161 turn(num1,num2,1);
162 }
163 else
164 clear(0,65540*2,1);
165 break;
166 case 'S':
167 if(num1<=num2)
168 turn(num1,num2,1);
169 break;
170 }
171 }
172 print();
173 return 0;
174 }