題目鏈接：[點擊打開鏈接](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; } ~~~