题目链接：[点击打开链接](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=502&problem=2397&mosmsg=Submission+received+with+ID+16736144) 题意：有3种区间操作， 将某个区间全部变成1； 将某个区间全部变成0；将某个区间的1变成0， 0变成1。 思路：前两个操作就是最基本的区间更新， 用到懒惰标记， 然而第3个操作却有些麻烦， 如果仅仅更新当前这个结点对应的大区间， 那么它所包含的小区间再次更新时就会发生错误， 错误的原因是因为标记的重叠和碰撞。  显然 ， 这就是很典型的一个问题， 处理标记碰撞的问题。    问题的核心是解决碰撞， 使得每个点每个时刻至多只有一个标记。   那么怎么办呢？我们可以在两个标记发生碰撞的时候来看看会出现什么等价的情况： 当我们要更新一个结点o时： 如果我们要进行区间更新， 那么直接覆盖而不用管原来的标记。 但是如果是区间反转的时候： 如果该结点已经有一个标记v 那么： 当v == 1， 说明该区间上一次有一次全部变成1的操作， 等价于这次全部变成0， 所以懒惰标记最终变成0. 当v == 0，同理， 懒惰标记最终变成1. 当v == 2，说明该区间上一次有一个全部反转的操作还没有实现， 等价于这次不反转， 所以懒惰标记最终变成-1 当v == -1，说明该区间上一次没有操作， 等价于这次需要反转， 懒惰标记最终为2 其实就是一个等价转换而已， 当碰撞多了还将涉及一个处理的顺寻问题。 还有一点， 如果你是在更新结点v时就更新了sum[v]， 那么在等价转换的时候还涉及到sum[v]的更新问题， 不要想错了。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 1024010; int T,n,m,q,l,r,kase=0,sum[maxn<<2],setv[maxn<<2],a[maxn],cnt = 0; void PushUp(int o) { sum[o] = sum[o<<1] + sum[o<<1|1]; } void pushdown(int l, int r, int o) { if(setv[o] != -1) { int m = (l + r) >> 1; if(setv[o] == 1) { sum[o<<1] = (m - l + 1); sum[o<<1|1] = (r - m); setv[o<<1] = setv[o<<1|1] = setv[o]; } else if(setv[o] == 0) { sum[o<<1] = 0; sum[o<<1|1] = 0; setv[o<<1] = setv[o<<1|1] = setv[o]; } else { if(setv[o<<1] == 1) { setv[o<<1] = 0; sum[o<<1] = 0; } else if(setv[o<<1] == 0) { setv[o<<1] = 1; sum[o<<1] = (m - l + 1); } else if(setv[o<<1] == 2) setv[o<<1] = -1, sum[o<<1] = m - l + 1 - sum[o<<1]; else { setv[o<<1] = 2; sum[o<<1] = m - l + 1 - sum[o<<1]; } if(setv[o<<1|1] == 1) { setv[o<<1|1] = 0; sum[o<<1|1] = 0; } else if(setv[o<<1|1] == 0) { setv[o<<1|1] = 1; sum[o<<1|1] = (r - m); } else if(setv[o<<1|1] == 2) setv[o<<1|1] = -1, sum[o<<1|1] = r - m - sum[o<<1|1]; else { setv[o<<1|1] = 2; sum[o<<1|1] = r - m - sum[o<<1|1]; } } setv[o] = -1; } } void build(int l, int r, int o) { int m = (l + r) >> 1; setv[o] = -1; if(l == r) { ++cnt; if(a[cnt]) sum[o] = 1; else sum[o] = 0; return ; } build(l, m, o<<1); build(m+1, r, o<<1|1); PushUp(o); } void update(int L, int R, int v, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { if(v == 1) { sum[o] = (r - l + 1); setv[o] = 1; } else if(v == 0) { sum[o] = 0; setv[o] = 0; } else { if(setv[o] == 1) { setv[o] = 0; sum[o] = 0; } else if(setv[o] == 0) { setv[o] = 1; sum[o] = r - l + 1; } else if(setv[o] == -1) { setv[o] = 2; sum[o] = r - l + 1 - sum[o]; } else setv[o] = -1, sum[o] = r - l + 1 - sum[o]; } return ; } pushdown(l, r, o); if(L <= m) update(L, R, v, l, m, o<<1); if(m < R) update(L, R, v, m+1, r, o<<1|1); PushUp(o); } int query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { return sum[o]; } pushdown(l, r, o); int ans = 0; if(L <= m) ans += query(L, R, l, m, o<<1); if(m < R) ans += query(L, R, m+1, r, o<<1|1); PushUp(o); return ans; } char s[100]; int main() { scanf("%d",&T); while(T--) { scanf("%d",&m); int n = 0; for(int i=0;i<m;i++) { scanf("%d%s",&cnt,s); int len = strlen(s); while(cnt--) { for(int j=0;j<len;j++) { a[++n] = s[j] - '0'; } } } cnt = 0; build(1, n, 1); scanf("%d",&q); printf("Case %d:\n",++kase); int cc = 0; while(q--) { scanf("%s%d%d",s,&l,&r); l++; r++; if(s[0] == 'F') update(l, r, 1, 1, n, 1); else if(s[0] == 'E') update(l, r, 0, 1, n, 1); else if(s[0] == 'I') update(l, r, 2, 1, n, 1); else printf("Q%d: %d\n",++cc, query(l, r, 1, n, 1)); } } return 0; } ~~~