URAL 2014 Zhenya moves from parents --线段树

题意：儿子身无分文出去玩，只带了一张他爸的信用卡，当他自己现金不足的时候就会用信用卡支付，然后儿子还会挣钱，挣到的钱都是现金，也就是说他如果有现金就会先花现金，但是有了现金他不会还信用卡的钱。他每花一次钱和挣一次钱都会给他爸发一条短信，告诉他挣/花的钱和时间，但是给出的短信顺序时间可能不是按顺序来的，然后他爸要根据现有的短信信息推测信用卡现在的负债是多少。

解法： 因为挣的钱或花的钱都只影响后面时间的负债，时间离散，每加入一个值，都更新这个pos到n的所有值，然后整个时间最小的值就是答案。结果与0取个最小值就可以了。但是一直不太了解这个原理，求大神解释。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#define lll __int64

using namespace std;

#define N 100017

lll Min[*N],mark[*N],b[N];

struct node{

    lll val,tim;

}a[N];

void pushup(int rt) { Min[rt] = min(Min[rt<<],Min[rt<<|]); }

void pushdown(int l,int r,int rt)

{

    if(mark[rt])

    {

        mark[rt<<] += mark[rt];

        mark[rt<<|] += mark[rt];

        Min[rt<<] += mark[rt];

        Min[rt<<|] += mark[rt];

        mark[rt] = ;

    }

}

void build(int l,int r,int rt)

{

    Min[rt] = mark[rt] = ;

    if(l == r) return;

    int mid = (l+r)/;

    build(l,mid,rt<<);

    build(mid+,r,rt<<|);

    pushup(rt);

}

void update(int l,int r,int aa,int bb,lll val,int rt)

{

    if(aa <= l && bb >= r)

    {

        Min[rt] += val;

        mark[rt] += val;

        return;

    }

    pushdown(l,r,rt);

    int mid = (l+r)/;

    if(aa <= mid) update(l,mid,aa,bb,val,rt<<);

    if(bb > mid)  update(mid+,r,aa,bb,val,rt<<|);

    pushup(rt);

}

lll GetTime()

{

    int date,month,hour,minu;

    scanf("%d.%d %d:%d",&date,&month,&hour,&minu);

    return (lll)month*31LL** + date*24LL* + 60LL*hour + minu;

}

int main()

{

    int n,i,j;

    scanf("%d",&n);

    for(i=;i<=n;i++)

    {

        scanf("%I64d",&a[i].val);

        a[i].tim = GetTime();

        b[i] = a[i].tim;

    }

    sort(b+,b+n+);

    build(,n+,);

    for(i=;i<=n;i++)

    {

        lll pos = lower_bound(b+,b+n+,a[i].tim)-b;

        update(,n+,pos,n,a[i].val,);

        printf("%I64d\n",min(0LL,Min[]));

    }

    return ;

}