本文共 1430 字，大约阅读时间需要 4 分钟。
给定长度为 2 N 2N 2N的序列， 1 N 1~N 1 N各处现过 2 2 2次， i i i第一次出现位置记为 a i a_i ai，第二次记为 b i b_i bi，求满足 a i < a j < b i < b j a_i<a_j<b_i<b_j ai<aj<bi<bj的对数
第一行是 N ( 1 ≤ N ≤ 50 , 000 ) N(1 \leq N \leq 50,000) N(1≤N≤50,000)
接下来的两行则是长度为 2 N 2N 2N的序列。输出满足的对数
432441321
3
这道题要用树状数组来做。
我们先把某个数第一次出现时叫做这个数的左端点，第二次出现时叫做右端点。
然后按左端点从小到大排序，然后对于每一个点，统计它左右端点之间的标记的个数（就是到过的数的右端点），然后就标记这个数的右端点。 这样子我们就可以得出答案了。 （至于为什么的话，自己推一推吧）#include#include using namespace std;struct node{ int l, r;}a[100001];int n, xx, ans, ge[100001];bool cmp(node x, node y) { return x.l < y.l;}int get(int now) { //得到单点值 int re = 0; for (int i = now; i > 0; i -= i & -i) re += ge[i]; return re;}void build(int now, int ad) { //单点加值 for (int i = now; i <= 2 * n; i += i & -i) ge[i] += ad;}int main() { // freopen("circlecross.in", "r", stdin);// freopen("circlecross.out", "w", stdout); scanf("%d", &n);//读入 for (int i = 1; i <= 2 * n; i++) { scanf("%d", &xx);//读入 if (!a[xx].l) a[xx].l = i;//第一次出现 else a[xx].r = i;//第二次 } sort(a + 1, a + n + 1, cmp);//按第一次出现时间从小到大排序 for (int i = 1; i <= n; i++) { ans += get(a[i].r) - get(a[i].l - 1);//得到以这个数左右端点中的已经到过的数 build(a[i].r, 1);//把数的右端点加入树状数组 } printf("%d", ans);//输出 // fclose(stdin);// fclose(stdout); return 0;}
转载地址：http://olph.baihongyu.com/