T1
题目描述
如果你有一个长度为 n 的序列：\(a_1, a_2, a_3, \dots, a_n\)，那么它的一个逆序对是一个二元组：\(< i, j >\) 满足 \(i < j\) 且 \(a_i > a_j\)，其中 \(i, j \in [1, n]\)。
我们称一个序列所包含的逆序对的个数为这个序列的逆序对数。
那么问题来了：
我给出一个长度为 n 的序列，需要你计算：
\[a_1, a_2, \dots, a_{n−1}, a_n\\ a_2, a_3, \dots, a_n, a_1\\ a_3, a_4, \dots, a_1, a_2\\ \dots\\ a_n, a_1, \dots, a_{n−2}, a_{n−1} \]这 \(n\) 个序列的逆序对个数之和。
输入格式
输入文件包含 \(2\) 行：
第 \(1\) 行 \(1\) 个整数：\(n\)，表示给定序列的长度。
第 \(2\) 行 \(n\) 个整数：\(a_1, a_2, \dots, a_n\)，表示初始序列。
输出格式
输出 \(n\) 个序列的逆序对个数的和。
输入样例1
3
2 2 3
输出样例1
3
样例1解释
以上样例中，3 个序列分别是：\(2, 2, 3\)，\(2, 3, 2\)，\(3, 2, 2\)，分别有 \(0, 1, 2\) 个逆序对，所以和为 \(3\)。
输入样例2
3
1 1 1
输出样例2
0
样例2解释
以上样例中，\(3\) 个序列都是：\(1, 1, 1\)，逆序对数为 \(0\)，所以答案为 \(0\)。
数据规模
对于 \(30\%\) 数据，\(1 \leq n \leq 300\)。
对于 \(60\%\) 数据，\(1 \leq n \leq 5000\)。
对于 \(100\%\) 数据，\(1 \leq n \leq 10^6, 1 \leq a_i \leq n\)。
完整代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 9;
int t[N * 24], a[N << 1], n, now, ans;
int lowbit(int x){
return x & (-x);
}
void insert(int p, int x){
for(int i = p; i <= n; i += lowbit(i))
t[i] += x;
}
int query(int p){
int ret = 0;
for(int i = p; i; i -= lowbit(i))
ret += t[i];
return ret;
}
signed main(){
freopen("rotinv.in", "r", stdin);
freopen("rotinv.out", "w", stdout);
scanf("%lld", &n);
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
a[n + i] = a[i];
}
for(int i = 1; i <= n; i++){
now += (i - 1) - query(a[i]);
insert(a[i], 1);
}
ans = now;
for(int i = n + 1; i < n + n; i++){
insert(a[i - n], -1);
now += (n - 1) - query(a[i]);
now -= query(a[i - n] - 1);
insert(a[i], 1);
ans += now;
}
printf("%lld", ans);
return 0;
}
T2
题目描述
你有一堆柱子，它们竖直地并排摆放在桌子上，它们的高度分别是：\(h_1, h_2, h_3, \dots, h_n\)。
你从前往后看，能够看见的柱子个数为这个柱子序列的“可见度”（能够看见柱子 \(i\) 当且仅当 \(hj < hi\) 且 \(j < i\)）。
现在给你一个长度为 \(n\) 的序列，还有 \(m\) 个询问，每次询问某个区间 \([l, r]\) 的柱子单独拿出来后，其可见度是多大。
输入格式
第 \(1\) 行 \(2\) 个整数：\(n, m\)，表示给出的柱子序列的长度和询问数。
第 \(2\) 行 \(n\) 个整数：\(a_1, a_2, a_3, \dots, a_n\)，表示每根柱子对应的高度。
接下来 \(m\) 行，每行 \(2\) 个整数：\(l, r\)，表示对区间 \([l, r]\) 进行询问。
输出格式
对于每个询问，输出答案。
输入样例
5 4
1 3 2 4 2
1 4
2 4
1 3
2 3
输出样例
3
2
2
1
样例解释
样例中“能够看见”的柱子的高度分别是：\(1, 3, 4\)，\(3, 4\)，\(1, 3\)，\(3\)。
数据规模
对于 \(30\%\) 的数据，\(1 \leq n, m \leq 10^3\)。
对于 \(100\%\) 的数据，\(1 \leq n, m \leq 10^5, 1 \leq a_i \leq n, 1 \leq l \leq r \leq n\)。
T3
题目描述
给你一棵无根树，边有边权，且是 \([0, 9]\) 之间的整数，给你 \(m\) 个询问，每次询问两个点 \(u, v\) 之间的路径的边的边权顺次连接起来后构成的那个数字取模于 \(31\)。
输入格式
第 \(1\) 行 \(2\) 个整数：\(n, m\)，表示树的节点个数和询问数。
接下来 \(n − 1\) 行，每行 \(3\) 个数：\(u, v, d\) 表示点 \(u\) 和点 \(v\) 之间有一条边权为 \(d\) 的边。
接下来 \(m\) 行，每行 \(2\) 个整数：\(u, v\) 表示一个询问。
输出格式
对于每个询问输出其答案。
输入样例
5 3
1 2 2
1 3 8
3 4 9
3 5 2
1 4
2 5
5 2
输出样例
27
24
6
样例解释
样例中三条路径对应的数字分别是：\(89, 582, 285\)，它们被 \(31\) 取模后为：\(27, 24, 6\)。
数据规模
对于 \(30\%\) 的数据，\(1 \leq n, m \leq 10^3\)。
对于 \(100\%\) 的数据，\(1 \leq n, m \leq 10^5, 1 \leq u, v \leq n, u \neq v, 0 \leq d \leq 9\)。
标签：dots,输出,23,2024.9,校测,样例,leq,序列,逆序 From： https://www.cnblogs.com/JPGOJCZX/p/18429295