P3939 数颜色 主席树板子

😊 | Powered By HeartFireY

Problem Analysis

题目大意： 给定一个序列，支持以下操作：

1. 查询给定区间 [ l ， r ] [l， r] [l，r]内 v a l val val的个数；
2. 交换第 x x x和 x + 1 x + 1 x+1只兔子的颜色。

首先考虑建权值数组，也就是对于每个颜色维护一棵主席树，然后操作就是一个普通的单点查询，直接树上二分到叶节点即可(可以考虑离散化)。

对于交换 x x x和 x + 1 x + 1 x+1颜色的操作，不难证明对于主席树而言，受影响的的版本只有 r o o t [ x ] root[x] root[x]，而对于 r o o t [ x + 1 ] root[x + 1] root[x+1]，交换颜色后，权值数组并没有发生什么变化(交换后两个数仍然位于 [ 1 , x + 1 ] [1,x+1] [1,x+1]范围内，位置不影响权值数组)。

对于 r o o t [ x ] root[x] root[x]版本，我们只需要将 x x x的颜色权值 − 1 -1 −1，然后将 x + 1 x + 1 x+1的颜色权值 + 1 +1 +1即可。非常模板。

Attention：千万千万不要用cin和cout，快读换成scanf也能过，但是cin和cout的IO会T的飞起。。。

Accepted Code

#include 
using namespace std;

const int N = 3e5 + 10;
 
int tot = 0, root[N], sum[N