b414. BZOJ 3809 Gty 的二逼妹子序列

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

Autumn 和 Bakser 又在研究 Gty 的妹子序列了!

但他們遇到了一個難題,對於一段妹子們,他們想讓你幫忙求出這之內美麗度 $s_i \in [a, b]$ 的妹子的美麗度的種類數。為了方便,我們規定妹子們的美麗度全都在 $[1,n]$ 中。

給定一個長度為 $n$ ( $1 \le n \le 100000$ ) 的正整數序列 $s$ ($1 \le s_i \le n$),對於 $m$ ( $1 \le m \le 1000000$) 次詢問 $l, r, a, b$,每次輸出 $[s_l, \text{... },s_r]$ 中,權值 $s_i \in [a, b]$ 的權值種類數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
10 10
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4

Sample Output

1
2
3
4
5
6
7
8
9
10
2
0
0
2
1
1
1
0
1
2

Solution

解決區間內數字在某個值域內部的種類數。

前情提要 ,如果單純問區間種類數 (獨特),可以轉換成找區間內部有多少數字大於右端點,要預處理每一個數字的下一個相同數字的位置,只要符合大於右端點的條件即為獨特。可以使用持久化線段樹來做這件事情,依序加入序列數字,貪心去保留最右側的相同數字是獨特的,藉由多版本的區間相減來完成。

現在特別要求在某個值域內部,那就沒有好方法可解,可以使用莫隊下去完成。但是莫隊算法在區間轉移 (example [l, r] to [l, r+1]) 的效能要縮小到 $O(1)$,若使用一般樹結構,莫隊算法會衰退到 $O(N^{1.5} \log N)$,還不如修改快一點 $O(1)$,詢問慢一點 $O(\sqrt{N})$,將值域使用塊狀表方式記錄,來達到 $O(N^{1.5} + Q \sqrt{N})$

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXV = 100005;
const int MAXQ = 1000005;
const int MAXSQRTV = 512;
class Offline {
public:
struct Event {
static int PILE, belong[MAXV];
int l, r, x, y, qid;
Event(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0):
l(a), r(b), x(c), y(d), qid(e) {}
bool operator<(const Event &x) const {
if (belong[l] != belong[x.l])
return l < x.l;
return r < x.r;
}
};
int A[MAXN], N, qsize;
Event event[MAXQ];
int ret[MAXQ];
void init(int N) {
this->N = N, qsize = 0;
memset(pile, 0, sizeof(pile));
memset(val_count, 0, sizeof(val_count));
val_PILE = Event::PILE = sqrt(N);
for (int i = N; i >= 1; i--)
val_belong[i] = Event::belong[i] = i / Event::PILE;
}
void q_add(int l, int r, int a, int b) {
event[qsize] = Event(l, r, a, b, qsize);
qsize++;
}
void run() {
sort(event, event+qsize);
int l = 1, r = 0;
for (int i = 0; i < qsize; i++) {
while (r < event[i].r) r++, update(A[r], 1);
while (r > event[i].r) update(A[r], -1), r--;
while (l > event[i].l) l--, update(A[l], 1);
while (l < event[i].l) update(A[l], -1), l++;
ret[event[i].qid] = query(event[i].x, event[i].y);
}
}
private:
// unrolled
int pile[MAXSQRTV], val_count[MAXV], val_belong[MAXV], val_PILE;
inline void update(int x, int val) {
val_count[x] += val;
if (val == -1 && val_count[x] == 0)
pile[val_belong[x]]--;
if (val == 1 && val_count[x] == 1)
pile[val_belong[x]]++;
}
int query(int a, int b) {
int ret = 0;
if (val_belong[a] == val_belong[b]) {
for (int i = a; i <= b; i++)
ret += val_count[i] > 0;
return ret;
}
for (int i = val_belong[a]+1; i < val_belong[b]; i++)
ret += pile[i];
for (int i = (val_belong[a]+1)*val_PILE-1; i >= a; i--)
ret += val_count[i] > 0;
for (int i = (val_belong[b])*val_PILE; i <= b; i++)
ret += val_count[i] > 0;
return ret;
}
} off;
int Offline::Event::PILE = 16, Offline::Event::belong[MAXV];
namespace mLocalStream {
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
class Print {
public:
static const int N = 1048576;
char buf[N], *p, *end;
Print() {
p = buf, end = buf + N - 1;
}
void printInt(int x) {
static char stk[16];
int idx = 0;
stk[idx++] = '\n';
if (!x)
stk[idx++] = '0';
while (x)
stk[idx++] = x%10 + '0', x /= 10;
while (idx) {
if (p == end) {
*p = '\0';
printf("%s", buf), p = buf;
}
*p = stk[--idx], p++;
}
}
~Print() {
*p = '\0';
printf("%s", buf);
}
} bprint;
}
int main() {
int n, m, l, r, a, b;
while (mLocalStream::ReadInt(&n)) {
mLocalStream::ReadInt(&m);
off.init(n);
for (int i = 1; i <= n; i++)
mLocalStream::ReadInt(&off.A[i]);
for (int i = 0; i < m; i++) {
mLocalStream::ReadInt(&l);
mLocalStream::ReadInt(&r);
mLocalStream::ReadInt(&a);
mLocalStream::ReadInt(&b);
off.q_add(l, r, a, b);
}
off.run();
for (int i = 0; i < m; i++)
mLocalStream::bprint.printInt(off.ret[i]);
// printf("%d\n", off.ret[i]);
}
return 0;
}