权值线段树模板 / p1908

前言

权值线段树是解决区间出现个数的一个好工具

其实现结构与普通线段树无太大区别，所不同的是权值线段树所维护的是元素出现个数

此外还要加一个离散化防止数组越界

权值线段树支持以下功能：

全局查询第 k 大 \ 小，查询区间元素出现个数、单点更新、查询单点元素出现个数

模板里有前三者的功能函数，对于第四功能，可利用第二功能稍加修改即可

一、 例题

题目链接 洛谷p1908

二、 思路及代码 1. 思路

很经典的权值线段树例题，问题是求逆序对

我们知道 a n s = ∑ i = 1 n ∑ j = i + 1 n [ a i > a j ] ans = \sum_{i=1}^{n}\sum_{j=i+1}^{n}{[a_i>aj]} ans=i=1∑n​j=i+1∑n​[ai​>aj] 用权值线段树统计 ∑ j = i + 1 n [ a i > a j ] \sum_{j=i+1}^{n}{[a_i>aj]} ∑j=i+1n​[ai​>aj]是一件很容易的事情，

于是我们对query累加即可得到答案

注意：求逆序对时，离散化不需要去重

2. 代码

代码如下 ：

#include 
#include 
#define int long long
using namespace std;
const int maxn = 5e5 + 5;
struct vtree {
  int l, r;
  int v;
} t[maxn  1;
  build(root * 2, l, mid);
  build(root * 2 + 1, mid + 1, r);
}
void update(int root, int k) {  // 权值线段树仅支持单点更新
  if (t[root].l == t[root].r) {
    if (t[root].l == k) t[root].v++;
    return;
  }
  int mid = (t[root].r + t[root].l) >> 1;
  if (k