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 ;
}

最新文章

  1. Android基础篇(一)
  2. JS面向对象逆向学习法,让难理解的统统一边去(1)~
  3. io资料
  4. cmd界面的编码如何改为utf8
  5. hibernate使用原生SQL查询返回结果集的处理
  6. POJ C++程序设计 编程题#2 编程作业—多态与虚函数
  7. Volley使用指南第三回(来自developer.android)
  8. JS function立即调用的几种写法
  9. java mvc框架系列总结ssh,ssm,servlet
  10. Why you should QC your reads AND your assembly?
  11. phpcmsV9手机站内容页有时内容不显示
  12. 如何编写入门级redis客户端
  13. SpringBoot jar包中资源加载问题
  14. 设置Oracle数据库开机自启动-亲试ok
  15. c语言操作文件函数大全
  16. MT【270】含参绝对值函数最大之二
  17. UOJ347 WC2018 通道 边分治、虚树
  18. html绝对路径,相对路径
  19. Codeforces 160D Edges in MST tarjan找桥
  20. ubuntu(14.04) sphinx安装

热门文章

  1. RQNOJ 342 最不听话的机器人:网格dp
  2. PS 图像调整— — gain and bias
  3. tcp攻击
  4. CodeForces - 204C Little Elephant and Furik and Rubik
  5. boost库安装和使用
  6. 洛谷P1092虫食算——深搜
  7. linux历史及基本知识
  8. POJ3928(树状数组:统计数字出现个数)
  9. 性能测试之Jmeter学习(八)
  10. VS2017 不能创建 vsto Excel 工作簿程序的问题