卸载前main：
本来早该学会的，但是肝硬化泰蒟蒻辣【确信】，于是今天才学会一点点，遂咕了很久现在才开始血………（duibuqi）
文学常识
-什么是主席树？
-主席树，也称为可持久化权值线段树，是一种数据结构，用于解决如静态区间第k小数等问题。它的核心思想是利用可持久化的特性，记录每次插入操作的历史版本，从而在不同版本间进行查询。
-你说得对，但是可持久化权值线段树为什么叫主席树？
-因为可持久化权值线段树的发明者是威风堂堂大名鼎鼎的黄嘉泰同志，在众多OIer的yy思考下发觉其首字母为 \(HJT\) ,遂将可持久化权值线段树称为主席树。
原理
可持久化权值线段树的究极奥义便是可持久，也就是支持回退操作，可以随时随地随心所欲随随便便地查询曾经的历史版本，那么我们应该如何完成这一操作呢？
-我们可以每次修改操作时就复制一棵线段树呀！
-好，现在我们有一棵 \(n\) 个节点的线段树，修改 \(m\) 次， \(n , m <= 10 ^ 5\) 。
-空间爆炸了欸！
-让我们动用人类智慧吧！
首先回顾一下曾经学过的普通线段树的单点修改，我们可以发现：
那么我们就可以每次只将这些需要修改的节点进行复制！
让我们一睹主席树の芳容↓
好丑。
其中 \(0,1,2\) 分别对应初始版本、第一次修改和第二次修改的节点。
我们又可以发现：
- 每次修改只会增加 \(log(n)\) 个节点（前面已经说了哦~）；
- 增加的非叶节点会连向一个曾经版本的节点和一个新节点。
- 主席树有很多根（数量取决于你想让它有多少个版本）；
- 每一个非根节点都可能有一堆爹（
n姓家奴）； - 每个根都可以构成一颗完整的线段树（一目了然）………
-都是非常有趣的性质呢！
-那么我们怎么建新节点？它的编号是多少？如何连边？怎样访问不同版本的节点？怎么存不同版本的根？
-直接新建一个数组下标为 \(总节点数+1\) 的点改成你要改的值然后结构体存它的左右儿子访问时直接找你存的左右儿子们根直接开个数组存。
-没听懂。
-对不起我们看看板子题吧喵。
板子题们
1.可持久化线段树
自家OJ的逆天题干
为什么说本题是福利呢？因为这是一道非常直白的可持久化线段树的练习题，目的并不是虐人，而是指导你入门可持久化数据结构。 线段树有个非常经典的应用是处理 \(RMQ\) 问题，即区间最大/最小值询问问题。现在我们把这个问题可持久化一下: "\(Q\) \(k\) \(l\) \(r\)" 查询数列在第 \(k\) 个版本时，区间 \([l,r]\) 上的最大值 "\(M\) \(k\) \(p\) \(v\)" 把数列在第 \(k\) 个版本时的第 \(p\) 个数修改为 \(v\) ，并产生一个新的数列版本。最开始会给你一个数列，作为第 $ 1$ 个版本。 每次 \(M\) 操作会导致产生一个新的版本………【其实全是废话不要再看了喵】
题目描述
第一行两个整数 $ N,Q$ 。 \(N\) 是数列的长度， \(Q\) 表示询问数。
第二行 $ N$ 个整数，是这个数列。
之后 \(Q\) 行，每行以 \(0\) 或者 \(1\) 开头，\(0\) 表示查询操 \(Q\) ， \(1\) 表示修改操作 \(M\) ，格式为"\(0\) \(k\) \(l\) \(r\)" 查询数列在第k个版本时，区间 \([l,r]\) 上的最大值 或者" \(1\) \(k\) \(p\) \(v\) " 把数列在第k个版本时的第 \(p\) 个数修改为 \(v\) ，并产生一个新的数列版本。
对于每个 \(M\) 询问，输出正确答案。
样例
输入
4 5
1 2 3 4
0 1 1 4
1 1 3 5
0 2 1 3
0 2 4 4
0 1 2 4 输出
4
5
4
4样例解释
序列版本1: \(1\) \(2\) \(3\) \(4\) ,
查询版本1的 \([1,4]\) 最大值为4;
修改产生版本2: \(1\) \(2\) \(5\) \(4\) ,
查询版本2的 \([1,3]\) 最大值为5;
查询版本1的 \([4,4]\) 最大值为4;
查询版本1的 \([2,4]\) 最大值为4.
数据范围
对于 \(100%\) 的数据，保证有\(N≤1×10^4,Q≤1×10^5\)
对于每次询问操作的版本号 \(k\) 保证合法，
区间 \([l,r]\) 一定满足 \(1≤l≤r≤N\) 。
Solve
纯血统主席树模版，原理前面已经说过了，直接放代码吧~
Code【马蜂诡异慎入】
#include <bits/stdc++.h>
using namespace std;
const int _ = 100010;
int n, q, bb, a[_], b[_], rt[_], op, x, y, z, num;
struct hhh{int ls, rs, v, mx;
}tree[_ << 5];inline int clone(int root){num ++;tree[num] = tree[root];return num;
}
inline void pushup(int root){tree[root]. mx = max(tree[tree[root]. ls]. mx, tree[tree[root]. rs]. mx);return ;
}
inline int build(int root, int l, int r){root = ++ num;if(l == r){tree[root]. v = tree[root]. mx = a[l];return num;}int mid = (l + r) >> 1;tree[root]. ls = build(tree[root]. ls, l, mid);tree[root]. rs = build(tree[root]. rs, mid + 1, r);pushup(root);return root;
}
inline int update(int root, int l, int r, int p, int v){root = clone(root);if(l == r){tree[root]. v = tree[root]. mx = v;return root;}int mid = (l + r) >> 1;if(p <= mid){tree[root]. ls = update(tree[root]. ls, l, mid, p, v);}else{tree[root]. rs = update(tree[root]. rs, mid + 1, r, p, v);}pushup(root);return root;
}
inline int query(int root, int l, int r, int x, int y){if(l >= x && r <= y){return tree[root]. mx;}if(l == r){return - 999999999;}int as = - 999999999;int mid = (l + r) >> 1;if(x <= mid){as = std::max(as, query(tree[root]. ls, l, mid, x, y));}if(y >= mid){as = std::max(as, query(tree[root]. rs, mid + 1, r, x, y));}return as;
}
int main(){scanf("%d%d", & n, & q);for(int i = 1; i <= n; i ++){scanf("%d", & a[i]);// b[i] = a[i];}//sort(b + 1, b + n + 1);
// int tot = unique(b + 1, b + n + 1) - b - 1;bb = 1;rt[bb] = build(rt[bb], 1, n);for(int i = 1; i <= q; i ++){scanf("%d%d%d%d", & op, & x, & y, & z);if(op == 0){printf("%d\n", query(rt[x], 1, n, y, z));}else{rt[++ bb] = update(rt[x], 1, n, y, z);}}return 0;
}
2.[BZOJ3207]花神的嘲讽计划
题目背景（一点用也没有）
花神是神，一大癖好就是嘲讽大J，举例如下：
“哎你傻不傻的！【hqz：大笨J】”
“这道题又被J屎过了！！”
“J这程序怎么跑这么快！J要逆袭了！”
……
描述
这一天DJ在给吾等众韶身讲题，花神在一边做题无聊，就跑到了一边跟吾等众韶身一起听。以下是部分摘录：
1.
“J你在讲什么！”
“我在讲XXX！”
“哎你傻不傻的！这么麻烦，直接XXX再XXX就好了！”
“……”
2.
“J你XXX讲过了没？”
“……”
“那个都不讲你就讲这个了？哎你傻不傻的！”
“……”
DJ对这种情景表示非常无语，每每出现这种情况，DJ都是非常尴尬的。
题目描述
\(DJ\) 对这种情景表示非常无语，每每出现这种情况， \(DJ\) 都是非常尴尬的。
经过众韶身研究， \(DJ\) 在讲课之前会有一个长度为 \(N\) 方案，我们可以把它看作一个数列；
同样，花神在听课之前也会有一个嘲讽方案，有 \(M\) 个，每次会在 \(x\) 到 \(y\) 的这段时间开始嘲讽，为了减少题目难度，每次嘲讽方案的长度是一定的，为 \(K\) 。
花神嘲讽 \(DJ\) 让 \(DJ\) 尴尬需要的条件：
在 \(x\) ~ \(y\) 的时间内 \(DJ\) 没有讲到花神的嘲讽方案，即J的讲课方案中的 \(x\) ~ \(y\) 没有花神的嘲讽方案【这样花神会嘲讽 \(J\) 不会所以不讲】。
经过众韶身努力，在一次讲课之前得到了花神嘲讽的各次方案， \(DJ\) 得知了这个消息以后欣喜不已， \(DJ\) 想知道花神的每次嘲讽是否会让 \(DJ\) 尴尬【说不出话来】。
第1行3个数 \(N，M，K\) ；
第2行N个数，意义如上；
第3行到第 \(3+M-1\) 行，每行 \(K+2\) 个数，前两个数为 \(x,y\) ,然后 \(K\) 个数，意义如上；
对于每一个嘲讽做出一个回答会尴尬输出" \(Yes\) "，否则输出" \(No\) "
样例
输入
8 5 3
1 2 3 4 5 6 7 8
2 5 2 3 4
1 8 3 2 1
5 7 4 5 6
2 5 1 2 3
1 7 3 4 5输出
No
Yes
Yes
Yes
No样例解释
\(2\)~\(5\)中有 \(2\) \(3\) \(4\) 的方案，输出 \(No\) ，表示 \(DJ\) 不会尴尬；
\(1\)~\(8\)中没有 \(3\) \(2\) \(1\) 的方案，输出 \(Yes\) ，表示 \(DJ\) 会尴尬；
\(5\)~\(7\)中没有 \(4\) \(5\) \(6\) 的方案，输出 \(Yes\) ，表示 \(DJ\) 会尴尬；
\(2\)~\(5\)中没有 \(1\) \(2\) \(3\) 的方案，输出 \(Yes\) ，表示 \(DJ\) 会尴尬；
\(1\)~\(7\)中有 \(3\) \(4\) \(5\) 的方案，输出 \(No\) ，表示 \(DJ\) 不会尴尬；
数据范围
题中所有数据不超过 \(2×10^9\) ;保证\(方案序列的每个数字<=N,n,m<=1e5,k<=20\)。
Solve
首先看到问是否有长度为 \(k\) 的相同子段，可以想到用Hash对序列进行前缀和处理，可以将连续的 \(k\) 个的Hash值作为一个元素，也就是说现在第 \(i\) 个元素表示 \({i...i+K-1}\) 这段区间的Hash值。
判断是否有解就是先判断区间长度是否大于 \(k\) ，给定串的Hash值是否在原串出现过，再在对应区间主席树里面查找是否存在，如果有任意一个不成立那就输出 \(Yes\) （不要学我搞反调了半天），都成立就是 \(No\) 。
查找是否存在就是找第 \(y-k+1\) 和第 \(x-1\) 棵树在该值位置的数量之差是否大于0。
然后处理Hash值用自然溢出即可，可以再做一个离散化。
样例经过这样操作得到的主席树是这样的↓
（你哪来这么多的人造主席树）
Code
#include <bits/stdc++.h>
using namespace std;
const int _ = 1e5 + 10;
int num, tot, n, m, k, rt[_], x, y, c[_], h;
unsigned long long p[_], ha, hs[_], a[_], b[_];
inline unsigned long long gh(int l, int r){return hs[r] - (hs[l - 1] * p[r - l + 1]);
}
struct hhh{int ls, rs, v;
}tree[_ << 5];
inline int clone(int root){num ++;tree[num] = tree[root];return num;
}
inline int update(int root, int l, int r, int pl, int v){root = clone(root);tree[root]. v += v;if(l == r){return root;}int mid = (l + r) >> 1;if(pl <= mid){tree[root]. ls = update(tree[root]. ls, l, mid, pl, v);}else{tree[root]. rs = update(tree[root]. rs, mid + 1, r, pl, v);}return root;
}
inline int query(int ra, int rb, int l, int r, int pl){//cout<<"MI";if(l == r){return tree[ra]. v - tree[rb]. v;}int mid = (l + r) >> 1;if(pl <= mid){return query(tree[ra]. ls, tree[rb]. ls, l, mid, pl);}else{return query(tree[ra]. rs, tree[rb]. rs, mid + 1, r, pl);}
}
inline int find(unsigned long long x){int l = 1, r = tot;while(l < r){int mid = (l + r) >> 1;if(x <= b[mid])r = mid;elsel = mid + 1;}return b[l] == x ? l : 0;
}
int main(){scanf("%d%d%d", & n, & m, & k);p[0] = 1;p[1] = 1331;for(int i = 2; i <= n; i ++){p[i] = p[i - 1] * p[1];}for(int i = 1; i <= n; i ++){scanf("%d", & c[i]);hs[i] = hs[i - 1] * p[1] + c[i];}for(int i = 1; i <= n - k + 1; i ++){a[i] = b[i] = gh(i, i + k - 1);}sort(b + 1, b + n + 1);for(int i = 1; i <= n; i ++){if(b[i] != b[i - 1]){b[++ tot] = b[i];}}for(int i = 1; i <= n; i ++){a[i] = find(a[i]);}for(int i = 1; i <= n - k + 1; i ++){rt[i] = update(rt[i - 1], 1, tot, a[i], 1);}for(int i = 1; i <= m; i ++){scanf("%d%d", & x, & y);ha = 0;for(int i = 1; i <= k; i ++){scanf("%d", & h);ha = ha * p[1] + h;}// cout<<ha<<' ';ha = find(ha);// cout<<ha;if(y - x + 1 < k || ! ha || ! query(rt[y - k + 1], rt[x - 1], 1, tot, ha)){printf("Yes\n");}else{printf("No\n");}}
// for(int i = 1; i <= tot; i ++){
// cout<<a[i]<<' ';
// }return 0;
}