BZOJ4695 最假女选手 < SegBeats >

Posted on Symbols count in article: 1.6k Reading time ≈ 6 mins.

Problem

最假女选手

Time  Limit:  50  Sec\mathrm{Time\;Limit:\;50\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

在刚刚结束的水题嘉年华的压轴节目放水大赛中，wyywyy\mathrm{wyywyy}如愿以偿的得到了最假女选手的奖项。但是作为主办人的C_SUNSHINE\mathrm{C\_SUNSHINE}为了证明wyywyy\mathrm{wyywyy}确实在放水，决定出一道基础题考察wyywyy\mathrm{wyywyy}的姿势水平。给定一个长度为NN序列，编号从11到NN。要求支持下面几种操作：

  1. 给一个区间[L,R][L,R]加上一个数xx
  2. 把一个区间[L,R][L,R]里小于xx的数变成xx
  3. 把一个区间[L,R][L,R]里大于xx的数变成xx
  4. 求区间[L,R][L,R]的和
  5. 求区间[L,R][L,R]的最大值
  6. 求区间[L,R][L,R]的最小值

Input

第一行一个整数NN表示序列长度
第二行NN个整数AiA_i表示初始序列
第三行一个整数MM表示操作个数
接下来MM行，每行三或四个整数，第一个整数TpTp表示操作类型，接下来L,R,XL,R,X或L,RL,R表述操作数

Output

对于每个4,5,64,5,6类型的操作，输出一行一个整数表示答案

Sample Input

1
2
3
4
5
2
1 2
2
2 1 2 2
4 1 2

Sample Output

1
4

HINT

1≤Tp≤6,  N,M≤5×105,  ∣Ai∣≤1081\le Tp\le6,\;N,M\le5\times10^5,\;|A_i|\le10^8
Tp=1Tp=1时,∣x∣≤1000|x|\le1000
Tp=2Tp=2或33时，∣x∣≤108|x|\le10^8

标签：SegBeats 线段树

Solution

Segment  Tree  Beats!\mathrm{Segment\;Tree\;Beats!}
参见吉老师的冬令营课件。

像课件里那样维护最大值、最大值个数、严格次大值、最小值、最小值个数、严格次小值、区间加标记、区间和，丧心病狂分类更新即可。注意只有区间和需要开long  long\mathrm{long\;long}，这样即省空间又省常数。

好久没写过上140140行的代码了…
强烈建议先对拍再交，否则容易卡住评测…

Code

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
#include <bits/stdc++.h>
#define ls (v<<1)
#define rs (v<<1|1)
#define mid ((s+t)>>1)
#define MAX_N 500000
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct node {int mx1, mx2, mxc, mi1, mi2, mic, tag;    lnt s;} tr[(MAX_N<<2)+5];
void update(int v) {
    tr[v].s = tr[ls].s+tr[rs].s;
    if (tr[ls].mx1 == tr[rs].mx1)
        tr[v].mx1 = tr[ls].mx1, 
        tr[v].mxc = tr[ls].mxc+tr[rs].mxc, 
        tr[v].mx2 = max(tr[ls].mx2, tr[rs].mx2);
    else if (tr[ls].mx1 > tr[rs].mx1)
        tr[v].mx1 = tr[ls].mx1, 
        tr[v].mxc = tr[ls].mxc, 
        tr[v].mx2 = max(tr[ls].mx2, tr[rs].mx1);
    else
        tr[v].mx1 = tr[rs].mx1, 
        tr[v].mxc = tr[rs].mxc, 
        tr[v].mx2 = max(tr[ls].mx1, tr[rs].mx2);
    if (tr[ls].mi1 == tr[rs].mi1)
        tr[v].mi1 = tr[ls].mi1, 
        tr[v].mic = tr[ls].mic+tr[rs].mic, 
        tr[v].mi2 = min(tr[ls].mi2, tr[rs].mi2);
    else if (tr[ls].mi1 < tr[rs].mi1)
        tr[v].mi1 = tr[ls].mi1, 
        tr[v].mic = tr[ls].mic, 
        tr[v].mi2 = min(tr[ls].mi2, tr[rs].mi1);
    else
        tr[v].mi1 = tr[rs].mi1, 
        tr[v].mic = tr[rs].mic, 
        tr[v].mi2 = min(tr[ls].mi1, tr[rs].mi2);
}
void updmx(int v, int s, int t, int x) {
    tr[v].s -= 1LL*tr[v].mxc*(tr[v].mx1-x);
    tr[v].mx1 = x, tr[v].mi1 = min(x, tr[v].mi1);
    if (tr[v].mx1^tr[v].mi1) tr[v].mi2 = min(x, tr[v].mi2);
    else
        tr[v].mx2 = -INF, tr[v].mi2 = INF, 
        tr[v].s = 1LL*(t-s+1)*x, tr[v].mxc = tr[v].mic = t-s+1;
}
void updmi(int v, int s, int t, int x) {
    tr[v].s += 1LL*tr[v].mic*(x-tr[v].mi1);
    tr[v].mi1 = x, tr[v].mx1 = max(x, tr[v].mx1);
    if (tr[v].mx1^tr[v].mi1) tr[v].mx2 = max(x, tr[v].mx2);
    else
        tr[v].mx2 = -INF, tr[v].mi2 = INF, 
        tr[v].s = 1LL*(t-s+1)*x, tr[v].mxc = tr[v].mic = t-s+1;
}
void downtag(int v, int s, int t) {
    int x = tr[v].tag;	tr[v].tag = 0;
    if (x)
        tr[ls].mx1 += x, tr[ls].mx2 += x, 
        tr[ls].mi1 += x, tr[ls].mi2 += x, 
        tr[ls].s += 1LL*(mid-s+1)*x, tr[ls].tag += x, 
        tr[rs].mx1 += x, tr[rs].mx2 += x, 
        tr[rs].mi1 += x, tr[rs].mi2 += x, 
        tr[rs].s += 1LL*(t-mid)*x, tr[rs].tag += x;
    if (tr[v].mx1 < tr[ls].mx1 && tr[v].mx1 > tr[ls].mx2) updmx(ls, s, mid, tr[v].mx1);
    if (tr[v].mi1 > tr[ls].mi1 && tr[v].mi1 < tr[ls].mi2) updmi(ls, s, mid, tr[v].mi1);
    if (tr[v].mx1 < tr[rs].mx1 && tr[v].mx1 > tr[rs].mx2) updmx(rs, mid+1, t, tr[v].mx1);
    if (tr[v].mi1 > tr[rs].mi1 && tr[v].mi1 < tr[rs].mi2) updmi(rs, mid+1, t, tr[v].mi1);
}
void build(int v, int s, int t) {
    if (s == t) {
        int x;	read(x);
        tr[v].mx1 = tr[v].mi1 = x, tr[v].mxc = tr[v].mic = 1;
        tr[v].mx2 = -INF, tr[v].mi2 = INF, tr[v].s = x;	return;
    }
    build(ls, s, mid), build(rs, mid+1, t), update(v);
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        tr[v].mx1 += x, tr[v].mx2 += x;
        tr[v].mi1 += x, tr[v].mi2 += x;
        tr[v].s += 1LL*(t-s+1)*x;
        tr[v].tag += x;	return;
    }
    downtag(v, s, t);
    if (l <= mid) modify(ls, s, mid, l, r, x);
    if (r >= mid+1) modify(rs, mid+1, t, l, r, x);
    update(v);
}
void optmx(int v, int s, int t, int l, int r, int x) {
    if (tr[v].mi1 >= x) return;
    if (s >= l && t <= r && x < tr[v].mi2)
        {updmi(v, s, t, x);	return;}
    downtag(v, s, t);
    if (l <= mid) optmx(ls, s, mid, l, r, x);
    if (r >= mid+1) optmx(rs, mid+1, t, l, r, x);
    update(v);
}
void optmi(int v, int s, int t, int l, int r, int x) {
    if (tr[v].mx1 <= x) return;
    if (s >= l && t <= r && x > tr[v].mx2)
        {updmx(v, s, t, x);	return;}
    downtag(v, s, t);
    if (l <= mid) optmi(ls, s, mid, l, r, x);
    if (r >= mid+1) optmi(rs, mid+1, t, l, r, x);
    update(v);
}
lnt query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].s;
    downtag(v, s, t);	lnt ret = 0LL;
    if (l <= mid) ret += query(ls, s, mid, l, r);
    if (r >= mid+1) ret += query(rs, mid+1, t, l, r);
    update(v);	return ret;
}
int getmx(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].mx1;
    downtag(v, s, t);	int ret = -INF;
    if (l <= mid) ret = max(ret, getmx(ls, s, mid, l, r));
    if (r >= mid+1) ret = max(ret, getmx(rs, mid+1, t, l, r));
    update(v);	return ret;
}
int getmi(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].mi1;
    downtag(v, s, t);	int ret = INF;
    if (l <= mid) ret = min(ret, getmi(ls, s, mid, l, r));
    if (r >= mid+1) ret = min(ret, getmi(rs, mid+1, t, l, r));
    update(v);	return ret;
}
int main() {
    int n, T;	read(n), build(1, 1, n), read(T);
    while (T--) {
        int opt, l, r, x;	read(opt);
        if (opt == 1) read(l), read(r), read(x), modify(1, 1, n, l, r, x);
        if (opt == 2) read(l), read(r), read(x), optmx(1, 1, n, l, r, x);
        if (opt == 3) read(l), read(r), read(x), optmi(1, 1, n, l, r, x);
        if (opt == 4) read(l), read(r), printf("%lld\n", query(1, 1, n, l, r));
        if (opt == 5) read(l), read(r), printf("%d\n", getmx(1, 1, n, l, r));
        if (opt == 6) read(l), read(r), printf("%d\n", getmi(1, 1, n, l, r));
    }
    return 0;
}