DL24JP 的博客
NOI算法6 技巧与思想
DL24JP SU @ 2026-10-9 16:41:54

1.莫队算法

洛谷题目：P2709 小B的询问
参考视频：https://www.bilibili.com/video/BV1nH4y1n7fd/

题目描述

小 B 有一个长为 $n$ 的整数序列 $a$ ，值域为 $[1,k]$ 。他一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$ ，求： $\sum\limits_{i=1}^k c_i^2$

其中 $c_i$ 表示数字 $i$ 在 $[l,r]$ 中的出现次数。

小 B 请你帮助他回答询问。

输入格式

第一行三个整数 $n,m,k$ 。

第二行 $n$ 个整数，表示小 B 的序列。

接下来的 $m$ 行，每行两个整数 $l,r$ 。

输出格式

输出 $m$ 行，每行一个整数，对应一个询问的答案。

输入输出样例 #1

输入 #1

6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6

输出 #1

说明/提示

【数据范围】对于 $100\%$ 的数据， $1\le n,m,k \le 5\times 10^4$ 。

1.1. 分块大小的选择

块大小B = sqrt(n)是莫队的最优选择：若B过小，左端点块数多，排序后指针移动次数多；若B过大，块内查询的右端点移动距离大。sqrt(n)可平衡左右指针的总移动次数，使总复杂度为O(n√n)。

1.2. 排序的奇偶性优化

对左端点所在块的奇偶性做区分：奇数块右端点升序、偶数块降序，可减少右端点在 “块间切换” 时的往返移动次数，实际效率比单纯按l/B升序 +r升序提升约 50%。

1.3. add/del 函数的核心逻辑

sum = Σc[x]²的更新不能直接sum += 2*c[x]+1（add 时），但代码中 “先减旧平方→更新次数→加新平方” 的方式更通用（适配任意基于次数的统计量），原理：

add(x)：新sum = sum - c[x]² + (c[x]+1)² = sum + 2*c[x]+1；
del(x)：新sum = sum - c[x]² + (c[x]-1)² = sum - 2*c[x]+1。

1.4. 双指针移动顺序

先扩展（左 / 右）、后收缩，保证每次移动仅调整一个位置，且不会出现区间越界（初始区间[1,0]为空，是安全的起始状态）。

1.5. 适用场景

普通莫队适用于 “离线查询”（所有查询提前给出）、“区间统计无修改” 的场景，可通过修改add/del函数适配不同统计目标（如区间不同数字个数、区间众数等）。

参考代码

// 普通莫队算法，解决区间查询（数字出现次数平方和），时间复杂度 O(n*sqrt(n))
#include <bits/stdc++.h>
using namespace std;

// 常量定义：数组/查询的最大规模（5e4级别适配莫队的分块效率）
const int N = 50005;

// 全局变量说明
int n, m, k;          // n：数组长度；m：查询次数；k：题目输入参数（此处未实际使用，保留格式）
int B;                // B：分块大小（通常取sqrt(n)，平衡指针移动次数）
int a[N];             // a[]：原始数组，存储每个位置的数值
int sum;              // sum：当前区间内「数字出现次数的平方和」（核心统计量）
int c[N];             // c[x]：当前区间内数字x的出现次数
int ans[N];           // ans[i]：存储第i个查询的答案（按查询原始编号）

// 查询结构体：存储单次查询的信息
struct Q
{
    int l, r, id;     // l/r：查询的区间左右端点；id：查询的原始编号（用于输出对应答案）
    
    // 重载<运算符：莫队的核心排序规则（减少双指针移动次数）
    // 排序逻辑：
    // 1. 优先按左端点所在块的编号（l/B）升序；
    // 2. 若块编号为奇数：右端点r升序；若为偶数：右端点r降序（奇偶性优化，减少r的移动距离）
    bool operator<(Q &b)
    {
        if (l / B != b.l / B) return l < b.l;  // 不同块：按左端点升序
        if ((l / B) & 1) return r < b.r;       // 奇数块：r升序
        return r > b.r;                        // 偶数块：r降序
    }
} q[N];  // q[]：存储所有查询

// 扩展操作：将数字x加入当前区间，更新sum和c[x]
// 原理：sum = Σc[i]²，加入x时，先减去旧的c[x]²，c[x]++后再加新的c[x]²
void add(int x)
{
    sum -= c[x] * c[x];  // 移除旧的贡献（加入前的次数平方）
    c[x]++;              // x的出现次数+1
    sum += c[x] * c[x];  // 加入新的贡献（加入后的次数平方）
}

// 删除操作：将数字x移出当前区间，更新sum和c[x]
// 原理与add对称：先减旧贡献，c[x]--后加新贡献
void del(int x)
{
    sum -= c[x] * c[x];  // 移除旧的贡献（删除前的次数平方）
    c[x]--;          // x的出现次数-1
    sum += c[x] * c[x];  // 加入新的贡献（删除后的次数平方）
}

int main()
{
    // 第一步：读入基础参数
    scanf("%d%d%d", &n, &m, &k);
    B = sqrt(n);  // 计算分块大小（核心参数，平衡时间复杂度）
    
    // 第二步：读入原始数组
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    
    // 第三步：读入所有查询，记录原始编号
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;  // 保留查询的原始编号，避免排序后答案错位
    }
    
    // 第四步：按莫队规则排序查询（核心优化）
    sort(q + 1, q + 1 + m);
    
    // 第五步：双指针动态调整区间，处理所有查询
    int cur_l = 1, cur_r = 0;  // cur_l/cur_r：当前维护的区间端点（初始为空区间[1,0]）
    for (int i = 1; i <= m; ++i)
    {
        int q_l = q[i].l, q_r = q[i].r;  // 当前查询的目标区间
        
        // 调整左指针：若当前左端点 > 目标左端点，向左扩展（cur_l--）
        while (cur_l > q_l) add(a[--cur_l]);
        // 调整右指针：若当前右端点 < 目标右端点，向右扩展（cur_r++）
        while (cur_r < q_r) add(a[++cur_r]);
        // 调整左指针：若当前左端点 < 目标左端点，向右收缩（cur_l++）
        while (cur_l < q_l) del(a[cur_l++]);
        // 调整右指针：若当前右端点 > 目标右端点，向左收缩（cur_r--）
        while (cur_r > q_r) del(a[cur_r--]);
        
        // 记录当前查询的答案（按原始编号存储）
        ans[q[i].id] = sum;
    }
    
    // 第六步：按查询原始顺序输出答案
    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);
    
    return 0;
}

2.CDQ分治（求三维偏序）

洛谷题目：P3810 陌上花开
参考视频：https://www.bilibili.com/video/BV1FF4m1u7fr/

题目描述

有 $n$ 个元素，第 $i$ 个元素有 $a_i,b_i,c_i$ 三个属性，设 $f(i)$ 表示满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 且 $c_j \leq c_i$ 且 $j \ne i$ 的 $j$ 的数量。

对于所有 $d \in [0, n)$ ，求 $f(i) = d$ 的数量。

输入格式

第一行两个整数 $n,k$ ，表示元素数量和最大属性值。

接下来 $n$ 行，每行三个整数 $a_i ,b_i,c_i$ ，分别表示三个属性值。

输出格式

共 $n$ 行，第 $d + 1$ 行表示 $f(i) = d$ 的 $i$ 的数量。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

对于所有数据，保证 $1 \leq n \leq 10^5$ ， $1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5$ 。

2.1. 核心思路

通过 CDQ 分治将三维偏序拆解为 “一维排序（x）+ 二维偏序（y,z）”
二维偏序用归并排序 + 树状数组解决
总时间复杂度 O(n log²n)。

2.2. 三维偏序的拆解思路

x 维度：先按 x 升序排序，CDQ 分治时左区间 x ≤ 右区间 x，将 x 维度的偏序转化为分治的区间划分，无需额外处理；
y 维度：CDQ 分治的归并过程中按 y 升序遍历，保证左区间 y ≤ 右区间 y，将 y 维度的偏序转化为归并顺序；
z 维度：用树状数组维护 z 的前缀和，统计≤当前 z 的元素个数，完成 z 维度的偏序统计。

2.3. 去重的意义

原始数据中可能存在完全相同的三元组，去重后合并为一个节点并记录重复个数cnt，避免重复计算，最终统计答案时再将重复个数累加到对应位置，保证结果正确。

2.4. 答案统计的逻辑

a[i].s：去重后，满足x≤、y≤、z≤且不包含自身重复的元素个数；
a[i].s + a[i].cnt - 1：包含自身重复的总个数（例如，重复 3 次的三元组，自身贡献 3 个，因此减 1 后加 cnt）；
ans[k] += a[i].cnt：将重复个数累加到 “满足条件数量为 k” 的位置，最终输出每个 k 的总个数。

2.5. 时间复杂度分析

排序： $O(n logn)$ ；
CDQ 分治：递归深度 $O(logn)$ ，每层归并 + 树状数组操作 $O(n logM)$ （M 为 z 的范围）；
总复杂度： $O(n log²n)$ （因 M≤2e5，logM可视为logn）。

2.6. 树状数组的核心作用

维度统计：在 CDQ 分治的归并阶段，快速统计≤当前元素 z 值的元素总个数，完成 z 维度偏序的计数；
高效操作：提供 O (logn) 时间复杂度的单点更新（加入 / 清空 z 维度元素）和前缀查询，支撑二维偏序（y、z）的高效计算；
状态维护：临时维护左区间 z 维度的元素分布，为右区间偏序统计提供数据支撑，且可快速清空以避免跨分治阶段的状态污染

参考代码

// CDQ分治(归并排序思想) + 树状数组 解决三维偏序问题，时间复杂度 O(n logn logn)
#include <bits/stdc++.h>
using namespace std;

// 树状数组核心宏：求x的最低位1（用于单点更新/前缀查询）
#define lowbit(x) x&-x
// 分治中点宏：等价于(l + r) / 2（位运算更快）
#define mid (l+r>>1)
// 常量定义：N=三元组最大数量，M=z维度的最大值（需覆盖输入的z范围）
const int N = 100005, M = 200005;

int n, m;     // n：原始三元组数量；m：题目输入的参数（此处未实际使用，为题目格式保留）
int s[M];     // 树状数组数组，用于维护z维度的前缀和（统计≤当前z的元素个数）
int ans[N];   // ans[k]：满足条件的数量为k的三元组总个数（最终输出）

// 三元组结构体：存储三维偏序的核心信息
struct E
{
    int x, y, z; // 三维坐标(x,y,z)
    // cnt：当前三元组的重复个数（去重后）
    //s：满足x≤、y≤、z≤的非自身重复的元素个数
    int cnt, s; 
    // 重载==运算符：判断两个三元组是否完全相同（用于去重）
    bool operator==(const E &t) const
    {
        return x == t.x && y == t.y && z == t.z;
    }
} a[N];  // 存储所有三元组（去重前/后）

// 排序规则1：按x升序，x相同按y升序，y相同按z升序
// 作用：CDQ分治时，左区间的x ≤ 右区间的x，将x维度的偏序转化为分治的区间划分
bool cmpx(E &a, E &b)
{
    if (a.x != b.x) return a.x < b.x;
    if (a.y != b.y) return a.y < b.y;
    return a.z < b.z;
}

// 排序规则2：仅按y升序
// 作用：CDQ分治的归并阶段，按y排序以统计y维度的偏序
bool cmpy(E &a, E &b)
{
    return a.y < b.y;
}

// 树状数组单点更新：在位置x处增加k（k可为负，用于清空）
// 作用：维护z维度的元素计数，统计≤当前z的元素个数
void change(int x, int k)
{
    while (x <= M)  // 不超过z的最大范围
    {
        s[x] += k;   // 更新当前节点值
        x += lowbit(x); // 跳到父节点（树状数组特性）
    }
}

// 树状数组前缀查询：查询[1, x]的累加和
// 作用：统计z维度≤x的元素总个数
int query(int x)
{
    int t = 0;
    while (x)  // 从x向下遍历到0
    {
        t += s[x];   // 累加当前节点值
        x -= lowbit(x); // 跳到子节点
    }
    return t;
}

// CDQ分治核心函数：处理区间[l, r]的二维偏序（y,z）
// 前提：整个数组已按x排序，因此左区间[l,mid]的x ≤ 右区间[mid+1,r]的x
void CDQ(int l, int r)
{
    // 递归边界：区间长度为1，无需处理
    if (l == r) return;
    
    // 第一步：分治处理左、右子区间（递归拆解问题）
    CDQ(l, mid);    // 处理左区间[l, mid]
    CDQ(mid + 1, r); // 处理右区间[mid+1, r]

    // 第二步：归并过程，统计左区间对右区间的y、z维度偏序贡献
    int i = l, j = mid + 1;
    // 双指针遍历左、右区间，按y升序归并
    while (i <= mid && j <= r)
    {
        if (a[i].y <= a[j].y)
        {
            // 左区间元素y更小，将其z加入树状数组（统计z的前缀）
            change(a[i].z, a[i].cnt);//精妙之处，树状数组相当于桶计数
            i++;
        }
        else
        {
            // 右区间元素y更大，查询树状数组中≤当前z的元素个数，累加到s（x≤、y≤、z≤的数量）
            a[j].s += query(a[j].z);
            j++;
        }
    }
    // 处理左区间剩余元素：全部加入树状数组
    while (i <= mid)
    {
        change(a[i].z, a[i].cnt);
        i++;
    }
    // 处理右区间剩余元素：查询并累加z的前缀和
    while (j <= r)
    {
        a[j].s += query(a[j].z);
        j++;
    }

    // 第三步：清空树状数组（避免影响后续分治）
    for (j = l; j <= mid; j++)
        change(a[j].z, -a[j].cnt); // 反向更新，恢复树状数组初始状态

    // 第四步：按y升序排序当前区间[l, r]（为上层分治的归并做准备）
    sort(a + l, a + r + 1, cmpy);
}

int main()
{
    // 第一步：输入原始数据
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
        a[i].cnt = 1; // 初始重复个数为1（未去重）
    }

    // 第二步：按x排序（CDQ分治的前提，保证左区间x≤右区间x）
    sort(a + 1, a + n + 1, cmpx);

    // 第三步：去重，合并相同的三元组（x,y,z全相同）
    int k = 1; // k：去重后的三元组数量
    for (int i = 2; i <= n; i++)
    {
        if (a[i] == a[k])
            a[k].cnt++; // 相同则累加重复个数
        else
            a[++k] = a[i]; // 不同则新增去重后的三元组
    }

    // 第四步：执行CDQ分治，统计二维偏序（y,z）的贡献
    CDQ(1, k);

    // 第五步：统计最终答案
    // a[i].s：去重后，≤当前三元组的非自身重复元素个数
    // a[i].s + a[i].cnt - 1：≤当前三元组的总个数（包含自身重复）
    // ans[k]：满足条件数量为k的三元组总个数
    for (int i = 1; i <= k; i++)
        ans[a[i].s + a[i].cnt - 1] += a[i].cnt;

    // 第六步：输出答案（ans[0]到ans[n-1]）
    for (int i = 0; i < n; i++)
        printf("%d\n", ans[i]);

    return 0;
}

CDQ分治算法执行流程跟踪：

#include <bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
#define mid (l+r>>1)
const int N = 100005, M = 200005;

int n, m;
int s[M];
int ans[N];

struct E
{
    int x, y, z;
    int cnt, s;
    bool operator==(const E &t) const
    {
        return x == t.x && y == t.y && z == t.z;
    }
    // 辅助输出三元组信息
    void print(const string &prefix = "") const {
        printf("%s(x=%d, y=%d, z=%d, cnt=%d, s=%d)\n", prefix.c_str(), x, y, z, cnt, s);
    }
} a[N];

// 辅助打印树状数组（可选，便于调试）
void print_tree_array(int max_z = 20) {
    printf("    【树状数组状态】s[1~%d] = [", min(max_z, M-1));
    for (int i = 1; i <= min(max_z, M-1); i++) {
        printf("%d", s[i]);
        if (i < min(max_z, M-1)) printf(", ");
    }
    printf("]\n");
}

bool cmpx(E &a, E &b)
{
    if (a.x != b.x) return a.x < b.x;
    if (a.y != b.y) return a.y < b.y;
    return a.z < b.z;
}

bool cmpy(E &a, E &b)
{
    return a.y < b.y;
}

// 树状数组单点更新：添加详细输出
void change(int x, int k)
{
    printf("    执行change(x=%d, k=%d)：\n", x, k);
    int orig_x = x;
    while (x <= M)
    {
        printf("      节点x=%d：s[%d] += %d → 原值=%d → 新值=%d\n", 
               x, x, k, s[x], s[x] + k);
        s[x] += k;
        x += lowbit(x);
    }
    // print_tree_array(20); // 可选：打印树状数组前20个元素
}

// 树状数组前缀查询：添加详细输出
int query(int x)
{
    printf("    执行query(x=%d)：\n", x);
    int t = 0, orig_x = x;
    while (x)
    {
        printf("      节点x=%d：t += s[%d] → 原值t=%d → 新值t=%d\n", 
               x, x, t, t + s[x]);
        t += s[x];
        x -= lowbit(x);
    }
    printf("    query(%d)返回：%d\n", orig_x, t);
    return t;
}

// CDQ分治核心函数：添加详细输出
void CDQ(int l, int r)
{
    printf("\n=====================================\n");
    printf("  进入CDQ分治：处理区间 [l=%d, r=%d]\n", l, r);
    printf("=====================================\n");

    // 递归边界：区间长度为1
    if (l == r) {
        printf("  【递归边界】l=r=%d → 直接返回\n", l);
        return;
    }

    // 第一步：递归处理左、右子区间
    printf("  第一步：递归拆解子区间\n");
    printf("    处理左区间：CDQ(%d, %d)\n", l, mid);
    CDQ(l, mid);
    printf("    处理右区间：CDQ(%d, %d)\n", mid+1, r);
    CDQ(mid + 1, r);

    // 第二步：归并过程，统计左→右的y/z偏序贡献
    printf("\n  第二步：归并统计y/z维度偏序\n");
    int i = l, j = mid + 1;
    printf("    双指针初始化：i=%d（左区间起点），j=%d（右区间起点）\n", i, j);
    
    while (i <= mid && j <= r)
    {
        printf("\n    对比：a[%d].y=%d vs a[%d].y=%d\n", i, a[i].y, j, a[j].y);
        if (a[i].y <= a[j].y)
        {
            printf("    → a[%d].y ≤ a[%d].y：左区间元素加入树状数组\n", i, j);
            change(a[i].z, a[i].cnt);
            i++;
            printf("    → i更新为：%d\n", i);
        }
        else
        {
            printf("    → a[%d].y > a[%d].y：右区间元素查询z前缀和\n", i, j);
            int q_res = query(a[j].z);
            a[j].s += q_res;
            printf("    → a[%d].s += %d → 原值s=%d → 新值s=%d\n", 
                   j, q_res, a[j].s - q_res, a[j].s);
            j++;
            printf("    → j更新为：%d\n", j);
        }
    }

    // 处理左区间剩余元素
    printf("\n    处理左区间剩余元素（i=%d ~ mid=%d）：\n", i, mid);
    while (i <= mid)
    {
        printf("    → 处理a[%d]：", i);
        a[i].print("      ");
        change(a[i].z, a[i].cnt);
        i++;
    }

    // 处理右区间剩余元素
    printf("\n    处理右区间剩余元素（j=%d ~ r=%d）：\n", j, r);
    while (j <= r)
    {
        printf("    → 处理a[%d]：", j);
        a[j].print("      ");
        int q_res = query(a[j].z);
        a[j].s += q_res;
        printf("    → a[%d].s += %d → 新值s=%d\n", j, q_res, a[j].s);
        j++;
    }

    // 第三步：清空树状数组（反向更新）
    printf("\n  第三步：清空树状数组（恢复初始状态）\n");
    for (j = l; j <= mid; j++)
    {
        printf("    → 撤销a[%d]的贡献：change(z=%d, k=-%d)\n", j, a[j].z, a[j].cnt);
        change(a[j].z, -a[j].cnt);
    }

    // 第四步：按y升序排序当前区间
    printf("\n  第四步：按y升序排序区间 [%d, %d]\n", l, r);
    sort(a + l, a + r + 1, cmpy);
    printf("    排序完成，当前区间前3个元素：\n");
    for (int p = l; p <= min(l+2, r); p++) {
        a[p].print("      a[" + to_string(p) + "]");
    }

    printf("\n=====================================\n");
    printf("  退出CDQ分治：区间 [l=%d, r=%d] 处理完成\n", l, r);
    printf("=====================================\n");
}

int main()
{
    printf("============ 程序启动：三维偏序问题 ============\n");
    // 第一步：输入原始数据
    printf("\n  第一步：读入输入数据\n");
    scanf("%d%d", &n, &m);
    printf("    读入n=%d（三元组数量），m=%d（题目参数）\n", n, m);
    printf("    读入%d个三元组：\n", n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
        a[i].cnt = 1;
        a[i].s = 0;
        a[i].print("      a[" + to_string(i) + "]");
    }

    // 第二步：按x升序排序（CDQ分治前提）
    printf("\n  第二步：按x升序排序（x相同按y/z升序）\n");
    sort(a + 1, a + n + 1, cmpx);
    printf("    排序后前5个元素：\n");
    for (int i = 1; i <= min(5, n); i++) {
        a[i].print("      a[" + to_string(i) + "]");
    }

    // 第三步：去重，合并相同三元组
    printf("\n  第三步：去重（合并x/y/z全相同的三元组）\n");
    int k = 1; // 去重后的三元组数量
    printf("    初始化k=%d，开始遍历去重：\n", k);
    for (int i = 2; i <= n; i++)
    {
        printf("      对比a[%d] vs a[%d]：\n", k, i);
        a[k].print("        基准：");
        a[i].print("        当前：");
        if (a[i] == a[k])
        {
            printf("        → 完全相同，a[%d].cnt += 1 → 新值cnt=%d\n", 
                   k, a[k].cnt + 1);
            a[k].cnt++;
        }
        else
        {
            k++;
            a[k] = a[i];
            printf("        → 不同，k更新为%d，a[%d] = a[%d]\n", k, k, i);
        }
    }
    printf("    去重完成：共%d个唯一三元组\n", k);
    printf("    去重后前3个元素：\n");
    for (int i = 1; i <= min(3, k); i++) {
        a[i].print("      a[" + to_string(i) + "]");
    }

    // 第四步：执行CDQ分治
    printf("\n  第四步：执行CDQ分治（处理y/z二维偏序）\n");
    CDQ(1, k);

    // 第五步：统计最终答案
    printf("\n  第五步：统计最终答案\n");
    memset(ans, 0, sizeof ans); // 初始化答案数组
    for (int i = 1; i <= k; i++)
    {
        int res = a[i].s + a[i].cnt - 1; // 总个数（包含自身重复）
        ans[res] += a[i].cnt;
        printf("    a[%d]：s=%d, cnt=%d → res=%d → ans[%d] += %d → 新值ans[%d]=%d\n",
               i, a[i].s, a[i].cnt, res, res, a[i].cnt, res, ans[res]);
    }

    // 第六步：输出答案
    printf("\n  第六步：输出答案（ans[0] ~ ans[%d]）\n", n-1);
    printf("=====================================\n");
    for (int i = 0; i < n; i++) {
        printf("ans[%d] = %d\n", i, ans[i]);
    }
    printf("=====================================\n");

    return 0;
}
/*
测试样例：
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
*/

图解CDQ分治：

3.整体二分（求区间第k小）

洛谷题目：P3834 可持久化线段树2
参考视频：https://www.bilibili.com/video/BV1jD421L77x/

题目描述

如题，给定 $n$ 个整数构成的序列 $a$ ，将对于指定的闭区间 $[l, r]$ 查询其区间内的第 $k$ 小值。

输入格式

第一行包含两个整数，分别表示序列的长度 $n$ 和查询的个数 $m$ 。第二行包含 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个元素 $a_i$ 。接下来 $m$ 行每行包含三个整数 $l, r, k$ , 表示查询区间 $[l, r]$ 内的第 $k$ 小值。

输出格式

对于每次询问，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输出 #1

说明/提示

样例 1 解释

$n=5$ ，数列长度为 $5$ ，数列从第一项开始依次为 $\{25957, 6405, 15770, 26287, 26465\}$ 。

第一次查询为 $[2, 2]$ 区间内的第一小值，即为 $6405$ 。
第二次查询为 $[3, 4]$ 区间内的第一小值，即为 $15770$ 。
第三次查询为 $[4, 5]$ 区间内的第一小值，即为 $26287$ 。
第四次查询为 $[1, 2]$ 区间内的第二小值，即为 $25957$ 。
第五次查询为 $[4, 4]$ 区间内的第一小值，即为 $26287$ 。

数据规模与约定

对于 $20\%$ 的数据，满足 $1 \leq n,m \leq 10$ 。
对于 $50\%$ 的数据，满足 $1 \leq n,m \leq 10^3$ 。
对于 $80\%$ 的数据，满足 $1 \leq n,m \leq 10^5$ 。
对于 $100\%$ 的数据，满足 $1 \leq n,m \leq 2\times 10^5$ ， $0\le a_i \leq 10^9$ ， $1 \leq l \leq r \leq n$ ， $1 \leq k \leq r - l + 1$ 。

3.1. 整体二分的核心思想

值域二分：不直接对数组排序，而是对数值范围[mi, mx]二分，判断每个查询的第 k 小落在左 / 右值域；
操作分流：将「原数插入」和「区间查询」整合为统一操作序列，按值域分流到左 / 右子问题；
树状数组辅助：统计区间内≤当前 mid 的元素个数，判断查询的分流方向，保证每次统计的时间复杂度为O(logn)。

3.2. 关键操作的逻辑链路

原数分流：值≤mid 的原数加入树状数组（统计贡献），分流到左值域；否则分流到右值域；
查询分流：若区间内≤mid 的数≥k → 第 k 小在左值域；否则更新 k（k -= 个数），分流到右值域；
递归终止：当值域区间长度为 1 时，该值即为所有当前查询的答案。

3.3. 树状数组的作用

统计区间内≤mid 的元素个数，支撑查询的分流判断；
单次更新 / 查询为O(logn)，保证每层二分的时间复杂度为O((n+m)logn)；
递归后撤销贡献，避免不同值域层的统计相互干扰。

3.4. 时间复杂度分析

值域二分层数：O(logV)（V 为数值范围，通常≤1e9，logV≈30）；
每层二分的操作：O((n+m)logn)（树状数组的更新 / 查询）；
总复杂度：O((n+m)logn logV)，等价于O(n logn logV)（m≤n）。

参考代码

// 整体二分（值域二分）+ 树状数组 解决区间第k小问题，时间复杂度 O(n*logn*logV)
// V为数值范围，logV是值域二分的层数，logn是树状数组的操作复杂度
#include <bits/stdc++.h>
using namespace std;

// 常量定义：数组/查询的最大总规模（原数n+查询m≤2e5）
const int N = 200005;

// 全局变量
int n, m, cnt;       // n：原数组长度；m：查询次数；cnt：原数+查询的总个数（用于整合操作序列）
int ans[N];         // ans[i]：存储第i个查询的答案（区间第k小值）
int s[N];          // s[]：树状数组，用于统计区间内≤某值的元素个数

// 操作结构体：整合「原数插入」和「区间查询」为统一的操作序列
struct Q
{
    // 字段说明：
    // 原数（opt=0）：x=元素位置，y=元素值，k/id无意义（设为0），opt=0（标记是原数）
    // 查询（opt=1）：x=区间左端点，y=区间右端点，k=第k小，id=查询编号（1~m），opt=1（标记是查询）
    int x, y, k, id, opt;
} q[N << 1], q1[N << 1], q2[N << 1];
// q[]：总操作序列（原数+查询）；q1[]：分流到左值域的操作；q2[]：分流到右值域的操作

// 树状数组单点更新：在位置x处增加v（v=1时添加贡献，v=-1时撤销贡献）
// 作用：统计某位置的元素是否属于当前值域区间，支撑区间计数
void add(int x, int v)
{
    while (x <= n)  		// 不超过原数组长度
    {
        s[x] += v;     // 更新当前节点的贡献值
        x += x & (-x);   // 跳到树状数组的父节点（lowbit操作）
    }
}

// 树状数组前缀查询：查询[1, x]的累加和
// 作用：统计前x个位置中，属于当前值域区间的元素总个数
int sum(int x)
{
    int t = 0;
    while (x)  // 从x遍历到0
    {
        t += s[x];         // 累加当前节点的贡献值
        x -= x & (-x);      // 跳到树状数组的子节点
    }
    return t;
}

// 整体二分核心函数：递归处理操作序列的[l, r]区间，值域范围为[L, R]
// l/r：操作序列的下标范围（原数+查询）；L/R：当前二分的数值范围
void solve(int l, int r, int L, int R)
{
    if (l > r) return;  // 递归边界：无操作需要处理，直接返回

    // 值域区间长度为1：所有当前区间的查询答案都是L（即R）
    if (L == R)
    {
        for (int i = l; i <= r; i++)
        {
            if (q[i].opt)  // 仅处理查询操作（opt=1）
                ans[q[i].id] = L;// 批量记录该查询的答案
        }
        return;
    }

    // 第一步：计算值域中点，划分左值域[L,mid]和右值域[mid+1,R]
    int mid = (L + R) >> 1;
    int p1 = 0, p2 = 0;  // p1：q1的指针（左值域操作数）；p2：q2的指针（右值域操作数）

    // 第二步：遍历当前操作区间，按值域分流操作
    for (int i = l; i <= r; i++)
    {
        if (!q[i].opt)  // 处理原数操作（opt=0）
        {
            // 原数的值≤mid：分流到左值域，同时加入树状数组统计贡献
            if (q[i].y <= mid)
            {
                add(q[i].x, 1);       // 标记该位置的元素属于左值域
                q1[++p1] = q[i];      // 加入左值域操作序列
            }
            else  // 原数的值>mid：分流到右值域，不统计贡献
            {
                q2[++p2] = q[i];      // 加入右值域操作序列
            }
        }
        else  // 处理查询操作（opt=1）
        {
            // 统计查询区间[x,y]内≤mid的元素个数：sum(y) - sum(x-1)
            int cnt_le_mid = sum(q[i].y) - sum(q[i].x - 1);
            // 情况1：≤mid的元素个数≥k → 第k小在左值域，分流到q1
            if (cnt_le_mid >= q[i].k)
            {
                q1[++p1] = q[i];
            }
            // 情况2：≤mid的元素个数<k → 第k小在右值域，更新k（减去左值域的个数），分流到q2
            else
            {
                q[i].k -= cnt_le_mid;  // 右值域中只需找第(k - cnt_le_mid)小
                q2[++p2] = q[i];
            }
        }
    }

    // 第三步：撤销树状数组的贡献（避免影响后续递归）
    for (int i = 1; i <= p1; i++)
    {
        if (!q1[i].opt)  // 仅撤销原数操作的贡献（查询无贡献）
            add(q1[i].x, -1);
    }

    // 第四步：合并分流后的操作序列，更新q数组
    // 左值域操作覆盖q[l..l+p1-1]
    for (int i = 1; i <= p1; i++)
        q[i + l - 1] = q1[i];
    // 右值域操作覆盖q[l+p1..r]
    for (int i = 1; i <= p2; i++)
        q[i + l + p1 - 1] = q2[i];

    // 第五步：递归处理左、右值域
    solve(l, l + p1 - 1, L, mid);        // 处理左值域[L,mid]的操作
    solve(l + p1, r, mid + 1, R);        // 处理右值域[mid+1,R]的操作
}

int main()
{
    // 第一步：读入原数组长度n和查询次数m
    scanf("%d%d", &n, &m);
    int mi = 2e9, mx = -2e9;  // mi/mx：原数组的最小/最大值（确定值域范围）
    int x, y, k;

    // 第二步：读入原数组，构建原数操作序列（opt=0）
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);  // x是原数组第i个位置的元素值
        q[++cnt] = {i, x, 0, 0, 0};  // 原数操作：x=位置i，y=值x，opt=0
        mi = min(mi, x);  // 更新最小值
        mx = max(mx, x);  // 更新最大值
    }

    // 第三步：读入查询，构建查询操作序列（opt=1）
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &x, &y, &k);  // x=左端点，y=右端点，k=第k小
        q[++cnt] = {x, y, k, i, 1};   // 查询操作：id=i（对应第i个查询），opt=1
    }

    // 第四步：启动整体二分，操作序列范围[1,cnt]，值域范围[mi,mx]
    solve(1, cnt, mi, mx);

    // 第五步：输出所有查询的答案
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);

    return 0;
}

整体二分算法执行流程跟踪：

#include <bits/stdc++.h>
using namespace std;

// 常量定义：数组/查询的最大总规模（原数n+查询m≤2e5）
const int N = 200005;

// 全局变量
int n, m, cnt;       // n：原数组长度；m：查询次数；cnt：原数+查询的总个数
int ans[N];         // ans[i]：存储第i个查询的答案
int s[N];          // s[]：树状数组，用于统计区间内≤某值的元素个数

// 操作结构体：整合「原数插入」和「区间查询」为统一的操作序列
struct Q
{
	int x, y, k, id, opt;
} q[N << 1], q1[N << 1], q2[N << 1];

// 辅助函数：打印树状数组当前状态（可选，便于调试）
void print_tree_array()
{
	printf("    【树状数组当前状态】s[1~%d] = [", n);
	for (int i = 1; i <= n; i++)
	{
		printf("%d", s[i]);
		if (i < n) printf(", ");
	}
	printf("]\n");
}

// 树状数组单点更新：添加详细输出
void add(int x, int v)
{
	printf("    执行add(x=%d, v=%d)：\n", x, v);
	int orig_x = x;
	while (x <= n)
	{
		printf("      节点x=%d：s[%d] += %d → 原值=%d → 新值=%d\n",
		       x, x, v, s[x], s[x] + v);
		s[x] += v;
		x += x & (-x); // lowbit操作，跳到父节点
	}
	// print_tree_array(); // 可选：打印完整树状数组
}

// 树状数组前缀查询：添加详细输出
int sum(int x)
{
	printf("    执行sum(x=%d)：\n", x);
	int t = 0, orig_x = x;
	while (x)
	{
		printf("      节点x=%d：t += s[%d] → 原值t=%d → 新值t=%d\n",
		       x, x, t, t + s[x]);
		t += s[x];
		x -= x & (-x); // lowbit操作，跳到子节点
	}
	printf("    sum(%d)返回结果：%d\n", orig_x, t);
	return t;
}

// 整体二分核心函数：添加详细输出，展示递归/分流/赋值全过程
void solve(int l, int r, int L, int R)
{
	printf("\n=====================================\n");
	printf("  进入solve(l=%d, r=%d, L=%d, R=%d)\n", l, r, L, R);
	printf("=====================================\n");

	// 递归边界1：无操作需要处理
	if (l > r)
	{
		printf("  【递归边界】l=%d > r=%d → 直接返回\n", l, r);
		return;
	}

	// 递归边界2：值域区间长度为1，批量赋值答案
	if (L == R)
	{
		printf("  【值域边界】L=R=%d → 批量赋值查询答案\n", L);
		for (int i = l; i <= r; i++)
		{
			if (q[i].opt)   // 仅处理查询操作（opt=1）
			{
				ans[q[i].id] = L;
				printf("    查询id=%d：ans[%d] = %d（区间第k小值）\n",
				       q[i].id, q[i].id, L);
			}
		}
		return;
	}

	// 第一步：计算值域中点，划分左右值域
	int mid = (L + R) >> 1;
	printf("  【值域二分】mid = (L+R)/2 = (%d+%d)/2 = %d\n", L, R, mid);
	int p1 = 0, p2 = 0; // q1/q2的指针（左/右值域操作数）

	// 第二步：遍历操作序列，按值域分流
	printf("  【操作分流】遍历操作序列[%d, %d]，按值域≤%d分流\n", l, r, mid);
	for (int i = l; i <= r; i++)
	{
		printf("\n  处理第%d个操作（i=%d）：\n", i - l + 1, i);
		if (!q[i].opt)   // 原数操作（opt=0）
		{
			printf("    类型：原数 | 位置x=%d | 值y=%d | opt=0\n", q[i].x, q[i].y);
			if (q[i].y <= mid)
			{
				printf("    判断：y=%d ≤ mid=%d → 分流到左值域q1\n", q[i].y, mid);
				add(q[i].x, 1); // 加入树状数组统计贡献
				q1[++p1] = q[i];
				printf("    q1当前长度：%d\n", p1);
			}
			else
			{
				printf("    判断：y=%d > mid=%d → 分流到右值域q2\n", q[i].y, mid);
				q2[++p2] = q[i];
				printf("    q2当前长度：%d\n", p2);
			}
		}
		else     // 查询操作（opt=1）
		{
			printf("    类型：查询 | 区间[%d,%d] | 第k=%d小 | id=%d | opt=1\n",
			       q[i].x, q[i].y, q[i].k, q[i].id);
			// 计算区间内≤mid的元素个数
			int sum_y = sum(q[i].y);
			int sum_x_1 = sum(q[i].x - 1);
			int cnt_le_mid = sum_y - sum_x_1;
			printf("    区间[%d,%d]内≤%d的元素个数：sum(%d)-sum(%d) = %d-%d = %d\n",
			       q[i].x, q[i].y, mid, q[i].y, q[i].x-1, sum_y, sum_x_1, cnt_le_mid);

			if (cnt_le_mid >= q[i].k)
			{
				printf("    判断：%d ≥ %d → 第k小在左值域，分流到q1\n", cnt_le_mid, q[i].k);
				q1[++p1] = q[i];
				printf("    q1当前长度：%d\n", p1);
			}
			else
			{
				printf("    判断：%d < %d → 第k小在右值域，更新k=%d-%d=%d，分流到q2\n",
				       cnt_le_mid, q[i].k, q[i].k, cnt_le_mid, q[i].k - cnt_le_mid);
				q[i].k -= cnt_le_mid;
				q2[++p2] = q[i];
				printf("    q2当前长度：%d\n", p2);
			}
		}
	}

	// 第三步：撤销树状数组的贡献（避免影响后续递归）
	printf("\n  【撤销贡献】遍历q1，撤销原数操作的树状数组贡献\n");
	for (int i = 1; i <= p1; i++)
	{
		if (!q1[i].opt)   // 仅撤销原数操作
		{
			printf("    撤销原数操作：位置x=%d → add(x=%d, v=-1)\n", q1[i].x, q1[i].x);
			add(q1[i].x, -1);
		}
	}

	// 第四步：合并分流后的操作序列到q数组
	printf("\n  【合并序列】更新原操作数组q：\n");
	printf("    左值域q1（长度%d）→ 覆盖q[%d~%d]\n", p1, l, l + p1 - 1);
	for (int i = 1; i <= p1; i++) q[i + l - 1] = q1[i];
	printf("    右值域q2（长度%d）→ 覆盖q[%d~%d]\n", p2, l + p1, r);
	for (int i = 1; i <= p2; i++) q[i + l + p1 - 1] = q2[i];

	// 第五步：递归处理左、右值域
	printf("\n  【递归调用】处理左值域：solve(%d, %d, %d, %d)\n", l, l + p1 - 1, L, mid);
	solve(l, l + p1 - 1, L, mid);
	printf("  【递归调用】处理右值域：solve(%d, %d, %d, %d)\n", l + p1, r, mid + 1, R);
	solve(l + p1, r, mid + 1, R);

	printf("\n=====================================\n");
	printf("  退出solve(l=%d, r=%d, L=%d, R=%d)\n", l, r, L, R);
	printf("=====================================\n");
}

int main()
{
	printf("============ 程序启动 ============\n");
	// 第一步：读入原数组长度和查询次数
	scanf("%d%d", &n, &m);
	printf("  读入n=%d（原数组长度），m=%d（查询次数）\n", n, m);

	int mi = 2e9, mx = -2e9;
	int x, y, k;

	// 第二步：读入原数组，构建原数操作序列
	printf("\n  【读入原数组】（共%d个元素）：\n", n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &x);
		printf("    位置%d：%d\n", i, x);
		q[++cnt] = {i, x, 0, 0, 0}; // 原数操作：x=位置，y=值，opt=0
		mi = min(mi, x);
		mx = max(mx, x);
	}
	printf("  原数组最小值mi=%d，最大值mx=%d（值域范围）\n", mi, mx);

	// 第三步：读入查询，构建查询操作序列
	printf("\n  【读入查询】（共%d个）：\n", m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &x, &y, &k);
		printf("    查询%d：区间[%d,%d]的第%d小值（id=%d）\n", i, x, y, k, i);
		q[++cnt] = {x, y, k, i, 1}; // 查询操作：x=左，y=右，k=第k小，id=编号，opt=1
	}

	// 第四步：启动整体二分核心函数
	printf("\n============ 启动整体二分 ============\n");
	solve(1, cnt, mi, mx);

	// 第五步：输出所有查询的答案
	printf("\n============ 最终查询结果 ============\n");
	for (int i = 1; i <= m; i++)
	{
		printf("  查询%d的答案：%d\n", i, ans[i]);
	}

	printf("\n============ 程序结束 ============\n");
	return 0;
}
/*
输入样例1：
5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输入样例2：
5 5
3 1 2 4 5
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1
*/

NOI算法6 技巧与思想

1.莫队算法

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

1.1. 分块大小的选择

1.2. 排序的奇偶性优化

1.3. add/del 函数的核心逻辑

1.4. 双指针移动顺序

1.5. 适用场景

参考代码

2.CDQ分治（求三维偏序）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

2.1. 核心思路

2.2. 三维偏序的拆解思路

2.3. 去重的意义

2.4. 答案统计的逻辑

2.5. 时间复杂度分析

2.6. 树状数组的核心作用

参考代码

3.整体二分（求区间第k小）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

样例 1 解释

数据规模与约定

3.1. 整体二分的核心思想

3.2. 关键操作的逻辑链路

3.3. 树状数组的作用

3.4. 时间复杂度分析

参考代码

状态

开发

支持

还没有账户？

登录