正文

洛谷p2345奶牛集会

zbtrs  zbtrs  2022-09-18  757

关键词：

题目背景

MooFest, 2004 Open

题目描述

约翰的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

输出格式：

? 单个整数：表示所有奶牛产生的音量之和

输入输出样例

输入样例#1：

输出样例#1：

57
分析：这道题如果看数据范围O(n^2)是不能过的，但是如果先按照v排序，再来暴力就能A掉，但是有没有更好的方法呢？因为已经按照v排序了，所以排除v的干扰，关键就是怎么快速求sum{|xi - xj|},绝对值化简出来要么是xi - xj,要么是xj - xi,那么我们找i之前有多少个比i小的num1，它们的和是多少x1，有多少个比i大的num2，它们的和是多少x2，那么很显然，ans += v * (num1 * x - x1 + x2 - num2 * x).那么怎么快速求出num和x1，x2呢？很显然，树状数组。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

long long n,c[50010],maxn,num[50010],ans;

struct node
{
    long long v,x;
}e[20010];

long long lowbit(long long x)
{
    return x & (-x);
}

void add(long long x,long long d)
{
    while (x <= maxn)
    {
        c[x] += d;
        x += lowbit(x);
    }
}

long long query(long long x)
{
    long long cnt = 0;
    while (x)
    {
        cnt += c[x];
        x -= lowbit(x);
    }
    return cnt;
}

void add2(long long x,long long d)
{
    while (x <= maxn)
    {
        num[x] += d;
        x += lowbit(x);
    }
}

long long query2(long long x)
{
    long long cnt = 0;
    while (x)
    {
        cnt += num[x];
        x -= lowbit(x);
    }
    return cnt;
}

bool cmp(node a,node b)
{
    return a.v < b.v;
}

int main()
{
    scanf("%lld",&n);
    for (int i = 1; i <= n; i++)
    {
    scanf("%lld%lld",&e[i].v,&e[i].x);
    maxn = max(maxn,e[i].x);
    }
    sort(e + 1,e + 1 + n,cmp);
    long long t = 0;
    for (int i = 1; i <= n; i++)
    {
        long long x = e[i].x,v = e[i].v;
        long long x1 = query(x - 1),num1 = query2(x - 1);
        long long num2 = i - 1 - num1,x2 = t - x1;
        t += e[i].x;
        ans += v * (num1 * x - x1 + x2 - num2 * x);
        add(x,x);
        add2(x,1);
    }
    printf("%lld
",ans);

    return 0;
}

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没... 查看详情

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情

洛谷p2345奶牛集会

p2345奶牛集会andp2657低头一族

做法是一样的题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为... 查看详情

题解p2345奶牛集会(代码片段)

题目一道树状数组的题。话说题目直接告诉做法是什么鬼？首先这个题直接暴力是(O(n^2))的，不能通过（评论里说可以？可能数据太水了，建议加强）考虑优化，首先对于答案里的(max)，可以直接通过排序优化掉，即把数据从小... 查看详情

洛谷p2986[usaco10mar]伟大的奶牛聚集（树形动规）

题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，查看详情

luogup2345奶牛集会

二次联通门: luoguP2345奶牛集会 /*luoguP2345奶牛集会权值线段树以坐标为下标，坐标为值建立线段树对奶牛按听力由小到大排序对于要查的牛每次第i次放入奶牛起作用的v就是vi；　　每次ans+=（xi*sum-sumxl）*vi+（... 查看详情

luogup2345奶牛集会

usaco2004moofest奶牛集会(代码片段)

题目问题描述约翰的n头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头奶牛的坐标是相... 查看详情

[usaco]2004openmoofest奶牛集会(代码片段)

奶牛集会(moofest,usaco2004open)

洛谷p1578奶牛浴场

P1578奶牛浴场题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产... 查看详情

[wc2002][洛谷p1578]奶牛浴场

洛谷题解里那个人可真是话多呢。题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛... 查看详情

洛谷p1472奶牛家谱cowpedigrees

P1472奶牛家谱CowPedigrees102通过193提交题目提供者该用户不存在标签USACO难度普及+/提高提交讨论题解最新讨论暂时没有讨论题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个... 查看详情

洛谷p1154奶牛分厩

P1154奶牛分厩农夫约翰有Ｎ（1<=Ｎ<=5000）头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号Ｓi，所有的奶牛都睡在一个有Ｋ个厩的谷仓中，厩的编号为０到Ｋ－１。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教... 查看详情

洛谷——p1154奶牛分厩

P1154奶牛分厩题目描述农夫约翰有Ｎ（1<=Ｎ<=5000）头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号Ｓi，所有的奶牛都睡在一个有Ｋ个厩的谷仓中，厩的编号为０到Ｋ－１。每头奶牛都知道自己该睡在哪一个厩中，因... 查看详情

洛谷p1154奶牛分厩

题目描述农夫约翰有Ｎ（1<=Ｎ<=5000）头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号Ｓi，所有的奶牛都睡在一个有Ｋ个厩的谷仓中，厩的编号为０到Ｋ－１。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教会... 查看详情

[usaco10mar]伟大的奶牛聚集

[USACO10MAR]伟大的奶牛聚集Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路... 查看详情