正文

洛谷p2345奶牛集会

third2333  third2333  2022-10-16  469

关键词：

洛谷P2345 奶牛集会
树状数组
按 v 从小到大排序消除 max 影响

 1 #include <bits/stdc++.h>
 2 #define For(i, j, k) for(int i=j; i<=k; i++)
 3 #define Dow(i, j, k) for(int i=j; i>=k; i--)
 4 #define LL long long
 5 using namespace std;
 6 inline int read() {
 7     int x = 0, f = 1;
 8     char ch = getchar();
 9     while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f = -1; ch = getchar(); }
10     while(ch>=‘0‘&&ch<=‘9‘) { x = x*10+ch-48; ch = getchar(); }
11     return x * f;
12 }
13 void write(int x) {
14     if(x<0) putchar(‘-‘), x = -x;
15     if(x>9) write(x/10);
16     putchar(x%10+48);
17 }
18 inline void writeln(int x) { write(x); putchar(‘
‘); }
19 
20 const int N = 20011; 
21 int n; 
22 struct node{
23     int v, pos; 
24 }a[N];
25 struct TT{
26     LL sum; 
27     int num; 
28 }tree[N];
29 LL sumpos, ans; 
30 
31 inline bool cmp_v(node a, node b) {
32     return a.v < b.v; 
33 }
34 
35 inline int lowbit(int x) { return x&(-x); }
36 
37 inline void add(int pos) {
38     for(int x=pos; x<=20000; x+=lowbit(x) ) {
39         ++tree[x].num;
40         tree[x].sum += pos; 
41     }
42 }
43 
44 inline TT Query(int pos) {
45     TT p; p.num = 0; p.sum = 0; 
46     for(int x=pos; x; x-=lowbit(x)) {
47         p.num += tree[x].num; 
48         p.sum += tree[x].sum; 
49     }
50     return p; 
51 }
52 
53 int main() {
54     n = read(); 
55     For(i, 1, n) {
56         a[i].v = read(); a[i].pos = read(); 
57     }
58     sort(a+1, a+n+1, cmp_v); 
59     For(i, 1, n) {
60         TT p = Query(a[i].pos); 
61         ans = ans+ a[i].v*(1ll*p.num*a[i].pos-p.sum + sumpos-p.sum-(1ll*i-1-p.num)*a[i].pos ); 
62         sumpos += a[i].pos; 
63         add(a[i].pos); 
64     }
65     printf("%lld
", ans); 
66     return 0; 
67 }

洛谷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条道路... 查看详情