函数复合是这样的一类问题：
有一个函数序列 \(f_1, f_2, f_3, ..., f_n\)。离线询问，给定参数 \(x\)， \(f_r(f_{r-1}(...f_l(x)))\) 的值。
有点抽象对吧。看道题就懂了。
[PKUSC 2024] 排队
QOJ 题目链接：#8672. 排队。（反正我在其他 OJ 上没找到）
前置知识：平衡树
题面上有简化题意，但我觉得看原题面更好理解。（懒得写题面了 qwq）
做法
我们考虑把询问离线下来扫描，然后维护一个多重集，集合里每个元素对一一个询问，表示扫到当前位置时这个询问的值是多少。
比如当前扫到 \(i\)，那如果一个区间的 \(l=i\) 就往集合里加入一个“\(0\)”的值。然后把集合里位于 \([l_i,r_i]\) 内的值给 \(+1\)。最后，如果一个区间的 \(r=i\) 就记录答案。
这个东西可以平衡树维护，拿 fhq-treap 来说， 加入“\(0\)”是简单的。
然后将 \([l_i,r_i]\) 内的值给 \(+1\) 可以把那段的子集给 split 出来之后打个标记，再塞回去。
至于计算某个点 \(u\) 的答案，由于标记可能还没下传，所以要从 \(u\) 往上跳到根，统计 tag 的和。正好 fhq 有期望层数 \(\log\) 的性质，所以这个也是 \(\log\) 级别的。
设 \(n,m\) 同阶，那时间复杂度就是 \(\mathcal{O}(n\log n)\)。
代码
代码十分简单，如下：（这份开 C++17 还加快读快写才过的 qwq）
点击查看代码
// Author: Aquizahv
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
int n, m, l[N], r[N], ans[N];
vector<int> in[N], out[N];
struct treap
{
int root, son[N][2], val[N], rank[N], tag[N], fa[N];
void insert(int u)
{
rank[u] = rand();
root = merge(u, root);
}
void add(int u, int x)
{
val[u] += x;
tag[u] += x;
}
void pushdown(int u)
{
if (tag[u])
{
add(son[u][0], tag[u]);
add(son[u][1], tag[u]);
tag[u] = 0;
}
}
void pushup(int u)
{
fa[son[u][0]] = fa[son[u][1]] = u;
}
void split(int u, int key, int &x, int &y)
{
if (!u)
{
x = y = 0;
return;
}
pushdown(u);
if (val[u] <= key)
{
x = u;
split(son[u][1], key, son[u][1], y);
}
else
{
y = u;
split(son[u][0], key, x, son[u][0]);
}
pushup(u);
}
int merge(int u, int v)
{
if (!u || !v)
return u ^ v;
pushdown(u), pushdown(v);
if (rank[u] > rank[v])
{
son[u][1] = merge(son[u][1], v);
pushup(u);
return u;
}
else
{
son[v][0] = merge(u, son[v][0]);
pushup(v);
return v;
}
}
int getsum(int u)
{
if (u == root)
return tag[u];
return tag[u] + getsum(fa[u]);
}
} t;
inline int read()
{
bool f = 1; int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{ if (ch == '-') f = !f; ch = getchar(); }
while (ch >= '0' && ch <= '9')
{ x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return f ? x : -x;
}
inline void write(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar((x % 10) ^ 48);
}
int main()
{
#ifdef Aquizahv
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin >> n >> m;
for (int i = 1; i <= n; i++)
l[i] = read(), r[i] = read();
int L, R;
for (int i = 1; i <= m; i++)
{
L = read(), R = read();
in[L].push_back(i);
out[R].push_back(i);
}
for (int i = 1; i <= n; i++)
{
for (auto j : in[i])
t.insert(j);
int x, y, z;
t.split(t.root, r[i], x, z);
t.split(x, l[i] - 1, x, y);
t.add(y, 1);
t.root = t.merge(t.merge(x, y), z);
for (auto j : out[i])
ans[j] = t.val[j] + (j != t.root ? t.getsum(t.fa[j]) : 0);
}
for (int i = 1; i <= m; i++)
write(ans[i]), putchar('\n');
return 0;
}