HDU 4107 Gangster（线段树 特殊懒惰标记）

两种做法。

第一种：标记区间最大值和最小值，若区间最小值>=P，则本区间+2c，若区间最大值<P，则本区间+c。非常简单的区间更新。

最后发一点牢骚：最后query查一遍就行，我这个2B竟然写了个for循环每个点查了一遍orz……然后比赛的时候就一直TLE还查不出原因……感觉线段树对我就像个诅咒一样，每场必不出，不管是多么简单的线段树，都会错在千奇百怪的地方……说到底也不过是对线段树掌握的不扎实罢了，sigh……以后要多加练习！

#include <cstdio>
#include <cstring>
#include <cstdlib>

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define lc rt << 1
#define rc rt << 1 | 1

using namespace std;

const int MAXN = 200100;

int N, M, P;
int sum[MAXN << 2];
int maxi[MAXN << 2];
int mini[MAXN << 2];
int lazy[MAXN << 2];

void build( int l, int r, int rt )
{
    sum[rt] = lazy[rt] = 0;
    maxi[rt] = 0;
    mini[rt] = 0;
    if ( l == r ) return;
    int m = ( l + r ) >> 1;
    build( lson );
    build( rson );
    return;
}

inline void PushDown( int rt, int m )
{
    if ( lazy[rt] )
    {
        lazy[lc] += lazy[rt];
        lazy[rc] += lazy[rt];
        sum[lc] += lazy[rt]*(m - (m >> 1) );
        sum[rc] += lazy[rt]*(m >> 1);
        maxi[lc] += lazy[rt], mini[lc] += lazy[rt];
        maxi[rc] += lazy[rt], mini[rc] += lazy[rt];
        lazy[rt] = 0;
    }
    return;
}

inline void PushUp( int rt )
{
    sum[rt] = sum[lc] + sum[rc];
    maxi[rt] = maxi[lc] > maxi[rc] ? maxi[lc] : maxi[rc];
    mini[rt] = mini[lc] < mini[rc] ? mini[lc] : mini[rc];
    return;
}

inline void update( int L, int R, int val, int l, int r, int rt )
{
    if ( L <= l && r <= R )
    {
        if ( maxi[rt] < P )
        {
            lazy[rt] += val;
            sum[rt] += val*(r - l + 1);
            maxi[rt] += val;
            mini[rt] += val;
            return;
        }
        else if ( mini[rt] >= P )
        {
            lazy[rt] += 2*val;
            sum[rt] += 2*val*(r - l + 1);
            maxi[rt] += 2*val;
            mini[rt] += 2*val;
            return;
        }
    }
    if ( l == r ) return;
    PushDown( rt, r - l + 1 );

    int m = ( l + r ) >> 1;
    if ( L <= m ) update( L, R, val, lson );
    if ( R > m )  update( L, R, val, rson );
    PushUp( rt );

    return;
}

bool first;

void query( int l, int r, int rt )
{
    if ( l == r )
    {
        if ( first ) putchar(' ');
        first = true;
        printf( "%d", sum[rt] );
        return;
    }
    PushDown( rt, r - l + 1 );
    int m = ( l + r ) >> 1;
    query( lson );
    query( rson );
    return;
}

int main()
{
    while ( scanf( "%d%d%d", &N, &M, &P ) == 3 )
    {
        build( 1, N, 1 );
        for ( int i = 0; i < M; ++i )
        {
            int a, b, c;
            scanf( "%d%d%d", &a, &b, &c );
            update( a, b, c, 1, N, 1 );
        }
        first = false;
        query( 1, N, 1 );
        puts("");
    }
    return 0;
}

第二种做法：线段树的特殊懒惰标记，方法跟 HDU 3954 一样。代码稍微改改就行。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define lc rt << 1
#define rc rt << 1 | 1

using namespace std;

const int MAXN = 200022;
const int INF = 1 << 30;

struct node
{
    int exp, level;
    int min_dis;
    int flag;
};

int N, M, P;
int K;
node Tr[ MAXN << 2 ];
int sum[20];

void build( int l, int r, int rt )
{
    Tr[rt].exp = Tr[rt].flag = 0;
    Tr[rt].level = 1;
    Tr[rt].min_dis = sum[1];
    if ( l == r ) return ;
    int m = ( l + r ) >> 1;
    build( lson );
    build( rson );
    return;
}

void PushDown( int rt )
{
    if ( Tr[rt].flag )
    {
        Tr[lc].exp += Tr[rt].flag * Tr[lc].level;
        Tr[lc].min_dis -= Tr[rt].flag;
        Tr[lc].flag += Tr[rt].flag;

        Tr[rc].exp += Tr[rt].flag * Tr[rc].level;
        Tr[rc].min_dis -= Tr[rt].flag;
        Tr[rc].flag += Tr[rt].flag;

        Tr[rt].flag = 0;
    }
    return;
}

void PushUp( int rt )
{
    Tr[rt].level = max( Tr[lc].level, Tr[rc].level );
    Tr[rt].exp = max( Tr[lc].exp, Tr[rc].exp );
    Tr[rt].min_dis = min( Tr[lc].min_dis, Tr[rc].min_dis );
    return;
}

void Update( int L, int R, int v, int l, int r, int rt )
{
    if ( l == r )
    {
        Tr[rt].exp += Tr[rt].level * v;
        while ( Tr[rt].exp >= sum[ Tr[rt].level ] )
            ++Tr[rt].level;
        Tr[rt].min_dis = ( sum[ Tr[rt].level ] - Tr[rt].exp ) / Tr[rt].level;
        if( ( sum[ Tr[rt].level ] - Tr[rt].exp ) % Tr[rt].level ) ++Tr[rt].min_dis;
        return;
    }
    int m = ( l + r ) >> 1;

    if ( L == l && r == R )
    {
        if ( v >= Tr[rt].min_dis )
        {
            PushDown(rt);
            if ( R <= m ) Update( L, R, v, lson );
            else if ( L > m ) Update( L, R, v, rson );
            else
            {
                Update( L, m, v, lson );
                Update( m + 1, R, v, rson );
            }
            PushUp(rt);
        }
        else
        {
            Tr[rt].exp += Tr[rt].level * v;
            Tr[rt].min_dis -= v;
            Tr[rt].flag += v;
        }
        return;
    }

    PushDown(rt);

    if ( R <= m ) Update( L, R, v, lson );
    else if ( L > m ) Update( L, R, v, rson );
    else
    {
        Update( L, m, v, lson );
        Update( m + 1, R, v, rson );
    }

    PushUp(rt);

    return;
}

bool first;

void Query( int l, int r, int rt )
{
    if ( l == r )
    {
        if ( first ) putchar(' ');
        first = true;
        printf( "%d", Tr[rt].exp );
        return;
    }
    PushDown(rt);
    int m = ( l + r ) >> 1;
    Query( lson );
    Query( rson );
    return;
}

int main()
{
    K = 2;
    while ( scanf( "%d%d%d", &N, &M, &P ) == 3 )
    {
        sum[1] = P;
        sum[2] = INF;

        build( 1, N, 1 );
        while ( M-- )
        {
            int a, b, c;
            scanf( "%d%d%d", &a, &b, &c );
            Update( a, b, c, 1, N, 1 );
        }
        first = false;
        Query( 1, N, 1 );
        puts("");
    }
    return 0;
}