奶牛集会

思路:

  把奶牛按照v排序;

  然后,每次都把奶牛放入一个集合s;

  因为奶牛已经排序;

  所以,每次第i次放入奶牛起作用的v就是vi;

  每次ans+=(xi*sum-sumxl)*vi+(sumxr-xi*sum)*vi;

  可以用线段树实现;

来,上代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 20005 struct CowType {
int vi,xi;
};
struct CowType cow[maxn]; struct TreeNodeType {
int l,r,xx,sum,mid;
};
struct TreeNodeType tree[maxn<<]; int n; long long ans,sx,ss; inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} bool cmp(CowType aa,CowType bb)
{
return aa.vi<bb.vi;
} void tree_build(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r;
if(l==r) return ;
tree[now].mid=l+r>>;
tree_build(now<<,l,tree[now].mid);
tree_build(now<<|,tree[now].mid+,r);
} void tree_add(int now,int to)
{
if(tree[now].l==tree[now].r)
{
tree[now].sum++;
tree[now].xx+=cow[to].xi;
return ;
}
if(cow[to].xi<=tree[now].mid) tree_add(now<<,to);
else tree_add(now<<|,to);
tree[now].xx=tree[now<<].xx+tree[now<<|].xx;
tree[now].sum=tree[now<<].sum+tree[now<<|].sum;
} void tree_query(int now,int l,int r)
{
if(tree[now].l==l&&tree[now].r==r)
{
sx+=tree[now].xx,ss+=tree[now].sum;
return ;
}
if(l>tree[now].mid) tree_query(now<<|,l,r);
else if(r<=tree[now].mid) tree_query(now<<,l,r);
else
{
tree_query(now<<,l,tree[now].mid);
tree_query(now<<|,tree[now].mid+,r);
}
} int main()
{
in(n);
for(int i=;i<=n;i++) in(cow[i].vi),in(cow[i].xi);
sort(cow+,cow+n+,cmp),tree_build(,,),tree_add(,);
for(int i=;i<=n;i++)
{
tree_add(,i);
sx=,ss=,tree_query(,,cow[i].xi-);
ans+=(ss*cow[i].xi-sx)*cow[i].vi;
sx=,ss=,tree_query(,cow[i].xi+,);
ans+=(sx-ss*cow[i].xi)*cow[i].vi;
}
cout<<ans;
return ;
}

最新文章

  1. Linux网络编程-tcp缓存设置
  2. Struts2入门案例
  3. PHP socket上传文件图片
  4. 在CentOS7上安装JDK1.8
  5. Python之路 day2 字典练习题之 三级菜单
  6. 怎么在阿里云服务器部署多个tomcat
  7. 四则运算GUI版本
  8. js控制元素的显示与隐藏
  9. MySQL客户端执行外部sql文件命令
  10. Android 程式开发:(廿一)消息传递 —— 21.3 使用Intent发送短信
  11. Android WebView 缓存
  12. IntelliJ IDEA 创建 Maven简单项目
  13. ECharts前端图形展示
  14. jquery裁剪图片插件cropit示例
  15. CentOS下安装zookeeper并设置开机自启动
  16. Kafka学习笔记之Kafka三款监控工具
  17. Js的substring和C#的Substring
  18. mySql---数据库索引原理及优化
  19. SP211 PRIMIT - Primitivus recurencis(欧拉回路)
  20. NodeJS操作Redis实现消息的发布与订阅

热门文章

  1. pg数据库数据表异常挂起
  2. String类中的toCharArray()方法
  3. Java从后台重定向(redirect)到另一个项目的方法
  4. C语言库函数实现 【微软面试100题 第八十三题】
  5. Spring进阶—如何用Java代码实现邮件发送(一)
  6. 《Cracking the Coding Interview》——第9章:递归和动态规划——题目5
  7. USACO Section2.1 Hamming Codes 解题报告 【icedream61】
  8. 每天一个Linux命令(3):ls命令
  9. SELECTORS模块实现并发简单版FTP
  10. Box布局管理