这道题也有点新意，就是须要记录最小值段和最大值段，然后成段更新这个段，而不用没点去更新，达到提快速度的目的。

本题过的人非常少，由于大部分都超时了，我严格依照线段树的方法去写。一開始竟然也超时。

然后修补了两个地方就过了，详细改动的地方请參看程序。

知道最大值段和最小值段，然后修补一下就能过了。不是特别难的题目。

#include <stdio.h>

#include <string>

#include <algorithm>

using namespace std;

const int SIZE = 200002;

const int TREESIZE = SIZE + (SIZE<<1);

int N, M, P;

int segTree[TREESIZE];

int smallest[TREESIZE];

int largest[TREESIZE];

inline int lChild(int rt) { return rt<<1; }

inline int rChild(int rt) { return rt<<1|1; }

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

{

	segTree[rt] = 0;

	smallest[rt] = 0;

	largest[rt] = 0;

	if (l == r) return ;

	int m = l + ((r-l)>>1);

	build(l, m, lChild(rt));

	build(m+1, r, rChild(rt));

}

inline void pushUp(int rt)

{

	smallest[rt] = min(smallest[lChild(rt)], smallest[rChild(rt)]);

	largest[rt] = max(largest[lChild(rt)], largest[rChild(rt)]);

}

inline void pushDown(int rt)

{

	if(segTree[rt])

	{

		int l = lChild(rt), r = rChild(rt);

		largest[l] += segTree[rt];

		largest[r] += segTree[rt];

		smallest[l] += segTree[rt];

		smallest[r] += segTree[rt];

		segTree[l] += segTree[rt];

		segTree[r] += segTree[rt];

		segTree[rt] = 0;

	}

}

void update(int L, int R, int val, int l, int r, int rt)

{

	if (L <= l && r <= R)

	{

		if(largest[rt] < P)

		{

			smallest[rt] += val;

			largest[rt] += val;

			segTree[rt] += val;

			return ;

		}

		if(smallest[rt] >= P)

		{

			smallest[rt] += val<<1;

			largest[rt] += val<<1;

			segTree[rt] += val<<1;

			return;

		}

	}

	//if (r < L || R < l) return;//在这里推断也会超时

	pushDown(rt);

	int m = l + ((r-l)>>1);

	if (L <= m) update(L, R, val, l, m, lChild(rt));

	if (m < R) update(L, R, val, m+1, r, rChild(rt));

	pushUp(rt);

}

inline void pushDown_2(int rt)

{

	if (segTree[rt])

	{

		segTree[lChild(rt)] += segTree[rt];

		segTree[rChild(rt)] += segTree[rt];

	}

}

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

{

	if (l == r)

	{

		if (l != N) printf("%d ", segTree[rt]);

		else printf("%d\n", segTree[rt]);

		return ;		//记得返回。

	}

	pushDown_2(rt);

	int m = l + ((r-l)>>1);

	printTree(l, m, lChild(rt));

	printTree(m+1, r, rChild(rt));

}

int main()

{

	int a, b, c;

	while (scanf("%d %d %d", &N, &M, &P) != EOF)

	{

		build(1, N, 1);

		//memset(largest, 0, sizeof(largest)); 这样写反而超时

		//memset(smallest, 0, sizeof(smallest));

		//memset(segTree, 0, sizeof(segTree));

		while (M--)

		{

			scanf("%d %d %d", &a, &b, &c);

			update(a, b, c, 1, N, 1);

		}

		printTree(1, N, 1);

	}

	return 0;

}