C/C++教程

【Coel.解题报告】【权值线段树初探】三元上升子序列

本文主要是介绍【Coel.解题报告】【权值线段树初探】三元上升子序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题前闲话

第一次写绿题解题报告,多少有点膈应quq
反正这个也是主席树和树套树的前置操作,就当是水博客了!
反正整个五月也没写几个博客

题目简介

洛谷传送门
最近洛谷出了个一键复制 markdown 的功能,这下方便多了!

题目描述

Erwin 最近对一种叫 thair 的东西巨感兴趣。。。

在含有 \(n\) 个整数的序列 \(a_1,a_2,\ldots,a_n\) 中,三个数被称作thair当且仅当 \(i<j<k\) 且 \(a_i<a_j<a_k\)。

求一个序列中 thair 的个数。

输入格式

开始一行一个正整数 \(n\),

以后一行 \(n\) 个整数 \(a_1,a_2,\ldots,a_n\)。

输出格式

一行一个整数表示 thair 的个数。

解题思路

根据乘法原理,不难发现,一个的 thair 就等于比它小且在前面的数个数乘上在它后面且比它大的数的个数。
比如对于样例:

\[2, 1, 3, 4 \]

数字 \(3\) 的 thair 就等于 \(2\times1=2\)。
因此,我们可以维护一个权值线段树,每次插入一个数,并记录下它的 thair,最后计算结果即可。


简单科普一下什么是权值线段树。
对一个数列 \(a\) 构造数列 \(b\) ,其中 \(b_i\) 表示 \(i\) 的出现次数,那么 \(b\) 就是 \(a\) 的权值数列。(其实就和桶排序的桶差不多)
对权值数列构造线段树,得到的就是权值线段树了。


考虑到要记录两个数(一个大于一个小于),我们需要建立两个权值线段树,当然也可以记录完一个数据之后清空线段树。

代码实现

首先肯定要先做一个离散化,不然值域太大没法直接开权值线段树。

void get_hash() {
    memcpy(t, a, sizeof(t));//开一个临时数组放排序加去重
    sort(t + 1, t + n + 1);
    int* end = unique(t + 1, t + n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(t + 1, end, a[i]) - t;//一个个放进原数组里面
}

接下来是权值线段树的查询和修改,方法和普通线段树大同小异。

int query(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y)
        return s[id];
    int mid = (l + r) >> 1, res = 0;
    if (mid >= x)
        res += query(id * 2, l, mid, x, y);
    if (mid < y)
        res += query(id * 2 + 1, mid + 1, r, x, y);
    return res;
}

void modify(int id, int l, int r, int v) {
    if (l == r && l == v)
        return s[id]++, (void)Flannelette;//做一个简写
    int mid = (l + r) >> 1;
    if (mid >= v)
        modify(id * 2, l, mid, v);
    else
        modify(id * 2 + 1, mid + 1, r, v);
    pushup(id);
}

最后是主函数的查询和修改,就放到完整代码里面了。
完整代码如下:

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>

#define int long long

#define Flannelette 0x00000000

const int maxn = 3e4 + 10;

namespace __Coel_FastIO {
#ifndef LOCAL
#define _getchar_nolock getchar_unlocked
#define _putchar_nolock putchar_unlocked
#endif
inline int read() {
    int x = 0, f = 1;
    char ch = _getchar_nolock();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = _getchar_nolock();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = _getchar_nolock();
    }
    return x * f;
}
inline void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    static int buf[35];
    int top = 0;
    do {
        buf[top++] = x % 10;
        x /= 10;
    } while (x);
    while (top)
        _putchar_nolock(buf[--top] + '0');
}
}  // namespace __Coel_FastIO

using namespace std;
using namespace __Coel_FastIO;

int n = read(), a[maxn], t[maxn];
int s[maxn * 4];
int ans, gre[maxn], les[maxn];

void get_hash() {
    memcpy(t, a, sizeof(t));
    sort(t + 1, t + n + 1);
    int* end = unique(t + 1, t + n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(t + 1, end, a[i]) - t;
}

void pushup(int id) {
    s[id] = s[id * 2] + s[id * 2 + 1];
}

int query(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y)
        return s[id];
    int mid = (l + r) >> 1, res = 0;
    if (mid >= x)
        res += query(id * 2, l, mid, x, y);
    if (mid < y)
        res += query(id * 2 + 1, mid + 1, r, x, y);
    return res;
}

void modify(int id, int l, int r, int v) {
    if (l == r && l == v)
        return s[id]++, (void)Flannelette;
    int mid = (l + r) >> 1;
    if (mid >= v)
        modify(id * 2, l, mid, v);
    else
        modify(id * 2 + 1, mid + 1, r, v);
    pushup(id);
}

signed main(void) {
    for (int i = 1; i <= n; i++)
        a[i] = read();
    get_hash();
    for (int i = 1; i <= n; i++) {
        if (a[i] > 1)
            les[i] = query(1, 1, n, 1, a[i] - 1);
        modify(1, 1, n, a[i]);
    }
    memset(s, 0, sizeof(s));
    for (int i = n; i >= 1; i--) {
        if (a[i] < n)
            gre[i] = query(1, 1, n, a[i] + 1, n);
        modify(1, 1, n, a[i]);
    }
    for (int i = 1; i <= n; i++)
        ans += 1LL * gre[i] * les[i];
    write(ans);
    return 0;
}
这篇关于【Coel.解题报告】【权值线段树初探】三元上升子序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!