首页 > ACM题库 > HDU-杭电 > HDU 3207-Highway-线段树-[解题报告]HOJ
2014
03-06

HDU 3207-Highway-线段树-[解题报告]HOJ

Highway

问题描述 :

As we all know, every day, there are hundreds of trucks passing through the highway. As some of the trucks might carry several tons of goods, the highway will be damaged unless it is frequently repaired. The administration of highway is worried about this, so it invented repairing cars to ensure that the cars can pass through the highway.

The highway has an initial durability. If a truck with x tons’ goods pass the highway, its durability will be decreased by x. Once the highway’s durability is less or equal to zero, it will be broken and can never be repaired. The trucks can’t pass through the broken ones.

There are two kinds of repairing cars: T1 can increase the highway’s durability by r, T2 can increase the highway’s durability to p, if the highway’s durability is less than p. Although the repairing cars can pass through the broken parts, the broken parts can’t be repaired.

输入:

The input consists of several test cases.

For every test case, there are three integers N (1<=N<=100000), M (1<=M<=100000), I (1<=I<=1000) in the first line, indicating the highway’s length, the numbers of cars and the initial durability of the highway.

Each of the next M lines described the information of cars in the following format:
1 s t d — There is a truck with d tons’ goods wanted to pass the interval [s, t]. You should check whether the truck can pass it. Notice that if the truck can’t pass the whole interval, it will give up the whole passing; otherwise it can pass the highway freely, even if the highway will be broken after the truck’s passing.
2 s t r — A T1 car will pass the interval [s, t] and increase its durability by r.
3 s t p — A T2 car will pass the interval [s, t] and increase its durability to p.
You can assume that 1<=s<=t<=N, 1<=d, p, r<=1000

The input ends with N=M=I=0.

输出:

The input consists of several test cases.

For every test case, there are three integers N (1<=N<=100000), M (1<=M<=100000), I (1<=I<=1000) in the first line, indicating the highway’s length, the numbers of cars and the initial durability of the highway.

Each of the next M lines described the information of cars in the following format:
1 s t d — There is a truck with d tons’ goods wanted to pass the interval [s, t]. You should check whether the truck can pass it. Notice that if the truck can’t pass the whole interval, it will give up the whole passing; otherwise it can pass the highway freely, even if the highway will be broken after the truck’s passing.
2 s t r — A T1 car will pass the interval [s, t] and increase its durability by r.
3 s t p — A T2 car will pass the interval [s, t] and increase its durability to p.
You can assume that 1<=s<=t<=N, 1<=d, p, r<=1000

The input ends with N=M=I=0.

样例输入:

5 5 5
1 1 3 3
2 2 3 10
1 1 3 3
1 1 3 1
1 2 3 1
5 3 10
1 1 2 5
1 2 3 5
1 1 3 5
0 0 0

样例输出:

3
2
Hint
In the second test case, the third truck can’t pass the road, because although the durability of interval [1, 2) and (2, 3] is larger than 0, in position 2, the durability is 0.

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

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

  一共三种操作:

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

  2、区间增加相同的数

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

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

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

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

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

#define prog 1
 
 #if prog == 1
 
 #include <cstdio>
 #include <cmath>
 #include <ctime>
 #include <cstdlib>
 #include <algorithm>
 
 using namespace std;
 
 int main() {
     int T;
 
     freopen("in", "w", stdout);
     scanf("%d", &T);
     srand(time(NULL));
     while (T--) {
         int n = 100;
         int m = rand() % 20 + 11;
         int init = rand() % 900 + 101;
 
         printf("%d %d %d\n", n, m, init);
         while (m--) {
             int s = rand() % n + 1;
             int t = rand() % n + 1;
 
             if (s > t) swap(s, t);
             printf("%d %d %d %d\n", (rand() % 4) % 3 + 1, s, t, rand() % 1000 + 1);
         }
         puts("");
     }
     puts("0 0 0");
 
     return 0;
 }
 
 #endif
 
 #if prog == 2
 
 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 #include <cstdlib>
 
 using namespace std;
 
 const int maxn = 100001;
 bool Break[maxn];
 int Dur[maxn], INIT;
 
 void init(int size) {
     for (int i = 1; i <= size; i++) {
         Break[i] = false;
         Dur[i] = INIT;
     }
 }
 
 bool can(int l, int r) {
     while (l <= r) {
         if (Break[l]) return false;
         l++;
     }
 
     return true;
 }
 
 void mod(int l, int r, int d) {
     while (l <= r) {
         Dur[l] = max(Dur[l], d);
         if (Dur[l] <= 0) Break[l] = true;
         l++;
     }
 }
 
 void add(int l, int r, int d) {
     while (l <= r) {
         Dur[l] += d;
         if (Dur[l] <= 0) Break[l] = true;
         l++;
     }
 }
 
 int main() {
     int N, M;
 
     freopen("in", "r", stdin);
     freopen("cmp", "w", stdout);
     while (~scanf("%d%d%d", &N, &M, &INIT) && (N + M + INIT)) {
         init(N);
 
         int cnt = 0;
 
         for (int i = 1; i <= M; i++) {
             int s, t, d, op;
 
             scanf("%d%d%d%d", &op, &s, &t, &d);
             switch (op) {
             case 1 :
                 if (can(s, t)) {
                     printf("Pass %d\n", i);
                     cnt++;
                     add(s, t, -d);
                 }
                 break;
             case 2 :
                 add(s, t, d);
                 break;
             case 3 :
                 mod(s, t, d);
                 break;
             }
         }
         printf("%d\n", cnt);
     }
 
     return 0;
 }
 
 
 #endif

代码如下:

#include <cstdio>
 #include <cstring>
 #include <algorithm>
 #include <cstdlib>
 #include <cassert>
 #include <cmath>
 
 using namespace std;
 
 #define lson l, m, rt << 1
 #define rson m + 1, r, rt << 1 | 1
 
 const int maxn = 100001;
 const int segCnt = 400;
 const int inf = 0x7f7f7f7f;
 
 int INIT, segLen = segCnt;
 struct Segment {
     int e[segCnt];
     int Min;
     int add;
     int addTo;
     int lowest;
 
     void init() {
         Min = INIT;
         for (int i = 0; i < segLen; i++) {
             e[i] = INIT;
         }
         add = addTo = lowest = 0;
     }
 
     void update() {
         Min = inf;
         for (int i = 0; i < segLen; i++) {
             if (e[i] <= abs(lowest)) e[i] = 0;
             if (e[i]) {
                 e[i] += add;
                 e[i] = max(e[i], addTo);
             }
             Min = min(Min, e[i]);
         }
         add = addTo = lowest = 0;
     }
 
     void Add(int l, int r, int d) {
         for (int i = l; i <= r; i++) {
             if (e[i]) {
                 e[i] = max(e[i] + d, 0);
             }
         }
         Min = inf;
         for (int i = 0; i < segLen; i++) {
             Min = min(Min, e[i]);
         }
     }
 
     void AddTo(int l, int r, int d) {
         for (int i = l; i <= r; i++) {
             if (e[i]) {
                 e[i] = max(e[i], d);
             }
         }
         Min = inf;
         for (int i = 0; i < segLen; i++) {
             Min = min(Min, e[i]);
         }
     }
 
     void show() {
         puts("Elements: ");
         for (int i = 0; i < segLen; i++) {
             printf(" %d", e[i]);
         }
         puts("");
         printf("min %d add %d addto %d lowest %d\n", Min, add, addTo, lowest);
         puts("~~~");
     }
 } seg[segCnt];
 
 bool noBreak(int _l, int _r) {
     int segL = _l / segLen, segR = _r / segLen;
     int restL = _l % segLen, restR = _r % segLen;
 
 //    printf("%d %d\n", segL, segR);
     if (segL != segR) {
         seg[segL].update();
         seg[segR].update();
 
         for (int i = restL; i < segLen; i++) {
             if (!seg[segL].e[i]) return false;
         }
         for (int i = 0; i <= restR; i++) {
             if (!seg[segR].e[i]) return false;
         }
         for (int i = segL + 1; i < segR; i++) {
             if (!seg[i].Min) return false;
         }
     } else {
         seg[segL].update();
 
         for (int i = restL; i <= restR; i++) {
             if (!seg[segL].e[i]) return false;
         }
     }
 
     return true;
 }
 
 void Add(int _l, int _r, int _d) {
     int segL = _l / segLen, segR = _r / segLen;
     int restL = _l % segLen, restR = _r % segLen;
 
     if (segL != segR) {
         seg[segL].update();
         seg[segR].update();
 
         seg[segL].Add(restL, segLen - 1, _d);
         seg[segR].Add(0, restR, _d);
         for (int i = segL + 1; i < segR; i++) {
             seg[i].add += _d;
             if (seg[i].Min) seg[i].Min += _d;
             if (seg[i].addTo) seg[i].addTo += _d;
         }
     } else {
         seg[segL].update();
 
         seg[segL].Add(restL, restR, _d);
     }
 }
 
 bool Sub(int _l, int _r, int _d) {
 
     if (noBreak(_l, _r)) {
 //        puts("noBreak");
         int segL = _l / segLen, segR = _r / segLen;
         int restL = _l % segLen, restR = _r % segLen;
 
         if (segL != segR) {
             seg[segL].update();
             seg[segR].update();
 
             seg[segL].Add(restL, segLen - 1, -_d);
             seg[segR].Add(0, restR, -_d);
             for (int i = segL + 1; i < segR; i++) {
                 seg[i].add -= _d;
                 seg[i].addTo = max(seg[i].addTo - _d, 0);
                 seg[i].Min = max(seg[i].Min - _d, 0);
                 if (!seg[i].addTo) seg[i].lowest = min(seg[i].lowest, seg[i].add);
             }
         } else {
             seg[segL].update();
 
             seg[segL].Add(restL, restR, -_d);
         }
 
         return true;
     }
     return false;
 }
 
 void AddTo(int _l, int _r, int _d) {
     int segL = _l / segLen, segR = _r / segLen;
     int restL = _l % segLen, restR = _r % segLen;
 
     if (segL != segR) {
         seg[segL].update();
         seg[segR].update();
 
         seg[segL].AddTo(restL, segLen - 1, _d);
         seg[segR].AddTo(0, restR, _d);
         for (int i = segL + 1; i < segR; i++) {
             if (seg[i].Min < _d && seg[i].addTo < _d) {
                 seg[i].addTo = _d;
                 if (seg[i].Min) seg[i].Min = _d;
             }
         }
     } else {
         seg[segL].update();
 
         seg[segL].AddTo(restL, restR, _d);
     }
 }
 
 int main() {
     int N, M;
 
 //    freopen("in", "r", stdin);
 //    freopen("out", "w", stdout);
 //
     while (~scanf("%d%d%d", &N, &M, &INIT) && (N + M + INIT)) {
         segLen = (int)sqrt((double) N) + 1;
         int op, a, b, c;
         int cnt = 0;
 
         for (int i = 0; i < segLen; i++) {
             seg[i].init();
 //            printf("Init %d\n", i);
 //            seg[i].show();
         }
         for (int i = 1; i <= M; i++) {
             scanf("%d%d%d%d", &op, &a, &b, &c);
             switch (op) {
             case 1 :
                 if (Sub(a, b, c)) {
                     cnt++;
 //                    printf("Pass %d\n", i);
                 }
                 break;
             case 2 :
                 Add(a, b, c);
                 break;
             case 3 :
                 AddTo(a, b, c);
                 break;
             }
 //            for (int j = 0; j < segLen; j++) {
 //                printf("Op %d-%d   %d~%d\n", i, j, segLen * j, segLen * (j + 1) - 1);
 //                seg[j].show();
 //            }
 //            puts("~~~~~~");
         }
         printf("%d\n", cnt);
     }
 
     return 0;
 }

 

——written by Lyon

参考:http://www.cnblogs.com/LyonLys/archive/2012/10/10/hdu_3207_Lyon.html


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的