python

6.3 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##POJ 2761 Feed the dogs

一、题目描述

Jiajia 要投喂 n 条狗，每条狗都有一个 漂亮指数，指数越小代表越漂亮。饭点让狗狗按编号顺序排成一排，投喂 m 次。每次选择 [i, j] 区间的第 k 漂亮的狗喂食。区间可能会存在重叠，但不会存在被另一个区间完全包含的区间。 n<100001, m<50001

二、题目解析

1、主席树经典解法

#include <cstdio>
#include <algorithm>
using namespace std;
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

const int N = 2e5 + 10;
int n, m;
int a[N], b[N], bl; // b和bl是一组，用于离散化的数组,bl为b的数组中有用数字的个数，一般下标0不放东西

struct Node {
    int l, r, cnt;
} tr[N << 5];
int root[N], idx;

//用于离散化的二分查找
int find(int x) {
    return lower_bound(b + 1, b + 1 + bl, x) - b;
}
//经典的主席树插入
void insert(int &u, int l, int r, int x) {
    tr[++idx] = tr[u]; //新开一个节点idx++,将新节点指向旧的tr[u]
    tr[idx].cnt++;     //新节点的cnt，因为多插入了一个数字，所以个数+1,这样处理的话，省去了pushup
    u = idx;           //因为是地址引用，需要回写u等于idx

    if (l == r) return; //如果已经到了叶子节点，上面的操作就足够了，可以直接返回，否则需要继续向下递归

    int mid = (l + r) >> 1;
    if (x <= mid)
        insert(tr[u].l, l, mid, x); //因为tr[u]进入本函数时，最先把旧的复制过来，所以tr[u].l也是上一个版本的左儿子节点
    else
        insert(tr[u].r, mid + 1, r, x);
}
// p:前面的版本，q:后面的版本,[l,r]：控制的范围
// k:要查找第k小的数字
int query(int p, int q, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    if (k <= cnt)
        return query(tr[p].l, tr[q].l, l, mid, k);
    else
        return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}
/*
答案：
3 2
*/
int main() {
//文件输入输出
#ifndef ONLINE_JUDGE
    freopen("POJ2761.in", "r", stdin);
#endif
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        a[i] = b[i] = read();

    //数据范围太大，直接建线段树会MLE，但是比较稀疏，可以离散化后用相对应的序号，数据量就小了
    sort(b + 1, b + 1 + n);
    bl = unique(b + 1, b + 1 + n) - b - 1; //离散化后共m个数字

    // 0号版本没有内容时，主席树是不需要进行build的,强行build时，可能会有部分测试点TLE
    // 0号版本有内容时，主席树是需要build的，不build，初始值无法给上

    // 主席树的数字增加，每增加一个，就相当于增加了一个版本root[i]记录了版本i的根节点
    for (int i = 1; i <= n; i++) {
        root[i] = root[i - 1];              //开新版本号i,抄袭上一个版本i-1的根节点
        insert(root[i], 1, bl, find(a[i])); //向版本i中增加find(a[i])的值
    }

    while (m--) {
        int l, r, k;
        l = read(), r = read(), k = read();
        //采用类似于前缀的方法，对位相减，由于是动态开点，需要指明控制范围[1,bl]
        //要查询的数字是k
        printf("%d\n", b[query(root[l - 1], root[r], 1, bl, k)]);
    }

    return 0;
}

树状数组 + 尺取法

`Treap`解法

`SBT`解法

划分树+归并树

https://www.acwing.com/solution/content/51456/

// 树状数组解法 // https://blog.csdn.net/auto_ac/article/details/8494268 // https://blog.csdn.net/neweryyy/article/details/104518201

// Treap解法 // https://www.cnblogs.com/justPassBy/p/4869692.html

// SBT 解法 // https://blog.csdn.net/behappyxiang/article/details/9921349

分块

二分套线段树

主席树

二分套线段树套 splay（支持修改）

整体二分视频讲解

思路

实现

树状数组+整体二分 `O(nlog^2n)` 整体二分的入门题

换一个角度思考问题。将数组从小到大排序，同时记录每个值原来的下标。例如样例排完序后的二元组就是 (1, 1), (2, 3), (3, 5), (4, 7), (5, 2), (6, 4), (7, 6)。

二元组第一个数字为数值，第二个数字为原来的下标。

考虑一个询问 [q.l, q.r, q.k]，我们进行二分答案然后判定。假设当前的二分区间为 [L, R]，二分某个位置 mid，我们可以在线性时间内统计数组 [L, mid] 中，有多少个数字的原下标位于区间 [q.l, q.r] 中，不妨记为 t。如果 q.k <= t ，则需要继续二分区间 [L, mid]。否则，q.k -= t，然后二分区间 [mid + 1, R]。

对于多个询问，同样可以采取这样的策略。我们在二分的过程中，将被询问区间分成两类，一类继续二分左区间，一类继续二分右区间。这里需要注意的是，我们不能使用普通前缀和数组进行统计（即扫一遍 1 到 n 求前缀和），而是使用树状数组动态维护前缀和。具体得，每次二分时，扫描区间 [L, mid] 的所有数字，对每个数字的原下标 x，在树状数组上 update(x, 1)。对于集合 [l, r] 内的每个询问，求 query(q[i].r) - query(q[i].l - 1) 记为 t，然后根据 t 和 k 的关系将区间分为两类，然后继续递归求解两个区间。

递归函数中大写的 L, R 表示排序后数组上的区间，l, r 表示询问集合的区间。q[i].l, q[i].r 表示第 i 个询问的区间。

时间复杂度 不妨假设询问和数组长度同阶，则递归表达式为 T(n)=2T(n/2)+O(nlogn)，故时间复杂度为 O(nlog2n)。

6.3 KiB Raw Permalink Blame History Unescape Escape