首页 > 代码库 > luogu P2345 奶牛集会
luogu P2345 奶牛集会
二次联通门 : luogu P2345 奶牛集会
/* luogu P2345 奶牛集会 权值线段树 以坐标为下标, 坐标为值建立线段树 对奶牛按听力由小到大排序 对于要查的牛 每次第i次放入奶牛起作用的v就是vi; 每次ans+=(xi*sum-sumxl)*vi+(sumxr-xi*sum)*vi */ #include <algorithm> #include <cstdio> #define Max 400003 void read (int &now) { now = 0; register char word = getchar (); while (word < ‘0‘ || word > ‘9‘) word = getchar (); while (word >= ‘0‘ && word <= ‘9‘) { now = now * 10 + word - ‘0‘; word = getchar (); } } inline int min (int a, int b) { return a < b ? a : b; } inline int max (int a, int b) { return a > b ? a : b; } inline int abs (int a) { return a > 0 ? a : -a; } struct Segment_Tree_Data { Segment_Tree_Data *Left, *Right; int l, r; int key; int Mid; int Count; Segment_Tree_Data () { Mid = 0; Left = Right = NULL; key = 0; Count = 0; } } *Root; class Segment_Tree_Type { public : void Build (Segment_Tree_Data *&now, int l, int r) { now = new Segment_Tree_Data (); now->l = l; now->r = r; if (l == r) return ; now->Mid = l + r >> 1; Build (now->Left, l, now->Mid); Build (now->Right, now->Mid + 1, r); } void Updata (Segment_Tree_Data *&now, int pos, int to) { if (now->l == now->r) { now->key += to; now->Count++; return ; } if (pos <= now->Mid) Updata (now->Left, pos, to); else Updata (now->Right, pos, to); now->key = now->Left->key + now->Right->key; now->Count = now->Left->Count + now->Right->Count; } int Query (Segment_Tree_Data *&now, int l, int r) { if (l <= now->l && r >= now->r) return now->key; int res = 0; if (l <= now->Mid) res += Query (now->Left, l, min (now->Mid, r)); if (r > now->Mid) res += Query (now->Right, max (now->Mid + 1, l), r); return res; } int Query_number_Count (Segment_Tree_Data *&now, int l, int r) { if (l <= now->l && r >= now->r) return now->Count; int res = 0; if (l <= now->Mid) res += Query_number_Count (now->Left, l, min (now->Mid, r)); if (r > now->Mid) res += Query_number_Count (now->Right, max (now->Mid + 1, l), r); return res; } }; int N; Segment_Tree_Type Tree; struct Cow_Data { int pos; int value; bool operator < (const Cow_Data &now) const { return now.value > value; } }; Cow_Data cow[Max]; int main (int argc, char *argv[]) { read (N); int pos, Value; long long Answer = 0; Tree.Build (Root, 0, Max); for (int i = 1; i <= N; i++) { read (cow[i].value); read (cow[i].pos); } std :: sort (cow + 1, cow + 1 + N); Tree.Updata (Root, cow[1].pos, cow[1].pos); for (int i = 2; i <= N; i++) { Tree.Updata (Root, cow[i].pos, cow[i].pos); register long long now = Tree.Query_number_Count (Root, 1, cow[i].pos - 1); Answer += (long long) cow[i].value * (cow[i].pos * now - Tree.Query (Root, 0, cow[i].pos - 1)); Answer += (long long) cow[i].value * (Tree.Query (Root, cow[i].pos + 1, Max) - cow[i].pos * (i - now - 1)); } printf ("%lld", Answer); return 0; }
luogu P2345 奶牛集会
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。