codeforces540E-树状数组求逆序对
2024-09-03 14:26:54
1-1e9的数据范围 但有1e5个区间 所以可以考虑把没有涉及到的区间缩成一个点 然后树状数组求逆序对
#include<bits/stdc++.h> #define inf 0x3f3f3f3f const int maxn=; using namespace std; typedef long long ll; int n; ll cnt; ll ans; ll tot; vector<ll> seg; map<ll,int> m; struct node{
ll l,r;
}s[maxn+]; ll a[maxn+]; ll c[maxn+]; ll t[maxn+]; int lowbit(int x){
return x&(-x);
} void add(int x,int y){
while(x<=cnt){
c[x]+=y;
x+=lowbit(x);
}
} ll sum(int x){
ll res=;
while(x){
res+=c[x];
x-=lowbit(x);
}
return res;
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%I64d%I64d",&s[i].l,&s[i].r);
seg.push_back(s[i].l);
seg.push_back(s[i].r);
}
unique(seg.begin(),seg.end());
sort(seg.begin(),seg.end());
for(size_t i=;i<seg.size();i++){
if(i==){
a[++cnt]=;
t[cnt]=cnt;
m[seg[i]]=cnt;
} else {
if(seg[i]-seg[i-]==){
a[++cnt]=;
m[seg[i]]=cnt;
t[cnt]=cnt;
} else {
a[++cnt]=seg[i]-seg[i-]-;
t[cnt]=cnt;
a[++cnt]=;
m[seg[i]]=cnt;
t[cnt]=cnt;
}
}
}
for(int i=;i<=n;i++){
int x=m[s[i].l];
int y=m[s[i].r];
swap(t[x],t[y]);
}
for(int i=;i<=cnt;i++){
tot+=a[i];
add(t[i],a[i]);
int temp=sum(t[i])-;
ans+=(tot-temp-)*a[i];
}
printf("%I64d\n",ans);
return ;
}
最新文章
- Android基础篇(一)
- JS面向对象逆向学习法,让难理解的统统一边去(1)~
- io资料
- cmd界面的编码如何改为utf8
- hibernate使用原生SQL查询返回结果集的处理
- POJ C++程序设计 编程题#2 编程作业—多态与虚函数
- Volley使用指南第三回(来自developer.android)
- JS function立即调用的几种写法
- java mvc框架系列总结ssh,ssm,servlet
- Why you should QC your reads AND your assembly?
- phpcmsV9手机站内容页有时内容不显示
- 如何编写入门级redis客户端
- SpringBoot jar包中资源加载问题
- 设置Oracle数据库开机自启动-亲试ok
- c语言操作文件函数大全
- MT【270】含参绝对值函数最大之二
- UOJ347 WC2018 通道 边分治、虚树
- html绝对路径,相对路径
- Codeforces 160D Edges in MST tarjan找桥
- ubuntu(14.04) sphinx安装