关键词：
显然只能有$hash$来做....
我们需要一个东西来维护$sum i * seed^rank[i]$
很自然地联想到平衡树
如果以序列下标建立一棵平衡树，那么无法处理
因此，可以以权值为下标建立一棵平衡树，把$rank[i]$拆分成若干个$sz[ls] + 1$即可维护
具体而言，记$pos[i]$表示$i$号节点的位置，$sum[i]$表示平衡树中$i$号节点的子树形成的$hash$值
那么，$sum[i] = pos[i] * seed^sz[ls] + 1 + sum[ls] + sum[rs] * seed^sz[ls] + 1$
首先预处理出所有$A$串的$hash$值，存进$map$中
处理时，注意$[1, m]$和$[2, m + 1]$的串在平衡树中的$hash$值会有一个增量的区别
由于元素两两不同，因此可以确定增量为$sum seed^i$
之后，每次动态地维护$B$串的$hash$值，查询即可
下面的代码由于插入了$-1$，因此更新时略有不同...
复杂度$O(n log n)$
#include <map> #include <cstdio> #include <cstring> using namespace std; #define ll long long #define ri register int #define ull unsigned long long #define rep(io, st, ed) for(ri io = st; io <= ed; io ++) #define drep(io, ed, st) for(ri io = ed; io >= st; io --) #define gc getchar inline int read() int p = 0; char c = gc(); while(c > ‘9‘ || c < ‘0‘) c = gc(); while(c >= ‘0‘ && c <= ‘9‘) p = p * 10 + c - ‘0‘, c = gc(); return p; const int sid = 500050; const int seed = 19260817; ll val[sid]; map <ull, int> ans; int n, m, q, rt, id, A[sid], B[sid]; ull pos[sid], sum[sid], wei[sid]; int s[sid][2], sz[sid], fa[sid]; inline bool isrc(int o) return s[fa[o]][1] == o; inline void upd(int o) int ls = s[o][0], rs = s[o][1]; sz[o] = sz[ls] + sz[rs] + 1; sum[o] = wei[sz[ls]] * pos[o] + sum[ls] + wei[sz[ls] + 1] * sum[rs]; inline void rotate(int o) int f = fa[o], g = fa[f]; int ro = isrc(o), rf = isrc(f); fa[o] = g; if(g) s[g][rf] = o; s[f][ro] = s[o][ro ^ 1]; fa[f] = o; fa[s[o][ro ^ 1]] = f; s[o][ro ^ 1] = f; upd(f); upd(o); inline void splay(int o, int tar) while(fa[o] != tar) int f = fa[o], g = fa[f]; if(g != tar) rotate(isrc(o) == isrc(f) ? f : o); rotate(o); if(!tar) rt = o; inline void insert(ll v, int w) int o = rt, f = 0; while(o) f = o, o = s[o][v > val[o]]; o = ++ id; if(f) s[f][v > val[f]] = o; fa[o] = f; sz[o] = 1; val[o] = v; pos[o] = w; sum[o] = w; splay(o, 0); inline void find(ll v) int o = rt; while(s[o][v > val[o]] && val[o] != v) o = s[o][v > val[o]]; splay(o, 0); inline void erase(int v) find(v); int pre = s[rt][0], suf = s[rt][1]; while(s[pre][1]) pre = s[pre][1]; while(s[suf][0]) suf = s[suf][0]; splay(pre, 0); splay(suf, pre); s[suf][0] = 0; if(suf) upd(suf); if(pre) upd(pre); inline void Hash() ull exa = 0; wei[0] = 1; rep(i, 1, m + 5) wei[i] = wei[i - 1] * seed; rep(i, 1, m) exa += wei[i]; insert(-1, 0); insert(2147483648, 0); rep(i, 1, m) insert(A[i], i); rep(i, m, n) ans[sum[rt] - exa * (i - m)] ++; if(i == n) break; erase(A[i - m + 1]); insert(A[i + 1], i + 1); rt = 0; rep(i, 1, id) s[i][0] = s[i][1] = sz[i] = 0; val[i] = sum[i] = fa[i] = 0; id = 0; int main() n = read(); m = read(); q = read(); rep(i, 1, n) A[i] = read(); Hash(); insert(-1, 0); insert(2147483648, 0); rep(i, 1, m) B[i] = read(); rep(i, 1, m) insert(B[i], i); rep(i, 1, q) int x = read(), c = read(); erase(B[x]); insert(B[x] = c, x); printf("%d ", ans[sum[rt]]); return 0;
luogup3391文艺平衡树
二次联通门: luoguP3391文艺平衡树 /*luogu3391文艺平衡树splay区间翻转每次翻转区间[l,r]都是把l旋到根节点上，r旋到根节点的右节点上那么要修改的区间就是根节点的右孩子的左子树然后打标记。。之后每次查... 查看详情
替罪羊树------luogup3369模板普通平衡树（treap/sbt）
二次联通门: luoguP3369【模板】普通平衡树（Treap/SBT） 闲的没事，把各种平衡树都写写比较比较。。。 下面是替罪羊树 #include<cstdio>#include<vector>#defineMax_100010#defineInline__attriute__((optimize("-O2")) 查看详情
红黑树------luogup3369模板普通平衡树（treap/sbt）
二次联通门: luoguP3369【模板】普通平衡树（Treap/SBT）近几天闲来无事。。。就把各种平衡树都写了一下。。。下面是红黑树(RedBlackTree) #include<cstdio>#defineMax100001#defineRedtrue#defineBlackfalse#defineInline__attri 查看详情
luogup3369普通平衡树(代码片段)
luoguP3369主要是贴一个splay的模板：#include<bits/stdc++.h>usingnamespacestd;namespacesplay#definels(x)ch[x][0]#definers(x)ch[x][1]constintN=1000005;constintinf=2e9;intch[N][2],f[N],key[N],nums[N],sz[N];i 查看详情
luogup3391[模板]文艺平衡树(splay)题解(代码片段)
链接一下题目：luoguP3391[模板]文艺平衡树(Splay)#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<cstring>#include<iomanip>#include<algorithm>#inclu 查看详情
数组splay------luogup3369模板普通平衡树（treap/sbt）
二次联通门: luoguP3369【模板】普通平衡树（Treap/SBT） #include<cstdio>#defineMax100005#defineInline__attriute__((optimize("-O2")))Inlinevoidread(int&now){now=0;registercharword 查看详情
luogup3369模板普通平衡树(代码片段)
解法就是最普通的splay啦，直接放代码QAQ代码#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<cmath>#defineINF0x3f3f3f3fusingnamespacestd;typedeflonglongLL;cons 查看详情
luogup3919[模板]可持久化数组(可持久化线段树/平衡树)(主席树)(代码片段)
luoguP3919[模板]可持久化数组(可持久化线段树/平衡树)题目#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<cstring>#include<iomanip>#include<algorithm>#inc 查看详情
luogup3369[模板]普通平衡树(treap/sbt)题解(代码片段)
链接一下题目：luoguP3369[模板]普通平衡树(Treap/SBT)#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<cstring>#include<iomanip>#include<algorithm>#i 查看详情
fhqtreap------luogup3369模板普通平衡树（treap/sbt）
二次联通门: LibreOJ#104.普通平衡树 #include<cstdio>#include<iostream>#include<algorithm>constintBUF=12312323;charBuf[BUF],*buf=Buf;inlinevoidread(int&now){boolt 查看详情
luogup3369普通平衡树|二叉搜索树（然而被卡了一个点）
题目链接平衡树板子题。然后写了一棵不会自动平衡的普通二叉搜索树（想了解二叉搜索树的同学可以看看这篇文章）。结果一共12个点跑过了11个点，最后一个点是在树中插入了一个有序数列卡掉的。可见二叉搜索树在随机数... 查看详情
「luogup3369」模板普通平衡树（用vector乱搞平衡树(代码片段)
Description您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：插入x数删除x数(若有多个相同的数，应只删除一个)查询x数的排名(排名定义为比当前数小的数的个数。若有多个相同的数，因输出最... 查看详情
[luogup3369]模板普通平衡树（treap/sbt）
[luoguP3369]【模板】普通平衡树（Treap/SBT）题目描述您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：插入x数删除x数(若有多个相同的数，因只删除一个)查询x数的排名(排名定义为比当前数小的... 查看详情
luogup3835模板可持久化平衡树(代码片段)
P3835【模板】可持久化平衡树题意题目背景本题为题目普通平衡树的可持久化加强版。题目描述您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作（对于各个以往的历史版本）：插入(x)数删除(x)... 查看详情
题解luogup1503鬼子进村(代码片段)
平衡树好题原题传送门这道题要用Splay，我博客里有对Splay的详细介绍这道题思维有点难，要把被摧毁的节点插入平衡树，而不是把没有摧毁的节点插入先把0和n+1插入平衡树，作为边界操作1：摧毁节点，把该点插入平衡树操作2... 查看详情
对于各种各样平衡树的比较
...样烂大街的就不比了) 二次联通门: 数组splay------luoguP3369【模板】普通平衡树（Treap/SBT）二次联通门: 替罪羊树------luoguP3369【模板】普通平衡树 查看详情
luogup2310loidc,看看海(代码片段)
各位大佬都用的排序和杨颙大定理，蒟蒻的我怎么也不会做（瑟瑟发抖），那么，就来一发主席树吧。我们知道线段树可以维护区间，平衡树可以维护值域那么，我们可以用线段树套平衡树来解决这个区间值域的问题线段树套平... 查看详情
平衡树
intmerge(intp1,intp2){//合并两棵treapif(!p1)returnp2;if(!p2)returnp1;if(z[p1].key<z[p2].key){z[p1].r=merge(z[p1].r,p2);returnp1;}else{z[p2].l=merge(p1,z[p2].l);returnp2;}}pair<int,int>split(intp, 查看详情