首页 > 代码库 > URAL 2014 Zhenya moves from parents 线段树
URAL 2014 Zhenya moves from parents 线段树
题目链接:点击打开链接
题意:
给定一张银行卡的n条记录:
val day.mon hour:min
表示这张卡在这个时间有一条交易。
输出n行,对于输出的第i行表示:根据前i件记录,可以推测出这张卡的最大透支额度是多少。
即:把前i个记录按时间排个序,跑一遍,输出过程中的最小值。
思路:
我们可以认为前i-1个事件已经有序,并且每个事件都有个过程最小值。
1、当插入第i个事件时,这个事件的最小值就是前面事件(前面事件指的是前i-1个事件中,按时间排序后在i事件发生前的事件)的前缀和+当前事件的val。
2、插入第i个事件后,对于这个事件后面的事件(后面也指的是按时间排序后发生在i事件后的事件)的最小值都要+=val
这样就容易想到用线段树维护了。
练习时比较紧张就直接用了2棵线段树,W表示维护前缀和。M表示维护最小值。
先对输入的事件排序,得到的顺序就是线段树中的标号。
然后再排回成输入顺序,按上述操作,每次输出M线段树中的最小值。
对于未插入的点的最小值我们认为是inf, 点权是0
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> using namespace std; template <class T> inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } typedef long long ll; #define Lson(x) (x<<1) #define Rson(x) (x<<1|1) #define L(x) tree[x].l #define R(x) tree[x].r #define Sum(x) tree[x].sum #define Lazy(x) tree[x].lazy #define Siz(x) tree[x].siz #define Min(x) tree[x].min const int N = 101000; struct Segment_Tree{ struct node{ int l, r; ll sum, lazy, siz, min; }tree[N << 2]; void push_down(int id){ if (Lazy(id)){ Lazy(Lson(id)) += Lazy(id); Lazy(Rson(id)) += Lazy(id); Sum(Lson(id)) += Lazy(id) * Siz(Lson(id)); Sum(Rson(id)) += Lazy(id) * Siz(Rson(id)); Min(Lson(id)) += Lazy(id); Min(Rson(id)) += Lazy(id); Lazy(id) = 0; } } void push_up(int id){ Sum(id) = Sum(Lson(id)) + Sum(Rson(id)); Min(id) = min(Min(Lson(id)), Min(Rson(id))); } void build(int l, int r, ll val, int id){ L(id) = l; R(id) = r; Siz(id) = r - l + 1; Lazy(id) = Sum(id) = Min(id) = 0; if (l == r){ Sum(id) = Min(id) = val; return; } int mid = (l + r) >> 1; build(l, mid, val, Lson(id)); build(mid + 1, r, val, Rson(id)); push_up(id); } ll query_sum(int l, int r, int id){ if (l == L(id) && R(id) == r){ return Sum(id); } push_down(id); int mid = (L(id) + R(id)) >> 1; if (r <= mid) return query_sum(l, r, Lson(id)); else if (mid < l) return query_sum(l, r, Rson(id)); else return query_sum(l, mid, Lson(id)) + query_sum(mid + 1, r, Rson(id)); } ll query_min(int l, int r, int id){ if (l == L(id) && R(id) == r){ return Min(id); } push_down(id); int mid = (L(id) + R(id)) >> 1; if (r <= mid) return query_min(l, r, Lson(id)); else if (mid < l) return query_min(l, r, Rson(id)); else return min(query_min(l, mid, Lson(id)), query_min(mid + 1, r, Rson(id))); } void updata(int l, int r, ll val, int id){ if (l == L(id) && R(id) == r){ Lazy(id) += val; Min(id) += val; Sum(id) += Siz(id) * val; return; } push_down(id); int mid = (L(id) + R(id)) >> 1; if (r <= mid) updata(l, r, val, Lson(id)); else if (mid < l) updata(l, r, val, Rson(id)); else { updata(l, mid, val, Lson(id)); updata(mid + 1, r, val, Rson(id)); } push_up(id); } void updata_pos(int pos, ll val, int id){ if (L(id) == R(id)){ Min(id) = Sum(id) = val; return; } push_down(id); int mid = (L(id) + R(id)) >> 1; if (pos <= mid) updata_pos(pos, val, Lson(id)); else updata_pos(pos, val, Rson(id)); push_up(id); } }W, M; struct Event{ ll val; int a, b, c, d, seg_id, id; }e[N]; bool cmp(Event x, Event y){ if (x.b != y.b)return x.b<y.b; if (x.a != y.a)return x.a<y.a; if (x.c != y.c)return x.c<y.c; return x.d<y.d; } bool cmp_query(Event x, Event y){ return x.id < y.id; } int n; void input(){ for (int i = 1; i <= n; i++) { rd(e[i].val); rd(e[i].a); rd(e[i].b); rd(e[i].c); rd(e[i].d); e[i].id = i; } sort(e + 1, e + n + 1, cmp); for (int i = 1; i <= n; i++) e[i].seg_id = i; sort(e + 1, e + n + 1, cmp_query); } int main(){ while (~scanf("%d", &n)){ input(); W.build(1, n, 0, 1); M.build(1, n, 1e9, 1); ll ans; for (int i = 1; i <= n; i++) { ll presum = W.query_sum(1, e[i].seg_id, 1); W.updata_pos(e[i].seg_id, e[i].val, 1); presum += e[i].val; M.updata_pos(e[i].seg_id, presum, 1); if (e[i].seg_id < n) M.updata(e[i].seg_id + 1, n, e[i].val, 1); ans = M.query_min(1, n, 1); if(ans > 0) ans = 0; pt(ans); putchar('\n'); } } return 0; }
URAL 2014 Zhenya moves from parents 线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。