技术标签： 树状数组
约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i 头奶牛的坐标为Xi，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第i 头和第j 头奶牛交流，会发出max{Vi; Vj}×|Xi − Xj | 的音量，其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。
假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。
• 第一行：单个整数N，1 ≤ N ≤ 20000
• 第二行到第N + 1 行：第i + 1 行有两个整数Vi 和Xi，1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000
• 单个整数：表示所有奶牛产生的音量之和
4
3 1
2 5
2 6
4 3
57
第i头牛和其他的牛发出的生意就等于=第i头牛的vi*（它之前牛的数目它的坐标-它之前所有牛的坐标和）+vi（它之后所有牛的坐标和-它之后牛的数目*他的坐标），对于牛的数目和牛的坐标，我们都可以用树状数组来维护
#include<bits/stdc++.h>
#define M(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MOD 1000000009
using namespace std;
inline void read(long long &x){
char ch=getchar(),c=ch;
x=0;
while(ch<'0' || ch>'9'){
c=ch;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
if(c=='-')x=-x;
}
long long wz[20010],yy[20010],n,mn=20000;
long long ans;
struct node{
long long xi;
long long vi;
}a[20010];
bool cmp(node x,node y)
{
return x.vi<y.vi;
}
int lobit(int x) {
return x&(-x);}
void crwz(int x) {
for(;x<=mn;x+=lobit(x)) wz[x]++;}
int z(int x)
{
int sum=0;
for(;x>=1;x-=lobit(x)) sum+=wz[x];
return sum;
}
void cryy(int x,int v) {
for(;x<=mn;x+=lobit(x)) yy[x]+=v;}
int y(int x)
{
int sum=0;
for(;x>=1;x-=lobit(x)) sum+=yy[x];
return sum;
}
int jdz(int x)
{
if(x<0) return -x;
else return x;
}
int main(){
read(n);
for(int i=1;i<=n;++i)read(a[i].vi),read(a[i].xi);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;++i)
{
int j=a[i].xi;
ans+=a[i].vi*(z(j-1)*j-y(j-1)+y(mn)-y(j)-(z(mn)-z(j))*j);
crwz(a[i].xi);
cryy(j,a[i].xi);
}
printf("%lld",ans);
return 0;
}
文章浏览阅读4.1w次，点赞12次，收藏14次。案例：绘制多个同心圆代码如下：import turtlet = turtle.Pen()my_colors = ("red", "green", "yellow", "black")t.width(4)t.speed(1)for i in range(10): # 0 1 2 3 4 t.penup() t.goto(0, -i*10) # 0, -100,-2..._python利用负循环画10个同心圆
文章浏览阅读240次。精通PKI网络安全认证技术与编程实现从实战出发，介绍了PKI应用开发过程和细节。《精通PKI网络安全认证技术与编程实现》共32章，分6篇，主要内容包括PKI基础知识、OpenSSL开发、CrytoAPI开发、JavaSecurity开发、电子商务网站应用、PKI技术应用等，涉及C语言、Java语言、JSP、ASP/ASP.NET、PHP等开发语言。为了方便读者深入了解PKI，《精通PKI网络安全认..._api安全技术与实战pdf
文章浏览阅读644次。函数名: modf头文件：函数原型: double modf(double value, double *iptr);功 能: 求双精度数的小数部分参 数： double value 为要操作的双精度数 ，double *iptr 为要传回整数部分的变量指针返回值： 返回value的小数部分程序例: 分别求出双精度number的小数部分和整数部分，并将结果输出#include#includ..._c语言求一个双精度数的整数部分和小数部分
文章浏览阅读288次。最近在学习DDos相关知识，参考一些只是，做了摘要，供自己参考。 参考：http://blog.csdn.net/xlf13872135090/article/details/8059538SYN Flood 攻击原理 利用TCP协议缺陷，发送了大量伪造的TCP连接请求，使得被攻击方资源耗尽，无法及时回应或处理正常的服务请求。一个正常的TCP连接需要三次握手，首先客户端发送一个包含SYN标志的数_http存在synflood吗
文章浏览阅读775次。我们之前学习的都是针对一个表的操作。如果要进行多个表之间的操作，就要用到外键把他们关联起来。外键的作用：能够让多个表进行关联，使表与表之间有联系，实现共性抽取。如果数据项比较多的情况下，把所有数据都存放在一个表中，如果表太大，影响操作效率。解决办法就是把一个表拆分成多个表，并且用外键去关联。例子：如果要设计一个员工表1）员工表：编号、姓名、年龄、性别、所在分公司、所在部门2）部门表：编号、部门名称、部门经理、主要任务3）公司表：编号、分公司名，地址、电话、法人把公司和部门的数据抽取出来，形成_sql查询外键id的数据
文章浏览阅读803次，点赞14次，收藏14次。章节一讲述了OpenGL在渲染的时候需要一个Context来记录了OpenGL渲染需要的所有信息和状态，可以把上下文理解成一个大的结构体，它里面记录了当前绘制使用的颜色、是否有光照计算以及开启的光源等。不同的操作系统，都有各自的上下文创建方法，最简单的上下文可以通过创建。章节二讲述了一个一个轻量级的图形界面框架，GLFW 的是提供了处理手柄、键盘、鼠标输入章节二还创建了一个空项目章节三讲述了GLAD库是用来管理OpenGL的函数指针的，所以在调用任何OpenGL的函数之前我们需要，从而让我们。_opengl窗口颜色
文章浏览阅读1.3k次。目标：使用OpenCV cv::inRange 函数进行基本的 阈值操作， 基于像素值在HSV色度空间的范围进行对象检测理论：前一篇文章中我们学习了如何使用cv::threshold 阈值函数进行阈值操作 本文我们将学习使用 cv::inRange 来进行处理 原理是一样的但是现在我们增加了一个我们所需要的 【像素值的范围】HSV色度空间 HSV colorspaceHSV ..._inrange和cv2.threshold一起使用
文章浏览阅读154次。 瑜伽培训课程层出不穷，但市面上都没有教授瑜伽老师们如何“教”的系统培训。瑜伽行业表面看似繁荣，但大多数老师缺失教学的“灵魂”。 为此，心合瑜伽学院王梓涵院长结合多年来积累的经验以及瑜伽老师的痛点，与心合教学团队不断打磨，开创瑜伽培训先河，首创贴合瑜伽老师的『瑜伽教学法』，教学法正是指导瑜伽老师们如何上课的法门！ 不少老师们，有时会有这样的问题： “我把正确的口令讲出来了，但是会员好像不听我的口令，并没有按照口令去做，需要我不停地辅助和做示范才能完成...” 一个优秀的老师，总可以_会员病了无法来上瑜伽课怎么说
文章浏览阅读2.2w次，点赞12次，收藏113次。随机森林概述随机森林是集成学习方法bagging类中的翘楚。与集成学习boosting类的GBDT分庭抗礼。bagging类集成学习采用的方法是：用部分数据 or 部分特征 or 多个算法 训练一些模型；然后再组合这些模型，对于分类问题采用投票多数表决，回归问题采用求平均。各个模型训练之间互不影响，天生就适合并行化处理。在如今大数据时代背景下很有诱惑力。 主要效果：重点关注降低方差，..._随机森林及其调参
文章浏览阅读1.5k次，点赞2次，收藏2次。解决Exception: org.apache.hadoop.io.nativeio.NativeIO$Windows.access0(Ljava/lang/String;I)Z和Error: JAVA_HOME is incorrectly set.Please update D:\Software\hadoop260\conf\hadoop-env.cmd‘-Xmx512m’ 不是内部或外部命令，也不是可运行的程序或批处理文件。这个错误目前我知道的有以下几种解决办法：一、查看hadoop安装是_org.apache.hadoop.io.nativeio.nativeio$windows.access0(ljava/lang/string;i)z
文章浏览阅读2.6k次。我的是linux系统，那么要怎么样才能查看防火墙有没有开启呢?下面由学习啦小编给你做出详细的linux查看防火墙是否开启方法介绍!希望对你有帮助!linux查看防火墙是否开启方法一：service iptables status可以查看到iptables服务的当前状态。但是即使服务运行了,防火墙也不一定起作用,你还得看防火墙规则的设置 iptables -L在此说一下关于启动和关闭防火墙的命令:1..._linux防火墙服务找不到
文章浏览阅读109次。public class useDatrgrivView { string conn = null; string sqlComm = null; DataSet das = null; DataGridView GridView = null; //初始化,绑定 publ..._datrgridview 显示不了数据