洛谷-P1801 黑匣子(权值线段树)¶
题目描述¶
Black Box是一种原始的数据库。它可以储存一个整数数组,还有一个特别的变量i。最开始的时候Black Box是空的.而i等于0。这个Black Box要处理一串命令。
命令只有两种:
ADD(x):把x元素放进BlackBox;
GET:i加1,然后输出Blackhox中第i小的数。
记住:第i小的数,就是Black Box里的数的按从小到大的顺序排序后的第i个元素。例如:
我们来演示一下一个有11个命令的命令串。(如下图所示)
现在要求找出对于给定的命令串的最好的处理方法。ADD和GET命令分别最多200000个。现在用两个整数数组来表示命令串:
1.A(1),A(2),…A(M):一串将要被放进Black Box的元素。每个数都是绝对值不超过2000000000的整数,M$200000。例如上面的例子就是A=(3,1,一4,2,8,-1000,2)。
2.u(1),u(2),…u(N):表示第u(j)个元素被放进了Black Box里后就出现一个GET命令。例如上面的例子中u=(l,2,6,6)。输入数据不用判错。
输入格式¶
第一行,两个整数,M,N。
第二行,M个整数,表示A(l)
……A(M)。
第三行,N个整数,表示u(l)
…u(N)。
输出格式¶
输出Black Box根据命令串所得出的输出串,一个数字一行。
输入输出样例¶
输入¶
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
输出¶
3
3
1
2
说明/提示¶
对于30%的数据,M≤10000;
对于50%的数据,M≤100000:
对于100%的数据,M≤200000。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int M = 200005;
vector<int> num(M), numCopy(M);
vector<int> u(M);
struct Node {
int left, right;
int cnt;
};
vector<Node> v(M << 2); //线段树
void build(int k, int leftPos, int rightPos)
{
v[k].left = leftPos;
v[k].right = rightPos;
if (leftPos == rightPos) return;
int mid = leftPos + ((rightPos - leftPos) >> 1);
build(k << 1, leftPos, mid);
build(k << 1 | 1, mid + 1, rightPos);
}
void update(int k, int position)
{
if (v[k].left == v[k].right) {
++v[k].cnt;
return;
}
int mid = v[k].left + ((v[k].right - v[k].left) >> 1);
if (position <= mid) update(k << 1, position);
else update(k << 1 | 1, position);
v[k].cnt = v[k << 1].cnt + v[k << 1 | 1].cnt;
}
int query(int k, int number)
{
if (v[k].left == v[k].right) return v[k].left;
if (number <= v[k << 1].cnt) return query(k << 1, number);
else return query(k << 1 | 1, number - v[k << 1].cnt);
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> M >> n;
for (int i = 1; i <= M; ++i) {
cin >> num[i];
numCopy[i] = num[i];
}
sort(numCopy.begin() + 1, numCopy.begin() + 1 + M); //排序来为离散化做铺垫
int range = unique(numCopy.begin() + 1, numCopy.begin() + 1 + M) - numCopy.begin() - 1; //离散化计算出线段树的区间范围
build(1, 1, range); //建立线段树,此时还未统计个数
for (int i = 1; i <= n; ++i)
cin >> u[i];
int pre = 0, times = 0; //pre记录上次GET操作的位置,times记录查询次数
while (n--) {
++pre;
for (int i = u[pre - 1] + 1; i <= u[pre]; ++i) {
int position = lower_bound(numCopy.begin() + 1, numCopy.begin() + 1 + M, num[i]) - numCopy.begin();
update(1, position);
}
cout << numCopy[query(1, ++times)] << endl;
}
return 0;
}
这道题目其实思路很顺畅,但是细节颇多。
题目的意思是首先存入M个数据,然后进行N次查询。比如u(6)
,代表的含义是已经存入的前6个数据,假设现在是第i
次查询(i
从0开始计数),那么就查询这前6个数里的第i+1
小的数据。那么和通常的线段树一般是在查询前就已经构建好不同,这里需要在每次查询前才更新线段树。同时注意一个细节,需要一个变量去记录上一次加入了多少个数据,比如样例给出的,第一次u(1) = 1,u(2) = 2
,那么在为2时,为1的情况已经构建过了,所以只需要从第1个数据以后的数据。
另外需要考虑的是如果数据量很大,需要离散化处理,离散化就需要额外的数组来查询。查询的时候,如果当前节点左子节点所包含的数据小于查询的数据,那么需要先减去左子节点包含的数量,然后再到右子节点查询。
这道题目其实很灵活,目前见到的方法有:AVL, Splay Tree,堆