←_←

题目链接题意给你 nnn 个模式串，qqq 次查询，每次查询 l,r,kl,r,kl,r,k，问第 kkk 个字符串在第 [l,r][l,r][l,r] 区间的模式串中出现多少次。思路首先思考一个模式串 sss 对全部串的贡献如何求？对 sss 的所有前缀跳 fail 链，对所有经过的模式串终点都有1点贡献，因为当前节点属于 sss 串前缀而经过的模式串终点则是 sss 串后缀。所以可...

题目链接题意n个整数的数列，多组询问，求区间减去一个值后绝对值的第k小。思路区间第K小主席树就行，这题要求减去一个值后绝对值第k小原先想着二分找到最接近0的左右k个元素，但是这样复杂度多了一个K有点大。可以二分答案，如果p-mid,p+mid区间内元素等于k个说明mid是答案，区间元素个数大于等于k作为判断条件具有单调性，可以据此二分，这样就优化掉了一个k。代码#include&lt...

题目链接思路用可持久化数组维护历史版本的 fa 父亲数组和 dep 树深度数组，以树深按秩合并。代码#include <stdio.h>const int maxn = 2e5+5;int n, m;struct Node{ int l, r, val;}h[maxn*80];int cnt, rootfa[maxn], rootdep[maxn], t...

题目链接题意给数组加个时间版本，维护数组的每个版本的值思路用可持久化线段树维护数组即可。代码#include <bits/stdc++.h>using namespace std;#define ll long longint root[1000005], tot = 0;struct Node{ int l, r, num;}t[(1000005&...

题目链接思路设 s[i]s[i]s[i] 为 aaa 序列的前 iii 个值得异或和异或和，满足前缀和求区间异或值的性质。那么每次查询 l,r,xl,r,xl,r,x ，答案即 ∑i=lrmin(S[n]⊕x⊕s[i−1])\sum_{i=l}^{r}min(S[n]\oplus x \oplus s[i-1])∑i=lr​min(S[n]⊕x⊕s[i−1])s[n]s[n]s[n]可用...

题目链接题意给定数组、无修改、多查询，求区间第k大。思路主席树板子题先离散化，在对每个节点建线段树，线段树存储下标位置+1的前缀和。每次查询，查询俩节点之间线段树的差值第k大。感觉代码思路理解不是很难，和树上每个节点建树差别不大?，但是用好写题不容易，太菜了。代码#include <stdio.h>#include <vector>#include &...