权值线段树、主席树
前言
拖了很久，就因为少看了一句话理解不了 T^T
权值线段树看上去名字高大上，其实就是以值为下标的线段树
主席树是可持久化权值线段树，但是后来我们就不理了，可持久化线段树全都写成主席树。所谓可持久化，就是保存了历史版本，所以这是黑科技呀！(⊙o⊙)
- 线段树：
电子科大 —— 算法讲堂 《权值线段树 主席树》
https://www.bilibili.com/video/av16552942?from=search&seid=7293261633840621022 - 主席树：
http://www.yhzq-blog.cc/%e4%b8%bb%e5%b8%ad%e6%a0%91%e5%ad%a6%e4%b9%a0%e6%80%bb%e7%bb%93/
https://www.cnblogs.com/zyf0163/p/4749042.html
一些思考
1.求任意区间不同数的和
其实十分像后缀数组，个人认为其思想是 “前缀的后缀可以表示任意子串”
Minimum Inversion Number - HDU - 1394
题意
求序列循环位移中逆序对数量最小值
思路
权值线段树
动态插入，这时比这个数大的数的数量即为新增的逆序对，累加后再处理循环位移的问题
循环位视为将最后一个数搬到最开始，答案的改变为 - (n – 末尾数 - 1) (即 末尾数 + 1 ~ n - 1) + (末尾数)（即 0 ~ 末尾数-1）
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const int N = 5e3 + 15;
int a[N];
int sum[N << 2];
inline void init(){
memset(sum, 0, sizeof(sum));
}
void pushUp(int rt){ sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
void push(int val, int l, int r, int rt){
if(l == r){
sum[rt]++;
return;
}
int m = (l + r) >> 1;
if(val <= m) push(val, lson);
else push(val, rson);
pushUp(rt);
}
int query(int ql, int l, int r, int rt){
if(ql <= l){
return sum[rt];
}
int ans = 0;
int m = (l + r) >> 1;
if(ql <= m) ans += query(ql, lson);
ans += query(ql, rson); //右端点是n，故每次都查询右子树
return ans;
}
int main(){
int n;
while(~scanf("%d", &n)){
init();
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
a[i]++;
}
int ans_tmp = 0, ans = 0;
for(int i = 0; i < n; i++){
push(a[i], 1, n, 1);
ans_tmp += query(a[i] + 1, 1, n, 1);
}
ans = ans_tmp;
for(int i = n - 1; i > 0; i--){
ans_tmp = ans_tmp + (a[i]) - (n - a[i] – 1);
ans = min(ans, ans_tmp);
}
printf("%d\n", ans);
}
}
KPI - HDU - 5249
思路
离散化 + 权值线段树
数字过大，不能直接用下标，所以先离散化
因为离散化，只能转离线了
最后求中位数就是求第 sum/2 + 1 小数
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const int N = 1e4 + 15;
int sum[N << 2];
int op_num[N], op[N]; //op_num为操作数，op是操作
int mp[N];
int n, m;
queue<int> que;
inline void init(){
memset(sum, 0, sizeof(sum));
n = m = 0;
while(!que.empty()) que.pop();
}
void pushUp(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
void setVal(int p, int val, int l, int r, int rt){
if(l == r){
sum[rt] = val;
return;
}
int m = (l + r) >> 1;
if(p <= m) setVal(p, val, lson);
else setVal(p, val, rson);
pushUp(rt);
}
int query(int k, int l, int r, int rt){
if(l == r){
return l;
}
int m = (l + r) >> 1;
if(k <= sum[rt << 1]) return query(k, lson);
else return query(k - sum[rt << 1], rson);
}
int main(){
int q;
int csn = 1;
while(~scanf("%d", &q)){
init();
while(q--){
char strop[10];
int num;
scanf("%s", strop);
if(strop[0] == 'i'){ //insert操作对应0
scanf("%d", &num);
mp[m++] = num;
que.push(num);
op_num[n] = num;
op[n++] = 0;
}else if(strop[0] == 'q'){ //query操作对应2
op_num[n] = -1;
op[n++] = 2;
}else if(strop[0] == 'o'){ //out操作对应1
int tmp = que.front();
que.pop();
op_num[n] = tmp;
op[n++] = 1;
}
}
sort(mp, mp + m);
printf("Case #%d:\n", csn++);
for(int i = 0; i < n; i++){
int p;
if(op[i] == 0){
p = lower_bound(mp, mp + m, op_num[i]) - mp;
setVal(p + 1, 1, 1, m, 1); //插入即设置为1，求和
}else if(op[i] == 1){
p = lower_bound(mp, mp + m, op_num[i]) - mp;
setVal(p + 1, 0, 1, m, 1); //删除即设置为0，求和
}else{
p = sum[1]/2 + 1; //求中位数，即第sum[1]/2 + 1个数
int loc = query(p, 1, m, 1);
printf("%d\n", mp[loc - 1]);
}
}
}
}
Kth number - HDU - 2665
题意
求某个区间的第k小数
思路
主席树（可持续化权值线段树） + 离散化
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson l, m
#define rson m + 1, r
using namespace std;
const int N = 1e5 + 15;
int mp[N], a[N];
int tot;
int sum[N*20], root[N*20], ls[N*20], rs[N*20]; //ls为左孩子，rs为右孩子，root为每棵树的根
inline void init(){
mp[0] = a[0] = 0;
tot = 1;
}
void build(int& o, int l, int r){ //建立空树
o = tot++;
sum[o] = 0;
if(l == r) return;
int m = (l + r) >> 1;
build(ls[o], lson);
build(rs[o], rson);
}
void update(int& o, int pre, int l, int r, int p){ //只修改变化的子树，剩下相连
o = tot++;
ls[o] = ls[pre];
rs[o] = rs[pre];
sum[o] = sum[pre] + 1;
if(l == r) return;
int m = (l + r) >> 1;
if(p <= m) update(ls[o], ls[pre], lson, p);
else update(rs[o], rs[pre], rson, p);
}
int query(int ss, int tt, int l, int r, int k){
if(l == r) return l;
int m = (l + r) >> 1;
int lson_sum = sum[ls[tt]] - sum[ls[ss]]; //以差值建树
if(k <= lson_sum) query(ls[ss], ls[tt], lson, k);
else query(rs[ss], rs[tt], rson, k - lson_sum);
}
int main(){
int t;
scanf("%d", &t);
while(t--){
init();
int n, q;
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
mp[i] = a[i];
}
sort(mp + 1, mp + n + 1);
int sz = unique(mp + 1, mp + n + 1) - (mp + 1);
build(root[0], 1, sz);
for(int i = 1; i <= n; i++){
int p = lower_bound(mp + 1, mp + sz + 1, a[i]) - mp;
update(root[i], root[i - 1], 1, sz, p); //从上一棵树建树
}
while(q--){
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
int p = query(root[l - 1], root[r], 1, sz, k); //[1, r] – [1, l - 1] = [l, r]
printf("%d\n", mp[p]);
}
}
return 0;
}
Turing Tree - HDU - 3333
题意
求某个区间内不重复元素和
思路
主席树（可持续化线段树），也可以用莫队写
对区间[1, r]建树，每次插入数，当该数没出现过时直接插入，出现过时删掉上次的，再插入这一次的， 删除和插入操作都是新开树进行的，即历史版本之一
最后对于查询的[l, r]，查询root[r]中的[l, r]区间即可，即前缀的后缀
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson l, m
#define rson m + 1, r
using namespace std;
const int N = 3e4 + 15;
typedef long long ll;
int pre_pos[N];
ll mp[N], a[N];
int tot;
ll sum[N*40];
int root[N*40], ls[N*40], rs[N*40];
inline void init(){
memset(pre_pos, 0, sizeof(pre_pos));
mp[0] = a[0] = 0;
tot = 1;
}
void build(int& o, int l, int r){
o = tot++;
sum[o] = 0;
if(l == r) return;
int m = (l + r) >> 1;
build(ls[o], lson);
build(rs[o], rson);
}
void update(int& o, int pre, int l, int r, ll val, int p){
o = tot++;
ls[o] = ls[pre];
rs[o] = rs[pre];
sum[o] = sum[pre] + val;
if(l == r) return;
int m = (l + r) >> 1;
if(p <= m) update(ls[o], ls[pre], lson, val, p);
else update(rs[o], rs[pre], rson, val, p);
}
ll query(int o, int ql, int qr, int l, int r){
if(ql <= l && r <= qr){
return sum[o];
}
ll ans = 0;
int m = (l + r) >> 1;
if(ql <= m) ans += query(ls[o], ql, qr, lson);
if(m < qr) ans += query(rs[o], ql, qr, rson);
return ans;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
init();
int n, q;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
mp[i] = a[i];
}
sort(mp + 1, mp + n + 1);
int sz = unique(mp + 1, mp + n + 1) - (mp + 1);
build(root[0], 1, n);
for(int i = 1; i <= n; i++){
int pp = lower_bound(mp + 1, mp + 1 + sz, a[i]) - mp;
if(pre_pos[pp]){
int tmp; //开一棵临时的树过渡，其也是历史版本
update(tmp, root[i - 1], 1, n, -a[i], pre_pos[pp]);
update(root[i], tmp, 1, n, a[i], i);
}else{
update(root[i], root[i - 1], 1, n, a[i], i);
}
pre_pos[pp] = i;
}
scanf("%d", &q);
while(q--){
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", query(root[r], l, r, 1, n));
}
}
return 0;
}
