trie字典树
//cnt是总共出现的点的个数，如果是字符串字典树，那么就是所有字符的数量
int son[N][27], idx, cnt[N];
//插入这个字符串
void insert(string a) {
int p = 0;
for (int i = 0; a[i]; i++) {
int u = a[i] - 'a';
if (!son[p][u])
son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
//返回这个字符串之前出现的次数
int query(string a) {
int p = 0;
for (int i = 0; a[i]; i++) {
int u = a[i] - 'a';
if (!son[p][u]) {
return 0;
}
p = son[p][u];
}
return cnt[p];
}
并查集
//初始化：
for (int i = 1; i <= n; i++) p[i] = i;
//查找：
int find(int a) {
if (p[a] != a)
p[a] = find(p[a]);
return p[a];
}
//添加a与b：
p(find(a))=find(b);
树状数组
其基本用法是动态的在1~n这些数字中加减后，仍然可以快速求得前缀和。
int n, m;
ll tr[N];
ll lowbit(ll a) {
return a & (-a);
}
//表示an[a]+=k;
void add(ll a,ll k) {
for (int i = a; i <= n; i += lowbit(i)) {
tr[i] += k;
}
}
//注意i>0,数字的下标也是从0开始的。ask(a)返回前a个数的和
ll ask(ll a) {
ll sum = 0;
for (int i = a; i; i -= lowbit(i)) {
sum += tr[i];
}
return sum;
}线段树
//建树操作，初始调用为build(1,1,n);注意u是根节点编号
void build(int u, int l, int r) {
tr[u] = {l, r};
if (l == r)
return;
int mid = tr[u].l + tr[u].r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
//修改操作，调用为modify(1,a,v)，将a这个点的值改为v,注意pushup是在更新了子节点后，用子节点的信息来更新自身节点，非常重要,注意u是根节点编号。
void modify(int u, int l,int r, int v) {
if (tr[u].l >= l && tr[u].r <= r)
tr[u].v = v;
else {
pushdown(u);
int mid = tr[u].r + tr[u].l >> 1;
if (l <= mid)
modify(u << 1, l,r, v);
if(r>mid)
modify(u << 1 | 1, l,r, v);
pushup(u);
}
}
//查询操作:调用为query(1,l,r)，在l和r这个区间内寻找答案，注意u是根节点编号
int query(int u, int l, int r) {
if (l <= tr[u].l && r >= tr[u].r)
return tr[u].v;
pushdown(u);
int ans = 0;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
ans = max(ans, query(u << 1, l, r));
if (r > mid)
ans = max(ans, query(u << 1 | 1, l, r));
return ans;
}
//或者：
node query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u];
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid)
return query(u << 1, l, r);
if (l > mid)
return query(u << 1 | 1, l, r);
node res;
auto ll = query(u << 1, l, r);
auto rr = query(u << 1 | 1, l, r);
pushup(res, ll, rr);
return res;
}
}
//pushup操作：用子节点的信息来更新自身节点，每道题有独特的写法
void pushup(int u) {
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void pushdown(int u){
tr[u].add=0;
}线段树经典题
区间修改和求区间gcd。
前提知识：gcd(a,b,c,d)=gcd(a,b-a,c-b,d-c);//注意到除了第一项，后面都可以转化成差分的形式，例如gcd(2,6,12)=gcd(2,4,6)，但要注意gcd要取绝对值，因为差分可能存在负数，但绝对值一定是对的，
gcd(a,b,c,d)=gcd(gcd(a,b),gcd(c,d))是这道题的核心思想
所以可以维护一个原数组的差分数组线段树，要求lr的gcd,先在树中求l1-r的gcd，然后求an[l],这里相当于求差分数组的1~l的和，用线段树去查找。
int n, m;
typedef long long ll;
ll an[500010];
ll sn[500010];
struct Node {
ll l, r;
ll sum, d;
} tr[500010 * 4];
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
void pushup(Node &u, Node &l, Node &r) {
u.sum = l.sum + r.sum;
u.d = gcd(l.d, r.d);
}
void pushup(int u) {
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
build(1, 1, n);
while (m--) {
char a;
cin >> a;
if (a == 'Q') {
int l, r;
cin >> l >> r;
ll c = query(1, 1, l).sum;
if (l == r)
cout << c<<"\n";
else {
ll d = query(1, l + 1, r).d;
cout << abs(gcd(c, d)) << "\n";
}
} else {
ll l, r, d;
cin >> l >> r >> d;
modify(1, l, d);
if (r + 1 <= n)
modify(1, r + 1, -d);
}
}
return 0;
}
主席树
用于在静态的数组中，动态寻找子区间第k小的数。
主席树本质上是可持久化权值线段树，前k个数组成的权值线段树可以用前k-1个数组成的线段树作为基础，动态开点。在遍历时，用 r-（l-1）的信息得到，l-r的权值线段树信息。
const int N = 100010;
int n, m;
int a[N];
vector<int> nums;
struct Node
{
int l, r;
int cnt;
}tr[N * 4 + N * 17]; //N * 4 + NlogN
int root[N], idx;
int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
// 对左右边界建立节点并编号, build是建立好骨架, 每个版本insert改不同数据
int build (int l, int r)
{
int p = ++idx;
if (l == r) return p;
int mid = l + r >> 1;
tr[p].l = build(l, mid), tr[p].r = build(mid+1, r);
return p;
}
// l, r是要放入的坐标范围, x是要插入的数离散化后的位置
int insert(int p, int l, int r, int x)
{
// 假设现在是从外界第一次执行insert, 那么调用的时候, p必定是根节点,
// 那么q就相当于复制了一个根节点, 从节点q进入这棵树的时候, 也能得到之前的所有内容.
// 同理, 再往下二分递归的时候, insert会继续复制根节点的左(右)子树, 一直递归直到l==r之前,
// q和原来的p都是一毛一样. 直到l==r才真正插入了新点, 每次插入的时间空间复杂度都是lgk,
// 总加起来就是lg1+lg2+...+lgn = lg(n!), 根据stirling公式, 结果为nlgn (大O)
int q = ++idx;
tr[q] = tr[p];
if (l == r) // 如果区间长度为1, 说明就是放这里了
{
// tr[q].cnt++是表示插在这个叶节点上
// 这个线段树只是保存的每个区间里面的元素个数
// 每次插入都只是覆盖到的那堆区间里面的cnt发生+1
tr[q].cnt++;
return q;
}
int mid = l + r >> 1;
if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
else tr[q].r = insert(tr[p].r, mid+1, r, x);
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt; // 相当于pushup了
return q;
}
// l ,r是检索范围, q是当前第r个节点root[r]能包含1~r之间所有
// p的输入是root[l-1], 作用是剔除这个根节点所包含数据的影响
int query(int q, int p, int l, int r, int k)
{
if (l == r) return r; // 如果找到位置
// 目标是求l r之间的第k小
// tr[tr[q].l].cnt - tr[tr[p].l].cnt的结果是求出在p之后插入到q这些数之后,
// 有多少个数(cnt)插入了p的左子树, 由于p的内容肯定不能出现在l r之间(p根节点就是root[l-1]),
// 所以cnt就是相当于"存在q左子树里面但不存在于1, l 之间的数的个数"
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
// k <= cnt说明要找的元素在q的左子树里面, 同时这里面也要剔除掉包含在p左子树的内容
if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
else return query(tr[q].r, tr[p].r, mid+1, r, k - cnt); // 类似同上
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
nums.push_back(a[i]); //离散化使用
}
// 离散化
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
// 构造线段树, 构造n个版本的线段树
// 第0个版本的什么都没有就用build, build是建立好骨架, 每个版本insert改不同数据
root[0] = build(0, nums.size() - 1);
// 后面的每插入一个点算一个版本, 每次插入都只是比上一个版本多1个数
// 左右参数给0和nums.size()-1是因为离散化之后的值域就是在0, nums.size()-1之间
// 要插入必须得把这些地方全包才能保证找得到插入点
for (int i = 1; i <= n; i++)
root[i] = insert(root[i-1], 0, nums.size() - 1, find(a[i]));
while (m -- )
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", nums[query(root[r], root[l-1], 0, nums.size()-1, k)]);
}
return 0;
}
