Codeforces Round #301 (Div. 2) E . Infinite Inversions 트리 배열 역순
19882 단어 codeforces
time limit per test
2 seconds
memory limit per test
256 megabytes
input standard input
output standard output
There is an infinite sequence consisting of all positive integers in the increasing order: p = {1, 2, 3, ...}. We performed n swapoperations with this sequence. A swap(a, b) is an operation of swapping the elements of the sequence on positions a and b. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (i, j), that i < j and pi > pj.
Input
The first line contains a single integer n (1 ≤ n ≤ 105) — the number of swap operations applied to the sequence.
Each of the next n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 109, ai ≠ bi) — the arguments of the swap operation.
Output
Print a single integer — the number of inversions in the resulting sequence.
Sample test(s)
input
2
4 2
1 4
output
4
input
3
1 6
3 4
2 5
output
15
제목: 무한히 긴 수조(1, 2, 3, 4,......),매번 두 위치의 값을 교환하는 n회 조작.
출력은 최종적으로 몇 개의 역순 대수가 있습니까?
이 문제는 숫자가 많을 수 있기 때문에 우리는 이산화 후에 역순수를 구할 수 밖에 없다. 먼저 모든 조작을 읽고 이산화 피조작수를 구할 수 있다.피조작수 사이의 숫자는 축소해서 처리할 수 있다. (모든 숫자를 하나의 숫자로 보고 처리하는 것이다.)그리고 결과를 구할 수 있을 거예요.
1 #include <set>
2 #include <map>
3 #include <cmath>
4 #include <ctime>
5 #include <queue>
6 #include <stack>
7 #include <cstdio>
8 #include <string>
9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 typedef unsigned long long ull;
16 typedef long long ll;
17 const int inf = 0x3f3f3f3f;
18 const double eps = 1e-8;
19 const int MAXN = 4e5+10;
20 int a[MAXN], tot, n;
21 int A[MAXN], B[MAXN];
22 int lowbit (int x)
23 {
24 return x & -x;
25 }
26 long long arr[MAXN], M;
27 void modify (int x, int d)
28 {
29 while (x < M)
30 {
31 arr[x] += d;
32 x += lowbit (x);
33 }
34 }
35 int sum(int x)
36 {
37 int ans = 0;
38 while (x)
39 {
40 ans += arr[x];
41 x -= lowbit (x);
42 }
43 return ans;
44 }
45 int p[MAXN],kk[MAXN];
46 int main()
47 {
48 #ifndef ONLINE_JUDGE
49 freopen("in.txt","r",stdin);
50 #endif
51 while (cin >> n)
52 {
53 int x, y;
54 tot = 0;
55 memset (arr, 0, sizeof (arr));
56 memset(kk, 0, sizeof (kk));
57 long long minv = inf;
58 long long maxv = 0;
59 map<int, int>pp;
60 for (int i = 0; i < n; i++)
61 {
62 scanf ("%d%d", &x, &y);
63 minv = min(minv, (long long)min(x, y));
64 maxv = max(maxv, (long long)max(x, y));
65 a[tot++] = x;
66 a[tot++] = y;
67 A[i] = x;
68 B[i] = y;
69 }
70 sort (a, a+tot);
71
72 tot = unique(a, a+tot) - a;
73 int ok = 0;
74 int tmp = tot;
75 long long j = minv;
76 int tt;
77 vector<int>vec;
78 for (int i = 0; i < tot; )
79 {
80 if (a[i] == j)
81 {
82 i++;
83 j++;
84 ok = 0;
85 }
86 else
87 {
88 if (ok == 0) //
89 {
90 ok = j;
91 a[tmp++] = j;
92 tt = j;
93 vec.push_back(tt);
94 }
95 pp[ok] += a[i]-j;
96 j = a[i];
97 }
98 }
99 tot = tmp;
100 sort (a, a+tot);
101 for (int i = 0; i < vec.size(); i++)
102 {
103 int qq = vec[i];
104 if (pp.count(qq) >= 1)
105 {
106 int ix = lower_bound(a, a+tot, qq)-a+1;
107 kk[ix] = pp[qq];
108 }
109 }
110 for (int i = 0; i < n; i++)
111 {
112 A[i] = lower_bound(a,a+tot, A[i]) - a + 1; //
113 B[i] = lower_bound(a,a+tot, B[i]) - a + 1;
114 }
115 maxv = lower_bound(a, a+tot, maxv) - a + 1;
116 M = maxv+10;
117 for (int i = 1; i <= maxv; i++)
118 {
119 p[i] = i;
120 }
121 for (int i = 0; i < n; i++)
122 {
123 swap(p[A[i]], p[B[i]]);
124 }
125 long long ans = 0;
126 long long cnt = 0;
127 for (int i = 1; i <= maxv; i++)
128 {
129 ans += (long long)(i-1+cnt - sum(p[i]))*max(1,kk[i]);
130 modify(p[i], max(1,kk[i]));
131 cnt += max(1,kk[i]) - 1;
132 }
133 printf("%I64d
", ans);
134 }
135 return 0;
136 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.