Problem Statement
$\hspace{15pt}$本题与《小鸡的排列构造》共享部分题目背景，但是所求内容不同，我们建议您重新阅读题面。
$\hspace{15pt}$小鸡出好了《小鸡的排列构造》一题，却发现自己不会写复杂度正确的checker（一定程度上是真的）！小鸡只好寻求你的帮助。
$\hspace{15pt}$具体来说，对于给定的长为 $n$ 的排列 $p$，你需要判断 $m$ 个问题，其中第 $i$ 个问题形如：
$\hspace{23pt}\bullet,$对于给定的 $l_i,r_i,c_i$，满足 $l_i\leq c_i\leq r_i$ 且 $l_i\neq r_i$，你需要输出将子区间 $[l_i,r_i]$ 中的元素从小到大排序后，原来位置 $c_i$ 处的数字移动到了哪里。
$\hspace{15pt}$这 $m$ 次询问是独立的，你可以理解为每次询问并不会真的改变原数组。
$\hspace{15pt}$长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，${2,3,1,5,4}$ 是一个长度为 $5$ 的排列，而 ${1,2,2}$ 和 ${1,3,4}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
$\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^5\right)$ 代表数据组数，每组测试数据描述如下：
$\hspace{15pt}$第一行输入两个正整数 $n,m\left(3\leq n\leq 10^5;\ 1\leq m\leq 3\times 10^5\right)$ 代表排列的长度、问题的数量。
$\hspace{15pt}$第二行输入 $n$ 个不同的正整数 $p_1,p_2,\dots,p_n\left(1\leq p_i\leq n\right)$ 代表给定的排列。
$\hspace{15pt}$此后 $m$ 行，每行输入三个正整数 $l,r,c\left(1\leq l\leq c\leq r \leq n;\ l\neq r\right)$ 代表一次询问。
$\hspace{15pt}$除此之外，保证单个测试文件的 $n$ 之和不超过 $3 \times 10^5$，$m$ 之和不超过 $3 \times 10^5$。
Output
$\hspace{15pt}$对于每一组测试数据，在一行上输出一个整数，代表第 $i$ 次询问的答案，即排序后原来位置 $c_i$ 处的数字移动到的位置的下标。
Sample
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
输入
2
5 3
1 4 2 3 5
3 5 4
1 3 2
1 5 4
9 5
1 4 9 2 8 7 3 5 6
1 7 4
2 9 2
3 4 4
5 9 7
1 9 7
输出
4 3 3 2 4 3 5 3
|
Solving
此题目我们不难想出要用树状数组求解：
暴力的思路是：
读取数据存储到arr数组，建立一个树状数组。
在线查询：每当输入l,r和c时，在树状数组上 依次从arr[l] arr[l+1] … arr[r]上的位置依次+1，最后返回arr[c]处在树状数组上的累加和(1-arr[c])得出排序后arr[c]在区间[l,r]内的位置，要得出答案还需加上l-1，最后再清空之前在[l,r]添加的1，进入下次查询
暴力算法
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
|
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define NINF -0x3f3f3f3f
//#define Single
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 1e5+100;
const int M = 0;
struct BIT
{
ll tree[N];//不要忘记初始化N
int n;
BIT()
{
memset(tree,0,sizeof(tree));
}
//注意树状数组的下标一定从1开始
int lowbit(int i)
{
return i & -i;
}
void add(int i,int v)
{
while(i <= n)
{
//将起始i二进制位不断加其本身最右边的1更新树状数组
tree[i] += v;
i += lowbit(i);
}
}
void clear()
{
for(int i=1;i<=n;i++)
{
if(tree[i]!=0) tree[i] = 0;
}
}
//返回1-i范围的累加和
ll sum(int i)
{
ll ans = 0;
while(i>0)
{
ans += tree[i];//不断加减去二进制最右边1的数
i -= lowbit(i);//不断减去二进制位最右边的1
}
return ans;
}
//返回l-r范围的累加和
ll rangesum(int l,int r)
{
return sum(r) - sum(l-1);
}
};
void solve()
{
int n,m;
cin >> n >> m;
BIT bit;
bit.n = n;
int arr[n+1];
for(int i=1;i<=n;i++) cin >> arr[i];
while(m--)
{
int l,r,c;
cin >> l >> r >> c;
for(int i=l;i<=r;i++)
{
bit.add(arr[i],1);
}
int ans = bit.sum(arr[c]);
cout << l + ans - 1 << endl;
for(int i=l;i<=r;i++)
{
bit.add(arr[i],-1);
}
}
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T;
#ifdef Single
T = 1;
#else
cin >> T;
#endif
while(T--)
{
solve();
}
return 0;
}
|
此类暴力算法虽然简单易懂，但时间复杂度最坏来到了O(m*nlogn) 显然无法在时间范围内解决这个问题。
此时我们需要对查询环节进行优化：
使用离线查询：
对各个查询的右边界进行排序，运用扫描线从右边界最小的时候开始依次查询。
离线处理的一般步骤:
排序查询 → 扫描线处理 → 动态维护 → 区间统计
在本题的区间统计中，由于是离线查询，我们可以离线处理所有查询的左边界和右边界，此时正常的在线查询答案的方式不再适用，我们可以利用前缀和的思想来统计区间内的数据：
这是前缀和思想在树状数组中的典型应用，其本质是：
$$
Sum[l...r] = Sum[r] - Sum[l-1]
$$
在离线处理中的优势：
顺序处理：按右端点排序后，可以保证处理到 r 时已经包含所有 <=r 的信息
空间复用：不需要为每个查询单独存储中间结果
时间优化：将 O(n) 的区间查询优化为 O(logn) 的前缀查询
离线思路
我们可以创建两个树状数组，一个用来维护每个查询区间[1,R]的结果，存储在ans1数组中；一个用来维护每个查询区间[1,L-1]的结果(由于是1~L-1所以后续答案仅需要加上当前查询区间的l,无需再-1)，存储在ans2数组中，随后利用前缀和的性质得出:
$$
ans[i] = ans1[i] - ans2[i] + query[i].l
$$
这样我们可以将总的时间复杂度降到了O(nlogn+mlogn):
离线查询+前缀和优化
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
|
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define NINF -0x3f3f3f3f
//#define Single
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 3e5+100;
const int M = 3e5+100;
struct Query
{
int l,r,val,id;//查询左右边界l,r，查询位置的值val，查询编号id.
}query[M];
bool cmp(Query a,Query b){ return a.r < b.r;};
struct BIT
{
ll tree[N];//不要忘记初始化N
int n;
BIT()
{
memset(tree,0,sizeof(tree));
}
//注意树状数组的下标一定从1开始
int lowbit(int i)
{
return i & -i;
}
void add(int i,int v)
{
while(i <= n)
{
//将起始i二进制位不断加其本身最右边的1更新树状数组
tree[i] += v;
i += lowbit(i);
}
}
//返回1-i范围的累加和
ll sum(int i)
{
ll ans = 0;
while(i>0)
{
ans += tree[i];//不断加减去二进制最右边1的数
i -= lowbit(i);//不断减去二进制位最右边的1
}
return ans;
}
//返回l-r范围的累加和
ll rangesum(int l,int r)
{
return sum(r) - sum(l-1);
}
};
void solve()
{
int n,m;
cin >> n >> m;
int arr[n+1];
for(int i=1;i<=n;i++) cin >> arr[i];
for(int i=1;i<=m;i++)
{
int l,r,c;
cin >> l >> r >> c;
int val = arr[c];
query[i] = {l,r,val,i};
}
//两个区间处理和总的答案数组
int ans1[m+1],ans2[m+1],ans[m+1];
//处理[1,r]小于val的个数
{
//复制一个query数组A
Query A[M];
memcpy(A,query,sizeof(query));
//依据右边界进行排序
sort(A+1,A+1+m,cmp);
//建立树状数组
BIT bit1;
bit1.n = n;
//扫描线指针
int ptr = 1;
for(int i=1;i<=m;i++)
{
//依次遍历每个查询
Query q = A[i];
while(ptr <= q.r)
{
bit1.add(arr[ptr],1);
ptr++;
}
//更新每个查询的答案
ans1[q.id] = bit1.sum(q.val-1);
}
}
//处理[1,l-1]小于val的个数
{
Query B[M];
memcpy(B,query,sizeof(query));
//将右边界设置为l-1排序
for(int i=1;i<=m;i++) B[i].r = B[i].l-1;
sort(B+1,B+1+m,cmp);
BIT bit2;
bit2.n = n;
int ptr = 1;
for(int i=1;i<=m;i++)
{
Query q = B[i];
if(q.r<1)//注意边界条件：如果左边界<1，则设置答案为0.
{
ans2[q.id] = 0;
continue;
}
while(ptr<=q.r)
{
bit2.add(arr[ptr],1);
ptr++;
}
ans2[q.id] = bit2.sum(q.val-1);
}
}
//利用前缀和思想得出答案
for(int i=1;i<=m;i++)
{
ans[i] = ans1[i] - ans2[i] + query[i].l;
cout << ans[i] << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T;
#ifdef Single
T = 1;
#else
cin >> T;
#endif
while(T--)
{
solve();
}
return 0;
}
|