題意：
? ? ?可以這樣理解，有一條直線，然后用n條線段去覆蓋，最后問全部都覆蓋完之后還有多少是沒有被完全覆蓋的。


思路：

? ? ?一開始想的有點(diǎn)偏，想到起點(diǎn)排序，然后..失敗了，原因是忘記了題目輸入的順序就是覆蓋的順序，后來(lái)突然想到了逆序，這個(gè)題目想到逆序也就差不多了，我們可以逆序處理，然后用異或操作去判斷當(dāng)前這段是否全部都被覆蓋了，只要異或不是1，那么就是還有沒覆蓋的，那么答案++，更新這段，把這段全都覆蓋上。

#include<stdio.h> #include<string.h> #include<algorithm>#define N 20005 #define lson l ,mid ,t << 1 #define rson mid + 1 ,r ,t << 1 | 1using namespace std;typedef struct {int l ,r; }EDGE;EDGE E[N]; int X[N*4]; int mark[N*4]; int num[N] ,numt[N];void PushUp(int t) {X[t] = X[t<<1] & X[t<<1|1];return ; }void PushDown(int t) {if(mark[t]){mark[t<<1] = mark[t<<1|1] = 1;X[t<<1] = X[t<<1|1] = 1;mark[t] = 0;}return ; }void BuidTree() {memset(X ,0 ,sizeof(X));memset(mark ,0 ,sizeof(mark));return ; }void Update(int l ,int r ,int t ,int a ,int b) {if(a <= l && b >= r){X[t] = mark[t] = 1;return ;}PushDown(t);int mid = (l + r) >> 1;if(a <= mid) Update(lson ,a ,b);if(b > mid) Update(rson ,a ,b);PushUp(t); }int Query(int l ,int r ,int t ,int a ,int b) {if(a <= l && b >= r)return X[t];PushDown(t);int mid = (l + r) >> 1;int s1 = -1 ,s2 = -1;if(a <= mid) s1 = Query(lson ,a ,b);if(b > mid) s2 = Query(rson ,a ,b);if(s1 == -1 && s2 == -1) return 0;if(s1 == -1) return s2;if(s2 == -1) return s1;return s1 & s2; }int Search2(int n ,int a) {int low = 1 ,up = n ,mid ,ans;while(low <= up){mid = (low + up) >> 1;if(a >= num[mid]){ans = mid;low = mid + 1;}else up = mid - 1;}return ans; }int main () {int n ,i ,Ans ,t ,id ,nn;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(id = 0 ,i = 1 ;i <= n ;i ++){scanf("%d %d" ,&E[i].l ,&E[i].r);numt[++id] = E[i].l;numt[++id] = E[i].r;}sort(numt + 1 ,numt + id + 1);nn = 0;for(i = 1 ;i <= id ;i ++)if(i == 1 || numt[i] != numt[i-1])num[++nn] = numt[i];BuidTree();for(Ans = 0 ,i = n ;i >= 1 ;i --){int l = Search2(nn ,E[i].l);int r = Search2(nn ,E[i].r);if(Query(1 ,nn ,1 ,l ,r)) continue;Ans ++;Update(1 ,nn ,1 ,l ,r);}printf("%d\n" ,Ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ2528线段树段更新逆序异或（广告牌）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。