P4137 Rmq Problem / mex - 线段树做法

rt[n] 是一棵权值线段树，用来记录前 n 个数（a[1],a[2],...,a[n]）的情况：

• [x,x] 节点记录数字 x 的最后出现的位置。
• [l,r] 节点记录数字 l,l+1,...,r 的最后出现位置的最小值。
  • 通过这个就能知道 [l,r] 是否存在 “最后出现位置小于某个数” 的数字。

当询问 L R 到来时，是在问第 L 个数到第 R 个数（a[L],a[L+1],...,a[R]）中，最小的没出现过的数字是谁。

rt[R] 中记录了前 R 个数的情况，所有 “没出现在第 L 个数到第 R 个数中” 的数字必然是 “最后出现位置小于 L” 的数字。找到满足这个条件（最后出现位置小于 L ）的最小的数字即可。

这是在线的做法，如果把询问离线下来可以不用可持久化线段树处理。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
// n数组a长度,m询问个数
int n, m, maxai, minai;
// a原数组，root森林里的根
int a[MAXN], root[MAXN];
int tot;
struct Tree
{
    // last:
    // 单点时：当前点最后一次出现的位置
    // 区间时：所有最后一次出现的位置的最小值
    int lc, rc, last;
} tree[MAXN * 32];
// 更新，上一棵的roor是pre，当前区间[l,r]，把 x 的值改为 y
int update(int pre, int l, int r, int x, int y)
{
    int now = ++tot;
    if (l == r)
    {
        tree[now].last = y;
        return now;
    }
    // 更新链
    int mid = (l + r) / 2;
    if (x > mid)
    {
        tree[now].lc = tree[pre].lc;
        tree[now].rc = update(tree[pre].rc, mid + 1, r, x, y);
    }
    else
    {
        tree[now].rc = tree[pre].rc;
        tree[now].lc = update(tree[pre].lc, l, mid, x, y);
    }
    tree[now].last = min(tree[tree[now].lc].last,
                         tree[tree[now].rc].last);
    return now;
}
// 查询 u 的 [l,r] 区间上第一个last小于x的数
int query(int u, int l, int r, int x)
{
    if (l == r)
        return l;
    if (u == 0)
        return l;
    // 左边最小的last值
    int temp = tree[tree[u].lc].last;
    int mid = (l + r) / 2;
    if (temp < x)
    {
        // 左边有小于x的数就去左边找
        return query(tree[u].lc, l, mid, x);
    }
    else
    {
        // 否则去右边找
        return query(tree[u].rc, mid + 1, r, x);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    maxai = -1;
    minai = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        maxai = max(maxai, a[i]);
    }
    maxai++;
    // 建空树,0号节点做一个自循环空树
    tree[0].lc = 0;
    tree[0].rc = 0;
    tree[0].last = 0;
    tot = 1;
    root[0] = 1;
    // 一人一棵权值线段树
    for (int i = 1; i <= n; i++)
    {
        root[i] = update(root[i - 1], minai, maxai, a[i], i);
    }
    // 处理询问
    while (m--)
    {
        int l, r, k;
        cin >> l >> r;
        cout << query(root[r], minai, maxai, l) << "\n";
    }
    return 0;
}

P3834 【模板】可持久化线段树 2

不离散化做权值线段树做法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
// n数组a长度,m询问个数
int n, m, maxai, minai;
// a原数组，root森林里的根
int a[MAXN], root[MAXN];

int tot;
struct Tree
{
    int lc, rc, cnt;
} tree[MAXN * 32];
// 更新，上一棵的roor是pre，当前区间[l,r]，要插入x
int update(int pre, int l, int r, int x)
{
    int now = ++tot;
    // 继承上一棵
    tree[now].cnt = tree[pre].cnt + 1;
    if (l == r)
        return now;
    // 更新链
    int mid = (l + r) / 2;
    if (x > mid)
    {
        tree[now].lc = tree[pre].lc;
        tree[now].rc = update(tree[pre].rc, mid + 1, r, x);
    }
    else
    {
        tree[now].rc = tree[pre].rc;
        tree[now].lc = update(tree[pre].lc, l, mid, x);
    }
    return now;
}
// 查询第x小值,[u,v]目标区间,[l,r]当前区间m
int query(int u, int v, int l, int r, int x)
{
    if (l == r)
        return l;
    int temp = tree[tree[v].lc].cnt - tree[tree[u].lc].cnt;
    int mid = (l + r) / 2;
    if (x <= temp)
        return query(tree[u].lc, tree[v].lc, l, mid, x);
    else
        return query(tree[u].rc, tree[v].rc, mid + 1, r, x - temp);
}
int main()
{
    scanf("%d%d", &n, &m);
    maxai = -1'000'000'001;
    minai = 1'000'000'001;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        maxai = max(maxai, a[i]);
        minai = min(minai, a[i]);
    }
    // 建空树,0号节点做一个自循环空树
    tree[0].lc = 0;
    tree[0].rc = 0;
    tree[0].cnt = 0;
    tot = 1;
    root[0] = 1;
    // 一人一棵权值线段树
    for (int i = 1; i <= n; i++)
        root[i] = update(root[i - 1], minai, maxai, a[i]);
    // 处理询问
    for (int i = 1; i <= m; i++)
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", query(root[l - 1], root[r], minai, maxai, k));
    }
    return 0;
}

离散化做权值线段树做法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
//n数组a长度,m询问个数,nn数组t长度,tot点的个数,离散化后的长度
int n, m, nn, tot;
//a原数组->映射关系，t离散后的数，root森林里的根
int a[MAXN], t[MAXN], root[MAXN];

struct Tree
{
	int l, r, cnt;
} tree[MAXN * 32];
//建树[l,r]
int build(int l,int r){
	int now=++tot;
	int mid=(l+r)/2;
	if(l<r){
		tree[now].l=build(l,mid);
		tree[now].r=build(mid+1,r);
	}
	return now;
}
//更新，上一棵的roor是pre，当前区间[l,r]，要插入x
int update(int pre,int l,int r,int x){
	int now=++tot;
	//继承上一棵
	tree[now].cnt=tree[pre].cnt+1;
	tree[now].l=tree[pre].l;
	tree[now].r=tree[pre].r;
	//更新链
	if(l<r){
		int mid=(l+r)/2;
		if(x>mid)	
			tree[now].r=update(tree[pre].r,mid+1,r,x);
		else
			tree[now].l=update(tree[pre].l,l,mid,x);
		
	}
	return now;
}
// 查询第x小值,[u,v]目标区间,[l,r]当前区间m
int query(int u,int v,int l,int r,int x){
	if(l==r) return l;
	int temp=tree[tree[v].l].cnt-tree[tree[u].l].cnt;
	int mid=(l+r)/2;
	if(x<=temp)
		return query(tree[u].l,tree[v].l,l,mid,x);
	else
		return query(tree[u].r,tree[v].r,mid+1,r,x-temp);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]),t[i] = a[i];
	//离散化
	sort(t + 1, t + n + 1);
	nn = unique(t + 1, t + n + 1) - t - 1;
	for (int i = 1; i <= n; i++)
		a[i] = lower_bound(t + 1, t + nn + 1, a[i]) - t;
	//建空树
	tot=0;
	root[0]=build(1,nn);
	//一人一棵权值线段树
	for(int i=1;i<=n;i++){
		root[i]=update(root[i-1],1,nn,a[i]);
	}
	//处理询问
	for(int i=1;i<=m;i++){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",t[query(root[l-1],root[r],1,nn,k)]);
	}
	return 0;
}