Codeforces Round #210 (Div. 2) C. Levko and Array Recovery

线段树的逆过程，想了老一会，然后发现应该是包含区间对存在有影响，就不知怎么做了。。。然后尚大神，说，So easy，你要倒着来，然后再正着来，判断是不是合法就行了。然后我乱写了写，就过了。数据难道又水了。。。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 int p[5001],o[5001],ans[5001];
 8 int t[5001],l[5001],r[5001],d[5001];
 9 int main()
10 {
11     int n,m,i,j,flag,maxz;
12     scanf("%d%d",&n,&m);
13     for(i = 1;i <= n;i ++)
14     p[i] = -10000000;
15     for(i = 1;i <= m;i ++)
16     {
17         scanf("%d%d%d%d",&t[i],&l[i],&r[i],&d[i]);
18     }
19     flag = 0;
20     for(i = m;i >= 1;i --)
21     {
22         if(t[i] == 1)
23         {
24             for(j = l[i];j <= r[i];j ++)
25             p[j] -= d[i];
26         }
27         else
28         {
29             for(j = l[i];j <= r[i];j ++)
30             {
31                 if(o[j]&&p[j] < d[i]) continue;
32                 p[j] = d[i];
33                 o[j] = 1;
34             }
35         }
36     }
37     for(i = 1;i <= n;i ++)
38     ans[i] = p[i];
39     for(i = 1;i <= m;i ++)
40     {
41         if(t[i] == 1)
42         {
43             for(j = l[i];j <= r[i];j ++)
44             p[j] += d[i];
45         }
46         else
47         {
48             maxz = -1000000000;
49             for(j = l[i];j <= r[i];j ++)
50             {
51                 maxz = max(maxz,p[j]);
52             }
53             if(maxz != d[i]) flag = 1;
54         }
55     }
56     if(flag)
57     printf("NO
");
58     else
59     {
60         printf("YES
");
61         for(i = 1;i <= n;i ++)
62         {
63             if(i == 1)
64             printf("%d",ans[i]);
65             else
66             printf(" %d",ans[i]);
67         }
68         printf("
");
69     }
70     return 0;
71 }