链接:
https://vjudge.net/problem/POJ-2104#author=malic
题意:
给定一个数组 a[1...n], 数组元素各不相同, 你的程序要对每次查询 Q(i,j,k) 作出回答, 其中 Q(i,j,k) 的含义为在数组 a[i...j] 中第 k 大的数字.
例如, 给出数组 a=(1, 5, 2, 6, 3, 7, 4). 查询语句为 Q(2, 5, 3), 即从 (5,2,6,3) 中找出第 3 大的元素, 将之排序得到 (2, 3, 5, 6), 故第三大的数字是 5, 所以这次查询的结果应当为 5.
思路:
主席树模板.
代码:
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- const int MAXN = 1e5+10;
- struct Node
- {
- int v;
- int pos;
- bool operator <(const Node& that)const
- {
- return this->v < that.v;
- }
- }node[MAXN];
- int Sca[MAXN], Ori[MAXN];
- struct Segment
- {
- int l, r;
- int cnt;
- }Seg[MAXN*30];
- int Tree_root[MAXN*30];
- int cnt = 0, tree_cnt = 0;
- int n, m;
- int Insert(int num, int last, int l, int r)
- {
- ++tree_cnt;// 树节点数加 1
- Seg[tree_cnt].cnt = Seg[last].cnt+1;// 数加 1
- int nownode = tree_cnt;// 记录当前节点数用于返回
- int mid = (l+r)/2;
- if (l == r)
- {
- return nownode;
- }
- else if (num <= mid)
- {
- Seg[nownode].l = Insert(num, Seg[last].l, l, mid);
- Seg[nownode].r = Seg[last].r;
- }
- else
- {
- Seg[nownode].l = Seg[last].l;
- Seg[nownode].r = Insert(num, Seg[last].r, mid+1, r);
- }
- return nownode;
- }
- int Query(int x, int y, int l, int r, int k)
- {
- // cout << Seg[x].cnt << ''<< Seg[y].cnt <<' '<< l <<' ' << r << endl;
- if (l == r)
- return l;
- int sum = (Seg[Seg[y].l].cnt - Seg[Seg[x].l].cnt);
- int mid = (l+r)/2;
- if (k <= sum)
- return Query(Seg[x].l, Seg[y].l, l, mid, k);
- else
- return Query(Seg[x].r, Seg[y].r, mid+1, r, k-sum);
- }
- void scatter()
- {
- // 离散化
- cnt = 0;
- int pos = 0;
- sort(node+1, node+1+n);
- Ori[++pos] = node[1].v;
- Sca[node[1].pos] = ++cnt;
- for (int i = 2;i <= n;i++)
- {
- if (node[i].v == node[i-1].v)
- {
- Sca[node[i].pos] = cnt;
- }
- else
- {
- Sca[node[i].pos] = ++cnt;
- Ori[++pos] = node[i].v;
- }
- }
- }
- int main()
- {
- scanf("%d %d", &n, &m);
- for (int i = 1;i <= n;i++)
- scanf("%d", &node[i].v), node[i].pos = i;
- scatter();
- Tree_root[0] = 0;
- Seg[0].cnt = 0;
- for (int i = 1;i <= n;i++)
- {
- int pos = Insert(Sca[i], Tree_root[i-1], 1, n);
- Tree_root[i] = pos;
- }
- while (m--)
- {
- int x, y, k;
- scanf("%d %d %d", &x, &y, &k);
- int pos = Query(Tree_root[x-1], Tree_root[y], 1, n, k);
- printf("%d\n", Ori[pos]);
- }
- return 0;
- }
- /*
- 7 3
- 1 5 2 6 3 7 4
- 2 5 3
- 4 4 1
- 1 7 3
- */
来源: http://www.bubuko.com/infodetail-3128805.html