1 /* 2 之前的思想是用回溯的方式進行顏色的更新的！如果用回溯的方法的話，就是將每一個節點的顏色都要更新 3 通過子節點的顏色情況來判斷父節點的顏色情況 ！這就是TLE的原因！ 4 5 后來想一想沒有必要 ！加入[a, b] 區間有p管轄，那么tree[p]的顏色值就是[a, b]所有點的顏色值！ 6 如果[a,b]的子區間[c,d]沒被跟新，那么tree[p]也是[c,d]的值！ 7 否則，在更新[c,d]區間的時候，一定會經過 p 點！然后由上到下更新p<<1 和 p<<1|1 的值! 8 當找到[c,d]區間所對應的p‘時，并更新p’的值！、 9 10 之前的剪枝是點返回， 后面的是線段返回，當然更快！ 11 */ 12 #include<string> 13 #include<iostream> 14 #include<algorithm> 15 #include<cstring> 16 #include<cstdio> 17 #define M 100005 18 using namespace std; 19 20 21 int tree[4*M]; 22 23 int color[32]; 24 int L, T, O; 25 26 27 void buildT(int ld, int rd, int p){ 28 if(ld<=rd){ 29 tree[p]=1; 30 if(ld==rd) 31 return ; 32 int mid = (ld+rd)/2; 33 buildT(ld, mid, p<<1); 34 buildT(mid+1, rd, p<<1|1); 35 } 36 } 37 38 39 40 void updateT(int ld, int rd, int a, int b, int p, int k){ 41 if(tree[p] == k) return ;//如果當前更新的顏色和 之前p所管轄的區間的顏色相同，則返回 42 43 if(ld==a && rd==b){//p所管轄的區間的點的顏色全部是k！如果其子區間的顏色被更改，那么 44 tree[p]=k; //在更新子區間的時候一定會經過 p點，讓后通過p更新 p<<1 和 p<<1|1 子區間的顏色！ 45 return ; 46 } 47 48 if(tree[p]!=-1){//也就是在經過父節點時更新子節點的顏色狀態，也就是[a,b]包含在 p點所管轄的區間內 49 tree[p<<1] = tree[p<<1|1] = tree[p]; 50 tree[p]=-1; 51 } 52 if(ld<rd){ 53 int mid = (ld+rd)/2; 54 if(mid<a) 55 updateT(mid+1, rd, a, b, p<<1|1, k); 56 else if(mid>=b) 57 updateT(ld, mid, a, b, p<<1, k); 58 else{ 59 updateT(ld, mid, a, mid, p<<1, k); 60 updateT(mid+1, rd, mid+1, b, p<<1|1, k); 61 } 62 } 63 } 64 65 void queryT(int ld, int rd, int a, int b, int p){ 66 if(ld>rd) return ; 67 if(tree[p]!=-1){ 68 color[tree[p]]=1; 69 } 70 else{ 71 int mid = (ld+rd)/2; 72 if(mid<a) 73 queryT(mid+1, rd, a, b, p<<1|1); 74 else if(mid>=b) 75 queryT(ld, mid, a, b, p<<1); 76 else{ 77 queryT(ld, mid, a, mid, p<<1); 78 queryT(mid+1, rd, mid+1, b, p<<1|1); 79 } 80 } 81 } 82 83 int main(){ 84 85 while(scanf("%d%d%d", &L, &T, &O)!=EOF){ 86 buildT(1, L, 1); 87 while(O--){ 88 char ch[2]; 89 int a, b, c; 90 scanf("%s", ch); 91 if(ch[0]=='C'){ 92 scanf("%d%d%d", &a, &b, &c); 93 if(a>b){ 94 a^=b; 95 b^=a; 96 a^=b; 97 } 98 updateT(1, L, a, b, 1, c); 99 } 100 else{ 101 scanf("%d%d", &a, &b); 102 if(a>b){ 103 a^=b; 104 b^=a; 105 a^=b; 106 } 107 memset(color, 0, sizeof(color)); 108 queryT(1, L, a, b, 1); 109 int cnt=0; 110 for(int i=1; i<=T; ++i) 111 if(color[i]) ++cnt; 112 printf("%d\n", cnt); 113 } 114 } 115 } 116 return 0; 117 }
?
