补题 abcD - Intersecting Intervals 离散化 + 树状数组
作者:
多米尼克領主的致意
,
2024-05-26 16:20:42
,
所有人可见
,
阅读 8
code:
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&-x;
typedef long long ll;
const int N = 5e5 + 10;
int oldl, oldr, newl[N], newr[N], s[N * 2];
int n;
int tree[2 * N];
struct node{
int l, r;
}a[N];
bool cmp(node a, node b){
return a.r < b.r;
}
void add(int x, int d){
while(x < 2 * N){
tree[x] += d;
x += lowbit(x);
}
}
ll sum(int x){
ll ans = 0;
while(x > 0){
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++){
cin >> oldl >> oldr;
newl[i] = oldl;
newr[i] = oldr;
s[i] = oldl;
s[i + n] = oldr;
}
sort(s + 1, s + 1 + 2 * n);
int cnt = n;
for(int i = 1;i <= cnt;i++){
newl[i] = lower_bound(s + 1, s + 1 + 2 * n, newl[i]) - s;
newr[i] = lower_bound(s + 1, s + 1 + 2 * n, newr[i]) - s;
a[i] = {newl[i], newr[i]};
}
sort(a + 1, a + 1 + cnt, cmp);
ll ans = 0;
for(int i = 1;i <= n;i++){
// cout << a[i].l << " " << a[i].r << endl;
auto l = a[i].l, r = a[i].r;
ans += sum(r) - sum(l - 1);
add(r, 1);
}
cout << ans;
return 0;
}