「BZOJ3236」[AHOI2013]作业

Description

给定一个长度为nn的数列,有mm次询问。每一次询问一个区间[l,r][l,r]vi[a,b]v_i\in[a,b]的数的个数。以及是这些数中由多少个不同的数。

Input

第一行两个数n,mn,m
接下来nn个数,表示给定的数列,保证每个数是正整数。
接下来mm行,每行四个数l,r,a,bl,r,a,b

Output

输出mm行,每行两个数。

Sample Input

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

Sample Output

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

HINT

n100000,m1000000n\leq 100000,m\leq 1000000

Solution

对于询问[l,r][l,r],把它插入到线段树的各个对应的节点上。
最后遍历一遍线段树,统计答案。

假设当前线段树节点代表的区间是[L,R][L,R]且当前节点有询问插入。

第一个询问,用主席树来统计答案。从LLRR,按照权值从小到大遍历一遍。按照权值为下标,节点ii的位置和+1+1。询问直接求[1,b][1,a1][1,b]-[1,a-1]
对于第二个询问,直接预处理prepre数组,preipre_i表示上一次出现当前颜色的位置。询问L,RL,R中由多少个prepre小于LL即可!

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 120000, M = 1200000;
int n, m;
int a[N], pre[N], lst[N];
struct Q {
int a, b, i, l;
};
int ans1[M], ans2[M];
vector<Q>v[N * 4];
#define lch (o<<1)
#define rch (o<<1|1)
void add(int o, int L, int R, int l, int r, Q x) {
if(l <= L && r >= R) {
v[o].pb(x);
return;
}
int mid = (L + R) >>1;
if(l <= mid) add(lch, L, mid, l, r, x);
if(r > mid) add(rch, mid + 1, R, l, r, x);
}
pii tmp[N];
int num;
struct Tre {
int l, r, s;
}t[N * 40];
void ins(int pre, int &o, int l, int r, int x) {
o = ++num;
t[o] = t[pre];
++t[o].s;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) ins(t[pre].l, t[o].l, l, mid, x);
else ins(t[pre].r, t[o].r, mid + 1, r, x);
}
int rt[N];
int query(int pre, int o, int l, int r, int x) {
if(!o) return 0;
if(l == r) return t[o].s - t[pre].s;
int mid = (l + r) >> 1;
if(x <= mid) return query(t[pre].l, t[o].l, l, mid, x);
else return t[t[o].l].s - t[t[pre].l].s + query(t[pre].r, t[o].r, mid + 1, r, x);
}
void solve(int o, int l, int r) {
if(v[o].size()) {
// printf("%d->%d\n", l, r);
int cnt = 0;
for(int i = l; i <= r; ++i) {
tmp[++cnt].fi = a[i];
tmp[cnt].se = pre[i];
}
sort(tmp + 1, tmp + 1 + cnt);
for(int i = 1; i <= cnt; ++i)
ins(rt[i - 1], rt[i], 0, n - 1, tmp[i].se);
tmp[cnt + 1].fi = 1e9;
++cnt;
//rt[cnt + 1] = rt[cnt];
for(int i = 0; i < v[o].size(); ++i) {
int x = v[o][i].i;
int a = lower_bound(tmp + 1, tmp + 1 + cnt, mk(v[o][i].a, 0)) - tmp - 1;
int b = upper_bound(tmp + 1, tmp + 1 + cnt, mk(v[o][i].b, 100000000)) - tmp - 1;
// printf("a=%d,b=%d,num=%d %d cnt=%d\n", a, b,t[rt[b]].s, rt[b], cnt);
ans1[x] += t[rt[b]].s - t[rt[a]].s;
ans2[x] += query(rt[a], rt[b], 0, n - 1, v[o][i].l);
}
for(int i = 1; i <= num; ++i) t[i].l = t[i].r = t[i].s = 0;
for(int i = 1; i <= cnt; ++i) rt[i] = 0;
num = 0;
}
if(l == r) return;
int mid = (l + r) >> 1;
if(l <= mid) solve(lch, l, mid);
if(r > mid) solve(rch, mid + 1, r);
}
int b[N], tot;
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) {
b[i] = a[i] = read();
}
sort(b + 1, b + 1 + n);
tot = unique(b + 1, b +1 + n) - b - 1;
for(int i = 1; i <= n; ++i) {
a[i] = lower_bound(b + 1, b +1 + tot, a[i]) - b;
pre[i] = lst[a[i]];
lst[a[i]] = i;
}
for(int i = 1; i <= m; ++i) {
int l = read(), r = read(), A = read(), B = read();
A = lower_bound(b + 1, b +1 + tot, A) - b;
B = upper_bound(b + 1, b +1 + tot, B) - b - 1;
add(1, 1, n, l, r, (Q){A, B,i, l - 1});
}
solve(1, 1, n);
for(int i = 1; i <= m; ++i)
write(ans1[i]), putchar(' '), writeln(ans2[i]);
return 0;
}