题目大意是一个人出国留学只用信用卡消费，会出现某天有金钱变化，这些都只会有两种情况，一种是挣钱，一种是花钱，如果钱不够就需要用信用卡透支。这些天还会像家里的父亲寄一封信来说明当天支出和收入。但是由于快递不行，所以到达父亲手里的信封的时间是乱序的，问每当收到一封信，父亲能推算的最大透支额度是多少。
思路：
线段树
先把时间离散化，然后对每一封信，用线段树更新当前天到最晚天的收支，最后用线段树维护当前所有天的最小值即是结果。
#include <bits/stdc++.h> using namespace std; int n; const int maxn = 100000 + 10; struct Letter { int val, t; }L[maxn]; map<int,int> id; const int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int daysec = 24 * 60 * 60; typedef long long ll; ll sumv[maxn<<2], minv[maxn<<2], pos[maxn], add[maxn<<2]; void pushdown(int o, int l, int r) { if(add[o]) { int m = (l+r)>>1; add[o<<1] += add[o]; add[o<<1|1] += add[o]; sumv[o<<1] += add[o] * (m - l + 1); sumv[o<<1|1] += add[o] * (r - m); minv[o<<1] += add[o]; minv[o<<1|1] += add[o]; add[o] = 0; } } void pushup(int o, int l, int r) { sumv[o] = sumv[o<<1] + sumv[o<<1|1]; minv[o] = min(minv[o<<1], minv[o<<1|1]); } ll qsum(int o, int l, int r, int ql, int qr) { if(ql <= l && qr >= r) { return sumv[o]; } pushdown(o, l, r); int m = (l+r)>>1; ll sum = 0; if(ql <= m) sum += qsum(o<<1, l, m, ql, qr); if(qr > m) sum += qsum(o<<1|1, m + 1, r, ql, qr); return sum; } ll qmin(int o, int l, int r, int ql, int qr) { if(ql <= l && qr >= r) { return min(0ll, minv[o]); } pushdown(o, l, r); int m = (l+r)>>1; ll minv = 0; if(ql <= m) minv = min(minv, qmin(o<<1, l, m, ql, qr)); if(qr > m) minv = min(minv, qmin(o<<1|1, m + 1, r, ql, qr)); return minv; } void update(int o, int l, int r, int ql, int qr, int V) { if(ql <= l && qr >= r) { sumv[o] += (ll)V * (r - l + 1); minv[o] += (ll)V; add[o] += (ll)V; return; } pushdown(o, l, r); int m = (l+r)>>1; if(ql <= m) update(o<<1, l, m, ql, qr, V); if(qr > m) update(o<<1|1, m + 1, r, ql, qr, V); pushup(o, l, r); } int main(int argc, char const *argv[]) { scanf("%d", &n); vector<int> T; for(int i = 0; i < n; ++i) { int d, m, h, s; scanf("%d %d.%d %d:%d", &L[i].val, &d, &m, &h, &s); int sec= s * 60 + h * 3600; int day = 0; for(int j = 1; j < m; ++j) day += month[j]; day += d; sec += daysec * day; L[i].t = sec; T.push_back(sec); } sort(T.begin(), T.end()); int cnt = 0; for(int i = 0; i < (int)T.size(); ++i) { id[T[i]] = ++cnt; } for(int i = 0; i < n; ++i) { L[i].t = id[L[i].t]; pos[L[i].t] = i; } for(int i = 0; i < n; ++i) { int val = L[i].val, t = L[i].t; update(1, 1, n, t, n, val); printf("%lld\n", qmin(1, 1, n, 1, n)); } return 0; }