C - Zhenya moves from parents （线段树 + lazy标记）

Zhenya moved from his parents’ home to study in other city. He didn’t take any cash with him, he only took his father’s credit card with zero balance on it. Zhenya succeeds in studies at the University and sometimes makes a little money on the side as a Maths tutor. As he makes his own money he spends only it, and when it is over he uses the credit card. Every time he gets or spends money, he sends a letter to his father, where he puts the following two things.

1. The date when it took place
2. The sum of earned or spent money

Every time receiving a letter from Zhenya, his father calculates the debt on the credit card at the moment. But here a problem arises. The point is that Russian Post delivers letters in an order different to the one they were sent in.

For example, in the first Zhenya’s letter the father read that on September 10 Zhenya spent one thousand rubles. He thought that his son had used the credit card, and now the debt is one thousand rubles. However the next day came a letter with the information that on September 9 Zhenya earned five hundred rubles. It means that half of the money he spent on September 10 was his own, and the debt on the credit card is just five hundred rubles.

Help Zhenya’s father with his account management.

Input

The first line contains an integer n which is the number of Zhenya’s letters (1 ≤n ≤ 100 000). These letters are listed in the next n lines. Description of each letter consists of the amount of money Zhenya spent or earned (in the form -c or +c accordingly, where c is an integer, 1 ≤ c ≤ 50 000) followed by both date and time when it took place (in the form of dd.MM hh:mm). All dates belong to the same year, which is not leap (i. e. there are 365 days in it). Any two letters contain either different dates or different time. The letters are listed in the order the father received them.

Output

After each received letter output what Zhenya’s father thinks the amount of the debt on the credit card is.

Example

input	output
5 -1000 10.09 21:00 +500 09.09 14:00 +1000 02.09 00:00 -1000 17.09 21:00 +500 18.09 13:00	-1000 -500 0 -500 -500

 

题目大意：Zhenya有一张信用卡，每当消费时手上有现金都优先花掉现金，否则就透支信用卡. 他也会赚钱，赚得的钱都是现金并且不会用来还信用卡.每次消费和赚钱都会发信息给他爸爸，但是信的邮寄顺序和消费时间顺序不一致. 父亲每收到一封信都要推断此时信用卡的透支状况.

思路概括：由于赚到的钱不会还卡，那么问题的核心是如何把现金和信用卡统一起来：考虑赚到的钱，虽然不会还卡，但是在后面的消费中会优先使用现金.所以赚/花的钱只会影响影响后续的行为，而不会影响之前欠款.所以按时间排序，给父亲收到信息的顺序标号，再给按时间排序的信息标号，所以我们只需要一直维护区间的最小值，然后输出出来就好

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 50;
struct node
{
    int id;
    int d, mon, m, h, miu;
}s[maxn];

int n;
int mone[maxn];
int tot[maxn];

bool cmp(node a, node b)
{
    if(a.m != b.m) return a.m < b.m;
    else
    {
        if(a.d != b.d) return a.d < b.d;
        else
        {
            if(a.h != b.h) return a.h < b.h;
            else
            {
                return a.miu < b.miu;
            }
        }
    }
}
struct nodd
{
    int lt, rt;
    ll mi, lazy;
}tree[4 * maxn];
void pushdown(int k)
{
    tree[k*2].mi += tree[k].lazy;
    tree[k*2 + 1].mi += tree[k].lazy;
    tree[k*2].lazy += tree[k].lazy;
    tree[k * 2 + 1].lazy += tree[k].lazy;
    tree[k].lazy = 0;
}
void build(int l, int r, int k)
{
    tree[k].lt = l;
    tree[k].rt = r;
    if(l == r)
    {
        tree[k].mi = 0;
        return ;
    }
    int mid = (l + r)/2;
    build(l, mid, k*2);
    build(mid + 1, r, k * 2 + 1);
    tree[k].mi = min(tree[k * 2].mi, tree[k * 2 + 1].mi);
}
void updata(int l, int r, int k, int num)
{
    int L = tree[k].lt;
    int R = tree[k].rt;
    if(L >= l && R <= r)
    {
        tree[k].mi += num;
        tree[k].lazy += num;
        return ;
    }
    if(tree[k].lazy) pushdown(k);
    int mid = (L + R) / 2;
    if(mid >= r) updata(l, r, k * 2, num);
    else if(mid < l) updata(l, r, k * 2 + 1, num);
    else
    {
        updata(l, mid, k * 2, num);
        updata(mid + 1, r, k * 2 + 1, num);
    }
    tree[k].mi = min(tree[k * 2].mi, tree[k * 2 + 1].mi);
}
int main()
{
    scanf("%d", &n);
    build(1, n, 1);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d.%d %d:%d", &s[i].mon, &s[i].d, &s[i].m, &s[i].h, &s[i].miu);
        mone[i] = s[i].mon;
        s[i].id = i;
    }
    sort(s + 1, s+ n + 1, cmp);
    for(int i=1;i<=n;i++) tot[s[i].id] = i;
    for(int i=1;i<=n;i++)
    {
        updata(tot[i], n, 1, mone[i]);
        if(tree[1].mi > 0) printf("%d\n", 0);
        else printf("%lld\n", tree[1].mi);
    }
    return 0;
}