HDU5306 Gorgeous Sequence

发表于

  题意:维护一个数列，三个操作:

  1、区间对一个数取min

  2、询问区间max

  3、询问区间sum

  这道题看着就是一个线段树。
  仔细观察发现，1操作似乎不是很好维护，如果要维护似乎只能暴力下传。(其实暴力下传也能够过)
  有什么更好的办法?
  参考吉如一2016集训队论文，发现虽然不能有更好的替代方法，但是可以进行优化，减少下传次数。
  维护最大值$max$与区间和$sum$之外，再维护次大值$second$，最大值出现次数$times$。
  每次区间对一个数$x$取min时:
  若区间$max <= x$，忽略。
  区间$max > x$ 但 $second < x$，则$sum$减去$(max - x) \times times$，$max$变为$times$。
  $second >= x$，没办法，暴力递归解决。
  但是这样好像会递归到不存在的区间呀怎么办?没关系。不存在的区间max与second均为0，到了就会返回回来。唯一带来的坑点就是数组要看到$maxn \times 8$!!!!!(神坑)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
 
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define ms(a, b) memset(a, b, sizeof a)
 
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
    if(flag) x = -x; return x;
}
const int maxn = 1000010;
typedef long long LL;
namespace SGT
{
#define ls h << 1
#define rs h << 1 | 1
#define mid ((l + r) >> 1)
#define lc l, mid
#define rc mid + 1, r
    LL T[maxn * 8], Max[maxn * 8], Times[maxn * 8], Second[maxn * 8];
    LL min[maxn * 8];
    void pushup(int h)
    {
        T[h] = T[ls] + T[rs];
        if(Max[ls] == Max[rs])
        {
            Max[h] = Max[ls];
            Times[h] = Times[ls] + Times[rs];
            Second[h] = std::max(Second[ls], Second[rs]);
        }
        else
        {
            if(Max[ls] > Max[rs])
            {
                Max[h] = Max[ls];
                Times[h] = Times[ls];
                Second[h] = std::max(Second[ls], Max[rs]);
            }
            else
            {
                Max[h] = Max[rs];
                Times[h] = Times[rs];
                Second[h] = std::max(Second[rs], Max[ls]);
            }
        }
    }
    void pushdown(int h)
    {
        if(~min[h])
        {
            if(Max[ls] > min[h])
            {
                T[ls] -= Times[ls] * (Max[ls] - min[h]);
                Max[ls] = min[ls] = min[h];
            }
            if(Max[rs] > min[h])
            {
                T[rs] -= Times[rs] * (Max[rs] - min[h]);
                Max[rs] = min[rs] = min[h];
            }
            min[h] = -1;
        }
    }
    void creat(int h, int l, int r)
    {
        min[h] = -1;
        if(l == r)
        {
            Max[h] = read(T[h]);
            Second[h] = 0; Times[h] = 1;
            return;
        }
        creat(ls, lc); creat(rs, rc);
        pushup(h);
    }
    void update(int h, int l, int r, int L, int R, LL t)
    {
        if(L <= l && r <= R)
        {
            if(Max[h] <= t) return;
            if(Second[h] < t)
            {
                T[h] -= Times[h] * (Max[h] - t);
                Max[h] = min[h] = t;
            }
            else
            {
                pushdown(h);
                update(ls, lc, L, R, t);
                update(rs, rc, L, R, t);
                pushup(h);
            }
            return;
        }
        
        pushdown(h);
        if(L <= mid) update(ls, lc, L, R, t);
        if(R > mid) update(rs, rc, L, R, t);
        pushup(h);
    }
    LL qry_max(int h, int l, int r, int L, int R)
    {
        if(L <= l && r <= R) return Max[h];
        pushdown(h); LL ret = 0;
        if(L <= mid) chkmax(ret, qry_max(ls, lc, L, R)); 
        if(R > mid) chkmax(ret, qry_max(rs, rc, L, R)); 
        return ret;
    }
    LL qry_sum(int h, int l, int r, int L, int R)
    {
        if(L <= l && r <= R) return T[h];
        pushdown(h); LL ret = 0;
        if(L <= mid) ret += qry_sum(ls, lc, L, R); 
        if(R > mid) ret += qry_sum(rs, rc, L, R); 
        return ret;
    }
}
using namespace SGT;
int n, m;
int main()
{
    int _; read(_);
    while(_--)
    {
        read(n); read(m);
        creat(1, 1, n);
        while(m--)
        {
            int op, L, R; LL t; read(op);
            if(op == 0) read(L), read(R), read(t), update(1, 1, n, L, R, t);
            if(op == 1) read(L), read(R), printf("%lld\n", qry_max(1, 1, n, L, R));
            if(op == 2) read(L), read(R), printf("%lld\n", qry_sum(1, 1, n, L, R));
        }
    }
    return 0;
}