【数据结构】可持久化线段树（主席树）

文章目录

接下来是一道例题
再放一道==标记永久化+主席树==
再加一道==主席树+在线处理==

主席树 即为 可持久化线段树，是一种可以记录每一个修改版本的数据结构。

难以进行区间的修改操作

主席树存储的信息

struct Node
{
   
    int l, r; // 左结点和右结点
    int cnt; // 区间内有多少数
};

下面以图示表示主席树记录修改的过程

在这里插入图片描述

接下来是一道例题

第k小数

给定长度为 $N$ 的整数序列 $A$ ，下标为 $1 \sim N$ 。

现在要执行 $M$ 次操作，其中第 $i$ 次操作为给出三个整数 $l_i,r_i,k_i$ ，求 $A[l_i],A[l_i+1],…,A[r_i]$ (即 $A$ 的下标区间 $l_i,r_i]$ 中第 $k_i$ 小的数是多少。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

第二行包含 $N$ 个整数，表示整数序列 $A$ 。

接下来 $M$ 行，每行包含三个整数 $l_i,r_i,k_i$ ，用以描述第 $i$ 次操作。

输出格式

对于每次操作输出一个结果，表示在该次操作中，第 $k$ 小的数的数值。

每个结果占一行。

数据范围

$N \leq 105, M \leq 104, ∣ A [i] ∣ \leq 109$

输入样例：

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

输出样例：

5
6
3

思路

参考前缀和的想法，找到 $1\ -\ r$ 和 $1\ -\ l-1$ 的区间元素个数，然后二分求解

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 10010;

int n, m;
int a[N]; // 原数组
vector<int> nums; // 离散化数组

struct Node
{
   
    int l, r;
    int cnt;
}tr[N * 4 + N * 17];

int root[N], idx; // 存以每个元素结尾的数组的线段树

int find(int x) // 离散化 找x对应的序号
{
   
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

int build(int l, int r)
{
   
    int p = ++ idx; // 新结点编号
    if (l == r) return p; // 说明是叶子结点
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r); // 建树
    return p;
}

// 在p结点的基础上
int insert(int p, int l, int r, int x)
{
   
    int q = ++ idx; // 新结点编号
    tr[q] = tr[p]; // 先复制一下原来的结点（也就是i-1版） 在原来结点的基础上进行修改
    if (l == r)    // 叶子结点返回
    {
   
        tr[q].cnt ++ ;
        return q;
    }
    // 在刚刚复制原来的结点时已经记录了l和r的信息 现在看哪一边需要修改就修改哪一边
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);

    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt; // 更新最新的cnt 可以理解为线段树里的pushup操作
    return q; // 返回结点编号
}

int query(int q, int p, int l, int r, int k)
{
   
    if (l == r) return r; // 叶子结点直接返回
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    // k小于cnt说明要找的点在左半边，否则在右半边
    if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

int main()
{
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
   
        cin >> a[i];
        nums.push_back(a[i]);
    }

    // 离散化去重
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    root[0] = build(0, nums.size() - 1); // 构造初版线段树

    for (int i = 1; i <= n; i ++ )
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i])); // 在i-1的版本上修改形成第i版

    while (m -- )
    {
   
        int l, r, k;
        cin >> l >> r >> k;
        cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << '\n';
    }
}

再放一道标记永久化+主席树

TTM - To the moon

一个长度为 $N$ 的数组 ${A\}$ ， $4$ 种操作：

C l r d：区间 $[l, r]$ 中的数都加 $d$ ，同时当前的时间戳加 $1$ 。
Q l r：查询当前时间戳区间 $[l, r]$ 中所有数的和。
H l r t：查询时间戳 $t$ 区间 $[l, r]$ 的和。
B t：将当前时间戳置为 $t$ 。

所有操作均合法。

ps：刚开始时时间戳为 $0$

输入格式，一行 $N$ 和 $M$ ，接下来 $M$ 行每行一个操作

输出格式：对每个查询输出一行表示答案

数据保证： $1\le N,M\le 10^5$ ， $|A_i|\le 10^9$ ， $1\le l \le r \le N$ ， $|d|\le10^4$ 。在刚开始没有进行操作的情况下时间戳为 $0$ ，且保证 B 操作不会访问到未来的时间戳。`

输入格式

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出格式

code

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100010;

int n, m;
int a[N];

struct Node
{
   
    int l, r; // 左右结点编号
    int ll, rr; // 左右边界
    int sum; // 区间元素和
    int lazy;
}tr[N * 40];

int root[N], idx;

int build(int l, int r)
{
   
    int p = ++ idx;
    tr[p].ll = l, tr[p].rr = r;
    if (l == r)
    {
   
        tr[p].sum = a[l];
        return p;
    }
    int mid = l + r >> 1;
    tr[p].l = build(l, mid);
    tr[p].r = build(mid + 1, r);
    tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum + tr[p].lazy * (r - l + 1);
    return p;
}

// l-r是要修改的部分 p是要修改的结点
int insert(int p, int l, int r, int x)
{
   
    int q = ++ idx;
    tr[q] = tr[p];
    if (tr[q].ll >= l && tr[q].rr <= r)
    {
   
        tr[q].lazy += x;
        tr[q].sum += (tr[q].rr - tr[q].ll + 1) * x;
        return q;
    }
    int mid = tr[q].ll + tr[q].rr >> 1;
    if (l <= mid) tr[q].l = insert(tr[p].l, l, r, x);
    if (r > mid) tr[q].r = insert(tr[p].r, l, r, x);
    tr[q].sum = tr[tr[q].l].sum + tr[tr[q].r].sum + tr[q].lazy * (tr[q].rr - tr[q].ll + 1);
    return q;
}

int query(int p, int l, int r, int lazy)
{
   
    if (tr[p].ll >= l && tr[p].rr <= r) return tr[p].sum + lazy * (tr[p].rr - tr[p].ll + 1);
    int mid = tr[p].ll + tr[p].rr >> 1;
    int res = 0;
    lazy += tr[p].lazy;
    if (l <= mid) res += query(tr[p].l, l, r, lazy);
    if (r > mid) res += query(tr[p].r, l, r, lazy);
    return res;
}

signed main()
{
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    root[0] = build(1, n);
    int now = 0;

    for (int i = 1; i <= m; i ++ )
    {
   
        char op;
        int l, r, d, t;
        cin >> op;

        if (op == 'C')
        {
   
            cin >> l >> r >> d;
            now ++ ;
            root[now] = insert(root[now - 1], l, r, d);
        }
        else if (op == 'Q')
        {
   
            cin >> l >> r;
            cout << query(root[now], l, r, tr[root[now]].lazy) << '\n';
        }
        else if (op == 'H')
        {
   
            cin >> l >> r >> t;
            cout << query(root[t], l, r, tr[root[t]].lazy) << '\n';
        }
        else
        {
   
            cin >> t;
            now = t;
        }
    }
}

再加一道主席树+在线处理

D. Jamie and To-do List

Why I have to finish so many assignments???

Jamie is getting very busy with his school life. He starts to forget the assignments that he has to do. He decided to write the things down on a to-do list. He assigns a value priority for each of his assignment (lower value means more important) so he can decide which he needs to spend more time on.

After a few days, Jamie finds out the list is too large that he can’t even manage the list by himself! As you are a good friend of Jamie, help him write a program to support the following operations on the to-do list:

set a**i x**i — Add assignment a**i to the to-do list if it is not present, and set its priority to x**i. If assignment a**i is already in the to-do list, its priority is changed to x**i.
remove a**i — Remove assignment a**i from the to-do list if it is present in it.
query a**i — Output the number of assignments that are more important (have a smaller priority value) than assignment a**i, so Jamie can decide a better schedule. Output - 1 if a**i is not in the to-do list.
undo d**i — Undo all changes that have been made in the previous d**i days (not including the day of this operation)

At day 0, the to-do list is empty. In each of the following q days, Jamie will do exactly one out of the four operations. If the operation is a query, you should output the result of the query before proceeding to the next day, or poor Jamie cannot make appropriate decisions.

Input

The first line consists of a single integer $q (1 ≤ q ≤ 10^5)$ — the number of operations.

The following q lines consists of the description of the operations. The i-th line consists of the operation that Jamie has done in the i-th day. The query has the following format:

The first word in the line indicates the type of operation. It must be one of the following four: set, remove, query, undo.

If it is a set operation, a string a**i and an integer $x_i$ follows $1 ≤ x_i ≤ 109)$ . a**i is the assignment that need to be set to priority $x_i$ .
If it is a remove operation, a string $a_i$ follows. $a_i$ is the assignment that need to be removed.
If it is a query operation, a string $a_i$ follows. $a_i$ is the assignment that needs to be queried.
If it is a undo operation, an integer $d_i$ follows $0 ≤ d_i < i)$ . $d_i$ is the number of days that changes needed to be undone.

All assignment names $a_i$ only consists of lowercase English letters and have a length $1 ≤ |a_i| ≤ 15$ .

It is guaranteed that the last operation is a query operation.

Output

For each query operation, output a single integer — the number of assignments that have a priority lower than assignment $a_i$ , or $- 1$ if $a_i$ is not in the to-do list.

Interaction

If the operation is a query, you should output the result of the query and flush the output stream before proceeding to the next operation. Otherwise, you may get the verdict Idleness Limit Exceed.

For flushing the output stream, please refer to the documentation of your chosen programming language. The flush functions of some common programming languages are listed below:

C: fflush(stdout);
C++: cout « flush;
Java: System.out.flush();

Examples

input

8
set chemlabreport 1
set physicsexercise 2
set chinesemockexam 3
query physicsexercise
query chinesemockexam
remove physicsexercise
query physicsexercise
query chinesemockexam

output

code

一棵线段树无法维护时可以同时维护两个线段树

#include <bits/stdc++.h>

using namespace std;

const int N = 11;
const int INF = 1e9 + 10;

int n, tot;
map<int, int> nums; // 离散化
map<string, int> m;

struct Operation
{
   
    string op;
    string test;
    int x;
};

struct Node
{
   
    int l, r;
    int cnt;
}tr[N * 50];

int root1[N], root2[N], idx;

int insert(int p, int l, int r, int pos, int op, string s)
{
   
    int q = ++ idx;
    tr[q] = tr[p];
    if (l == r)
    {
   
        tr[q].cnt += op;
        return q;
    }
    int mid = l + r >> 1;
    if (pos <= mid) tr[q].l = insert(tr[q].l, l, mid, pos, op, s);
    else tr[q].r = insert(tr[q].r, mid + 1, r, pos, op, s);
    if (tr[q].l == tr[q].r) tr[q].cnt = tr[tr[q].l].cnt;
    else tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int query(int q, int l, int r, int nl, int nr)
{
   
    if (r == -1) return 0;
    if (nl >= l && nr <= r) return tr[q].cnt;
    int mid = nl + nr >> 1;
    int res = 0;
    if (l <= mid) res += query(tr[q].l, l, r, nl, mid);
    if (r > mid) res += query(tr[q].r, l, r, mid + 1, nr);
    return res;
}

int main()
{
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    vector<Operation> ope(n + 1);

    for (int i = 1; i <= n; i ++ )
    {
   
        cin >> ope[i].op;
        string op = ope[i].op;
        if (op == "set")
        {
   
            cin >> ope[i].test >> ope[i].x;
            nums[ope[i].x] = tot;
            string s = ope[i].test;
            int x = ope[i].x;

            if (!query(root1[i - 1], 0, n - 1, tot, tot))
            {
   
                root1[i] = insert(root1[i - 1], 0, n - 1, tot, x, s);
                root2[i] = insert(root2[i - 1], 0, INF, x, 1, s);
            }
            else
            {
   
                root1[i] = insert(root1[i - 1], 0, n - 1, tot, x, s);
                root2[i] = insert(root2[i - 1], 0, INF, x, 1, s);
                root2[i] = insert(root2[i - 1], 0, INF, m[s], -1, s);
            }
            m[s] = x;
            tot ++ ;
        }
        else if (op == "remove")
        {
   
            cin >> ope[i].test;
            string s = ope[i].test;
            if (!query(root1[i - 1], 0, n - 1, tot, tot))
            {
   
                root1[i] = root1[i - 1];
                root2[i] = root2[i - 1];
                continue;
            }
            root1[i] = insert(root1[i - 1], 0, n - 1, nums[m[s]], m[s], s);
            root2[i] = insert(root2[i - 1], 0, INF, m[s], -1, s);
        }
        else if (op == "query")
        {
   
            cin >> ope[i].test;
            root1[i] = root1[i - 1];
            root2[i] = root2[i - 1];
            string s = ope[i].test;
            if (!query(root1[i - 1], 0, n - 1, tot, tot))
            {
   
                cout << -1 << '\n';
                cout << flush;
            }
            else
            {
   
                cout << query(root2[i], 0, m[s] - 1, 0, INF) << '\n';
                cout << flush;
            }
        }
        else
        {
   
            cin >> ope[i].x;
            int d = ope[i].x;
            root1[i] = root1[i - d - 1];
            root2[i] = root2[i - d - 1];
        }
    }
}

【数据结构】可持久化线段树（主席树）

文章目录

接下来是一道例题

再放一道标记永久化+主席树

再加一道主席树+在线处理

相关推荐

最近更新

热门阅读