【题目来源】
洛谷：[P5677 GZOI2017] 配对统计 - 洛谷
【题目描述】
给定 \(n\) 个数 \(a_1,\cdots,a_n\)。
对于一组配对 \((x,y)\)，若对于所有的 \(i=1,2,\cdots,n\)，满足 \(|a_x-a_y|\le|a_x-a_i|(i\not=x)\)，则称 \((x,y)\) 为一组好的配对（\(|x|\) 表示 \(x\) 的绝对值）。
给出若干询问，每次询问区间 \([l,r]\) 中含有多少组好的配对。
即，取 \(x,y\)（\(l\le x,y\le r\) 且 \(x\not=y\)），问有多少组 \((x,y)\) 是好的配对。
【输入】
第一行两个正整数 \(n,m\)。
第二行 \(n\) 个数 \(a_1,\cdots,a_n\)。
接下来 \(m\) 行，每行给出两个数 \(l,r\)。
【输出】
\(Ans_i\) 表示第 \(i\) 次询问的答案，输出 \(\sum_{i=1}^m\limits Ans_i\times i\) 即可。
【输入样例】
3 2
2 1 3
1 2
1 3
【输出样例】
10
【算法标签】
《洛谷 P5677 配对统计》 #树状数组# #排序# #各省省选# #2017# #贵州# #O2优化#
【代码详解】
// 30分版本
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型
const int N = 300005; // 最大数组大小int a[N]; // 原始数组，存储数值
int b[N]; // b[i]: 存储a[i]与其他元素的最小差值
int n, m, l, r, x, y; // n: 数组长度, m: 查询次数, l,r: 查询区间, x,y: 临时变量
int ans; // 最终结果signed main()
{// 输入数组长度和查询次数cin >> n >> m;// 读入原始数组for (int i = 1; i <= n; i++) cin >> a[i];// 预处理：计算每个元素与其他元素的最小差值for (int i = 1; i <= n; i++){int mins = 1e9; // 初始化为极大值// 遍历所有其他元素，找到与a[i]的最小差值for (int j = 1; j <= n; j++){if (i == j) continue; // 跳过自身mins = min(mins, abs(a[i] - a[j]));}b[i] = mins; // 存储a[i]的最小差值}// 处理m个查询for (int i = 1; i <= m; i++){cin >> l >> r; // 读入查询区间int count = 0; // 当前查询的计数// 双重循环：遍历区间[l,r]中的所有元素对for (int x = l; x <= r; x++){for (int y = l; y <= r; y++){if (x == y) continue; // 跳过相同的元素// 检查条件：|a[x]-a[y]| <= b[x]// 即检查a[y]是否在a[x]的"邻域"内if (abs(a[x] - a[y]) <= b[x]){count++; // 满足条件，计数加1}}}// 累加结果：count * 查询编号ians += count * i;}// 输出最终结果cout << ans << endl;return 0;
}
// 50分版本
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型
const int N = 300005; // 最大数组大小// 结构体：存储数值和原始位置
struct Node
{int num; // 数值int id; // 原始位置（下标）
} a[N];int b[N][2]; // b[i][0]: 存储i的左侧最近邻元素位置，b[i][1]: 存储i的右侧最近邻元素位置
int n, m, l, r, x, y; // n: 数组长度, m: 查询次数, l,r: 查询区间
int ans; // 最终结果/*** 比较函数：按数值升序排序*/
bool cmp(Node x, Node y)
{return x.num < y.num;
}signed main()
{// 输入数组长度和查询次数cin >> n >> m;// 读入数组并记录原始位置for (int i = 1; i <= n; i++) {cin >> a[i].num; a[i].id = i; // 记录原始下标}// 按数值升序排序sort(a + 1, a + n + 1, cmp);// 预处理：计算每个元素的最近邻元素// 处理第一个元素（只有右侧邻居）b[a[1].id][1] = a[2].id; // 第一个元素的右侧最近邻是第二个元素// 处理最后一个元素（只有左侧邻居）b[a[n].id][0] = a[n - 1].id; // 最后一个元素的左侧最近邻是倒数第二个元素// 处理中间元素for (int i = 2; i < n; i++){// 默认左侧最近邻是前一个元素b[a[i].id][0] = a[i - 1].id;// 比较左右两侧的距离int left_dist = a[i].num - a[i - 1].num; // 到左侧邻居的距离int right_dist = a[i + 1].num - a[i].num; // 到右侧邻居的距离if (right_dist < left_dist){// 右侧邻居更近，清空左侧邻居，设置右侧邻居b[a[i].id][0] = 0; // 清空左侧邻居b[a[i].id][1] = a[i + 1].id; // 设置右侧邻居}else if (right_dist == left_dist){// 两侧距离相等，同时记录右侧邻居b[a[i].id][1] = a[i + 1].id;}// 如果左侧更近，则只保留左侧邻居（默认情况）}// 调试输出（注释状态）// for (int i = 1; i <= n; i++)// cout << b[i][0] << " " << b[i][1] << endl;// 处理m个查询for (int i = 1; i <= m; i++){cin >> l >> r; // 读入查询区间int count = 0; // 当前查询的计数// 遍历区间[l,r]中的每个元素for (int j = l; j <= r; j++){// 检查左侧最近邻是否在查询区间内if (b[j][0] >= l && b[j][0] <= r)count++;// 检查右侧最近邻是否在查询区间内if (b[j][1] >= l && b[j][1] <= r)count++;}// 累加加权结果：计数 × 查询编号ans += count * i;}// 输出最终结果cout << ans << endl;return 0;
}
// 100分版本
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型
const int N = 3000005; // 最大数组大小int n, m, l, r; // n: 数组长度, m: 查询次数, l,r: 查询区间
int paircount = 1; // 配对数计数器，从1开始
int trl[N * 2], trr[N * 2]; // 两个树状数组，用于统计区间内的有效对
int ans; // 最终结果// 结构体：存储数值和原始位置
struct Node
{int num; // 数值int id; // 原始位置（下标）
} a[N];// 结构体：存储一对元素的位置
struct Pair
{int x; // 较小位置int y; // 较大位置
} p[N * 2]; // 最多可能有2n个对// 结构体：存储查询区间
struct Sec
{int left; // 区间左端点int right; // 区间右端点int id; // 查询编号
} s[N];/*** 比较函数：按数值升序排序*/
bool cmp(Node x, Node y)
{return x.num < y.num;
}/*** 比较函数：按Pair的y值（较大位置）升序排序*/
bool cmp2(Pair x, Pair y)
{return x.y < y.y;
}/*** 比较函数：按查询区间的右端点升序排序*/
bool cmp3(Sec x, Sec y)
{return x.right < y.right;
}/*** 添加一对元素到Pair数组* @param pos 存储位置* @param x 第一个元素位置* @param y 第二个元素位置*/
void addpair(int pos, int x, int y)
{p[pos].x = min(x, y); // 存储较小位置p[pos].y = max(x, y); // 存储较大位置
}/*** 计算lowbit：获取x的最低位的1* @param x 输入数值* @return x的最低位的1所代表的值*/
int lowbit(int x)
{return x & -x; // 利用补码性质
}/*** 树状数组更新操作：在Pair的x和y位置分别添加值* @param pos Pair的索引* @param c 增加的值*/
void add(int pos, int c)
{// 在较小位置x的树状数组中添加值for (int i = p[pos].x; i <= n; i += lowbit(i))trl[i] += c;// 在较大位置y的树状数组中添加值for (int i = p[pos].y; i <= n; i += lowbit(i))trr[i] += c;
}/*** 查询区间[left, right]内的有效对数量* @param left 区间左端点* @param right 区间右端点* @return 有效对数量*/
int query(int left, int right)
{int ans1 = 0, ans2 = 0;// 查询左端点之前的和for (int i = left; i; i -= lowbit(i))ans1 += trl[i];// 查询右端点之前的和for (int i = right; i; i -= lowbit(i))ans2 += trr[i];// 返回区间内的数量：右端点的和 - 左端点的和return ans2 - ans1;
}signed main()
{// 输入数组长度和查询次数cin >> n >> m;// 特殊情况处理：只有一个元素if (n == 1){cout << 0;return 0;}// 读入数组并记录原始位置for (int i = 1; i <= n; i++){cin >> a[i].num;a[i].id = i;}// 按数值升序排序sort(a + 1, a + n + 1, cmp);// 预处理：计算每个元素的最近邻对// 处理第一个元素（只有右侧邻居）addpair(paircount++, a[1].id, a[2].id);// 处理最后一个元素（只有左侧邻居）addpair(paircount++, a[n].id, a[n - 1].id);// 处理中间元素for (int i = 2; i < n; i++){int left_dist = a[i].num - a[i - 1].num; // 到左侧邻居的距离int right_dist = a[i + 1].num - a[i].num; // 到右侧邻居的距离if (right_dist < left_dist){// 右侧邻居更近addpair(paircount++, a[i].id, a[i + 1].id);}else if (right_dist > left_dist){// 左侧邻居更近addpair(paircount++, a[i].id, a[i - 1].id);}else{// 两侧距离相等，记录两个邻居addpair(paircount++, a[i].id, a[i + 1].id);addpair(paircount++, a[i].id, a[i - 1].id);}}// 按Pair的y值（较大位置）排序，用于离线查询sort(p + 1, p + paircount, cmp2);// 调试输出（注释状态）// for (int i = 1; i < paircount; i++)// cout << p[i].x << " " << p[i].y << endl;// 读入所有查询for (int i = 1; i <= m; i++){cin >> s[i].left >> s[i].right;s[i].id = i; // 记录查询编号}// 按查询区间的右端点排序，用于离线处理sort(s + 1, s + m + 1, cmp3);// 调试输出（注释状态）// for (int i = 1; i <= m; i++)// cout << s[i].left << " " << s[i].right << endl;// 离线处理查询int pos = 1; // 当前处理的Pair索引for (int i = 1; i <= m; i++){// 将右端点小于等于当前查询右端点的Pair加入树状数组while (pos < paircount && p[pos].y <= s[i].right){add(pos, 1); // 将Pair加入树状数组pos++;}// 查询当前区间内的有效对数量// query(left-1, right) 返回区间[left, right]内的数量int count = query(s[i].left - 1, s[i].right);// 调试输出（注释状态）// cout << "count " << count << endl;// 累加加权结果：计数 × 查询编号ans += count * s[i].id;}// 输出最终结果cout << ans << endl;return 0;
}
【运行结果】
3 2
2 1 3
1 2
1 3
10