[UOJ 25] [IOI 2014] Wall 【线段树】

题目链接：UOJ – 25

题目分析

每个操作就是将被操作的数限制在一个区间，比如 Set_Max(5) 就是将被操作的数限定在了 [5, INF] 的区间里。

这些操作是可加的，但是必须按照顺序，不满足交换律。

对每个节点维护两个标记 Min_Tag[x], Max_Tag[x] ，表示这个节点的数被限制在了 [Max_Tag, Min_Tag] 的区间内。

最终的答案应该是 gmax(Max_Tag[x], gmin(MinTag[x], Val[x]))。其中 Val[x] 是 x 这个位置的初值。

对某一个节点进行 Set_Max(Num) 时，就是进行这样的操作: Max_Tag[x] = gmax(Max_Tag[x], Num); Min_Tag[x] = gmax(Min_Tag[x], Num);

对某一个节点进行 Set_Min(Num) 时，就是进行这样的操作: Max_Tag[x] = gmin(Max_Tag[x], Num); Min_Tag[x] = gmin(Min_Tag[x], Num);

PushDown(x) 的时候就是用 x 的 Max_tag, Min_Tag 对 x 的孩子进行操作。

这样维护两个标记，最后取答案的时候再用 gmax(Max_Tag[x], gmin(MinTag[x], Val[x])) 取答案就行了，不过这道题中初值都是0。

代码

#include "wall.h"const int MaxN = 2000000 + 5, MaxH = 100000 + 5;int Min_Tag[MaxN * 4], Max_Tag[MaxN * 4];void Build(int x, int s, int t)
{
if (s == t)
{
Min_Tag[x] = MaxH;
Max_Tag[x] = -MaxH;
return;
}
Min_Tag[x] = MaxH;
Max_Tag[x] = -MaxH;
int m = (s + t) >> 1;
Build(x << 1, s, m);
Build(x << 1 | 1, m + 1, t);
}inline int gmin(int a, int b) {return a < b ? a : b;}
inline int gmax(int a, int b) {return a > b ? a : b;} inline void Paint_Max(int x, int Num)
{
Max_Tag[x] = gmax(Max_Tag[x], Num);
Min_Tag[x] = gmax(Min_Tag[x], Num);
}inline void Paint_Min(int x, int Num)
{
Max_Tag[x] = gmin(Max_Tag[x], Num);
Min_Tag[x] = gmin(Min_Tag[x], Num);
}inline void PushDown(int x)
{
Paint_Max(x << 1, Max_Tag[x]);
Paint_Max(x << 1 | 1, Max_Tag[x]);
Max_Tag[x] = -MaxH;
Paint_Min(x << 1, Min_Tag[x]);
Paint_Min(x << 1 | 1, Min_Tag[x]);
Min_Tag[x] = MaxH;
}void Set_Max(int x, int s, int t, int l, int r, int Num)
{
if (l <= s && r >= t)
{
Paint_Max(x, Num);
return;
}
PushDown(x);
int m = (s + t) >> 1;
if (l <= m) Set_Max(x << 1, s, m, l, r, Num);
if (r >= m + 1) Set_Max(x << 1 | 1, m + 1, t, l, r, Num);
}void Set_Min(int x, int s, int t, int l, int r, int Num)
{
if (l <= s && r >= t)
{
Paint_Min(x, Num);
return;
}
PushDown(x);
int m = (s + t) >> 1;
if (l <= m) Set_Min(x << 1, s, m, l, r, Num);
if (r >= m + 1) Set_Min(x << 1 | 1, m + 1, t, l, r, Num);
}void Get_Ans(int x, int s, int t, int *&P)
{
if (s == t)
{
*P++ = gmax(Max_Tag[x], gmin(0, Min_Tag[x]));
return;
}
PushDown(x);
int m = (s + t) >> 1;
Get_Ans(x << 1, s, m, P);
Get_Ans(x << 1 | 1, m + 1, t, P);
}void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
Build(1, 1, n);
for (int i = 0; i < k; ++i)
{
if (op[i] == 1) Set_Max(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
else Set_Min(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
}
int *P = finalHeight;
Get_Ans(1, 1, n, P);
return;
}