hdu 3207 Highway

http://acm.hdu.edu.cn/showproblem.php?pid=3207

　　一道看上去好像是线段树的题，不过因为有两种操作（区间增加相同的数，以及将区间中比给出的数小的数更新成给出的数），所以用一般的线段数是不能正确更新的。这题应该是可以用线段树做的，因为在统计里的时间第一的人是貌似是用O(nlogn)的方法的。

　　一共三种操作：

　　1、如果区间连续，区间减少相同的数

　　2、区间增加相同的数

　　3、区间中比给出的数小的数都更新成给出的数

　　如果某个数小于等于0，那么那个数的位置断裂，而且不能修复！

　　这题一个比较简单的，而且不超时的方法是用类似二级检索的方法进行更新块状数组。因为线段树的更新延迟不止一个单位的时间，所以在多次的操作一或二和操作三交替进行，问题就会产生，所以要用二级检索，将区间分成每份长度都是sqrt(n)的段，每次都直接对段进行更新。假如将增加减少和操作三合成一个，那么多组操作同时更新会造成一定的问题。但是二级检索就不一样了，顺序O(sqrt(n))更新，这样更新就不会产生超过1个时间单位的延迟了。

　　每段需要记录元素的数组，一个记录最小值，一个记录增加量，一个记录当前要增加到的值，另外还要一个记录最大减少值（小于0的最小值）。

暴力代码以及随机数据生成器：

View Code

  1 #define prog 1
  2 
  3 #if prog == 1
  4 
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <ctime>
  8 #include <cstdlib>
  9 #include <algorithm>
 10 
 11 using namespace std;
 12 
 13 int main() {
 14     int T;
 15 
 16     freopen("in", "w", stdout);
 17     scanf("%d", &T);
 18     srand(time(NULL));
 19     while (T--) {
 20         int n = 100;
 21         int m = rand() % 20 + 11;
 22         int init = rand() % 900 + 101;
 23 
 24         printf("%d %d %d\n", n, m, init);
 25         while (m--) {
 26             int s = rand() % n + 1;
 27             int t = rand() % n + 1;
 28 
 29             if (s > t) swap(s, t);
 30             printf("%d %d %d %d\n", (rand() % 4) % 3 + 1, s, t, rand() % 1000 + 1);
 31         }
 32         puts("");
 33     }
 34     puts("0 0 0");
 35 
 36     return 0;
 37 }
 38 
 39 #endif
 40 
 41 #if prog == 2
 42 
 43 #include <cstdio>
 44 #include <cstring>
 45 #include <algorithm>
 46 #include <cstdlib>
 47 
 48 using namespace std;
 49 
 50 const int maxn = 100001;
 51 bool Break[maxn];
 52 int Dur[maxn], INIT;
 53 
 54 void init(int size) {
 55     for (int i = 1; i <= size; i++) {
 56         Break[i] = false;
 57         Dur[i] = INIT;
 58     }
 59 }
 60 
 61 bool can(int l, int r) {
 62     while (l <= r) {
 63         if (Break[l]) return false;
 64         l++;
 65     }
 66 
 67     return true;
 68 }
 69 
 70 void mod(int l, int r, int d) {
 71     while (l <= r) {
 72         Dur[l] = max(Dur[l], d);
 73         if (Dur[l] <= 0) Break[l] = true;
 74         l++;
 75     }
 76 }
 77 
 78 void add(int l, int r, int d) {
 79     while (l <= r) {
 80         Dur[l] += d;
 81         if (Dur[l] <= 0) Break[l] = true;
 82         l++;
 83     }
 84 }
 85 
 86 int main() {
 87     int N, M;
 88 
 89     freopen("in", "r", stdin);
 90     freopen("cmp", "w", stdout);
 91     while (~scanf("%d%d%d", &N, &M, &INIT) && (N + M + INIT)) {
 92         init(N);
 93 
 94         int cnt = 0;
 95 
 96         for (int i = 1; i <= M; i++) {
 97             int s, t, d, op;
 98 
 99             scanf("%d%d%d%d", &op, &s, &t, &d);
100             switch (op) {
101             case 1 :
102                 if (can(s, t)) {
103                     printf("Pass %d\n", i);
104                     cnt++;
105                     add(s, t, -d);
106                 }
107                 break;
108             case 2 :
109                 add(s, t, d);
110                 break;
111             case 3 :
112                 mod(s, t, d);
113                 break;
114             }
115         }
116         printf("%d\n", cnt);
117     }
118 
119     return 0;
120 }
121 
122 
123 #endif

代码如下：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cstdlib>
  5 #include <cassert>
  6 #include <cmath>
  7 
  8 using namespace std;
  9 
 10 #define lson l, m, rt << 1
 11 #define rson m + 1, r, rt << 1 | 1
 12 
 13 const int maxn = 100001;
 14 const int segCnt = 400;
 15 const int inf = 0x7f7f7f7f;
 16 
 17 int INIT, segLen = segCnt;
 18 struct Segment {
 19     int e[segCnt];
 20     int Min;
 21     int add;
 22     int addTo;
 23     int lowest;
 24 
 25     void init() {
 26         Min = INIT;
 27         for (int i = 0; i < segLen; i++) {
 28             e[i] = INIT;
 29         }
 30         add = addTo = lowest = 0;
 31     }
 32 
 33     void update() {
 34         Min = inf;
 35         for (int i = 0; i < segLen; i++) {
 36             if (e[i] <= abs(lowest)) e[i] = 0;
 37             if (e[i]) {
 38                 e[i] += add;
 39                 e[i] = max(e[i], addTo);
 40             }
 41             Min = min(Min, e[i]);
 42         }
 43         add = addTo = lowest = 0;
 44     }
 45 
 46     void Add(int l, int r, int d) {
 47         for (int i = l; i <= r; i++) {
 48             if (e[i]) {
 49                 e[i] = max(e[i] + d, 0);
 50             }
 51         }
 52         Min = inf;
 53         for (int i = 0; i < segLen; i++) {
 54             Min = min(Min, e[i]);
 55         }
 56     }
 57 
 58     void AddTo(int l, int r, int d) {
 59         for (int i = l; i <= r; i++) {
 60             if (e[i]) {
 61                 e[i] = max(e[i], d);
 62             }
 63         }
 64         Min = inf;
 65         for (int i = 0; i < segLen; i++) {
 66             Min = min(Min, e[i]);
 67         }
 68     }
 69 
 70     void show() {
 71         puts("Elements: ");
 72         for (int i = 0; i < segLen; i++) {
 73             printf(" %d", e[i]);
 74         }
 75         puts("");
 76         printf("min %d add %d addto %d lowest %d\n", Min, add, addTo, lowest);
 77         puts("~~~");
 78     }
 79 } seg[segCnt];
 80 
 81 bool noBreak(int _l, int _r) {
 82     int segL = _l / segLen, segR = _r / segLen;
 83     int restL = _l % segLen, restR = _r % segLen;
 84 
 85 //    printf("%d %d\n", segL, segR);
 86     if (segL != segR) {
 87         seg[segL].update();
 88         seg[segR].update();
 89 
 90         for (int i = restL; i < segLen; i++) {
 91             if (!seg[segL].e[i]) return false;
 92         }
 93         for (int i = 0; i <= restR; i++) {
 94             if (!seg[segR].e[i]) return false;
 95         }
 96         for (int i = segL + 1; i < segR; i++) {
 97             if (!seg[i].Min) return false;
 98         }
 99     } else {
100         seg[segL].update();
101 
102         for (int i = restL; i <= restR; i++) {
103             if (!seg[segL].e[i]) return false;
104         }
105     }
106 
107     return true;
108 }
109 
110 void Add(int _l, int _r, int _d) {
111     int segL = _l / segLen, segR = _r / segLen;
112     int restL = _l % segLen, restR = _r % segLen;
113 
114     if (segL != segR) {
115         seg[segL].update();
116         seg[segR].update();
117 
118         seg[segL].Add(restL, segLen - 1, _d);
119         seg[segR].Add(0, restR, _d);
120         for (int i = segL + 1; i < segR; i++) {
121             seg[i].add += _d;
122             if (seg[i].Min) seg[i].Min += _d;
123             if (seg[i].addTo) seg[i].addTo += _d;
124         }
125     } else {
126         seg[segL].update();
127 
128         seg[segL].Add(restL, restR, _d);
129     }
130 }
131 
132 bool Sub(int _l, int _r, int _d) {
133 
134     if (noBreak(_l, _r)) {
135 //        puts("noBreak");
136         int segL = _l / segLen, segR = _r / segLen;
137         int restL = _l % segLen, restR = _r % segLen;
138 
139         if (segL != segR) {
140             seg[segL].update();
141             seg[segR].update();
142 
143             seg[segL].Add(restL, segLen - 1, -_d);
144             seg[segR].Add(0, restR, -_d);
145             for (int i = segL + 1; i < segR; i++) {
146                 seg[i].add -= _d;
147                 seg[i].addTo = max(seg[i].addTo - _d, 0);
148                 seg[i].Min = max(seg[i].Min - _d, 0);
149                 if (!seg[i].addTo) seg[i].lowest = min(seg[i].lowest, seg[i].add);
150             }
151         } else {
152             seg[segL].update();
153 
154             seg[segL].Add(restL, restR, -_d);
155         }
156 
157         return true;
158     }
159     return false;
160 }
161 
162 void AddTo(int _l, int _r, int _d) {
163     int segL = _l / segLen, segR = _r / segLen;
164     int restL = _l % segLen, restR = _r % segLen;
165 
166     if (segL != segR) {
167         seg[segL].update();
168         seg[segR].update();
169 
170         seg[segL].AddTo(restL, segLen - 1, _d);
171         seg[segR].AddTo(0, restR, _d);
172         for (int i = segL + 1; i < segR; i++) {
173             if (seg[i].Min < _d && seg[i].addTo < _d) {
174                 seg[i].addTo = _d;
175                 if (seg[i].Min) seg[i].Min = _d;
176             }
177         }
178     } else {
179         seg[segL].update();
180 
181         seg[segL].AddTo(restL, restR, _d);
182     }
183 }
184 
185 int main() {
186     int N, M;
187 
188 //    freopen("in", "r", stdin);
189 //    freopen("out", "w", stdout);
190 //
191     while (~scanf("%d%d%d", &N, &M, &INIT) && (N + M + INIT)) {
192         segLen = (int)sqrt((double) N) + 1;
193         int op, a, b, c;
194         int cnt = 0;
195 
196         for (int i = 0; i < segLen; i++) {
197             seg[i].init();
198 //            printf("Init %d\n", i);
199 //            seg[i].show();
200         }
201         for (int i = 1; i <= M; i++) {
202             scanf("%d%d%d%d", &op, &a, &b, &c);
203             switch (op) {
204             case 1 :
205                 if (Sub(a, b, c)) {
206                     cnt++;
207 //                    printf("Pass %d\n", i);
208                 }
209                 break;
210             case 2 :
211                 Add(a, b, c);
212                 break;
213             case 3 :
214                 AddTo(a, b, c);
215                 break;
216             }
217 //            for (int j = 0; j < segLen; j++) {
218 //                printf("Op %d-%d   %d~%d\n", i, j, segLen * j, segLen * (j + 1) - 1);
219 //                seg[j].show();
220 //            }
221 //            puts("~~~~~~");
222         }
223         printf("%d\n", cnt);
224     }
225 
226     return 0;
227 }

——written by Lyon