【题目链接】

Time Limit: 2 Seconds Memory Limit: 65536 KB

Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.
Your task is counting the segments of different colors you can see at last.

Input

The first line of each data set contains exactly one integer n, 1 <= n <=8000, equal to the number of colored segments.

Each of the following n lines consists of exactly 3 nonnegative integers separatedby single spaces:

x1 x2 c

x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicatesthe color of the segment.

All the numbers are in the range [0, 8000], and they are all integers.

Input may contain several data set, process to the end of file.

Output

Each line of the output should contain a color index that can be seen from thetop, following the count of the segments of this color, they should be printedaccording to the color index.

If some color can’t be seen, you shouldn’t print it.

Print a blank line after every dataset.

Sample Input

5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1

Sample Output

1 1
2 1
3 1

1 1

0 2
1 1

题目意思

多组案例，每组一个n，表示操作次数，每次操作三个数字x1,x2,c，表示把x1-x2之间染成颜色c，并且连续的颜色只算一次，求最后各种颜色的出现的次数。

坑点

1.每次的区间[x1 , x2]表示的是平面端点，在一维情况下代表的是[x1+1 , x2]的点值，所以每次读入x1后都要加1。（建议纸上模拟一下）
2.有颜色0，所以mark初始为-1。
3.不是所有区间的范围小于n，而是所有区间的范围小于8000，所以应该是build(1,8000,1)，update，query同理。
4.可能中间有没有涂颜色（即-1的点），经过这些点要把pre（标记上一次颜色）重置为-1。pushdown也要将mark置为-1。
5.每组案例多输出一个换行。
6.每次操作的区间左值不一定小于等于右值。（有些题目会卡这种情况，本题没卡）。

AC代码

一个星期前卡了我一个下午，今天重写突然发现踩了坑点4。。。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define sc scanf
#define pr printf
#define rep(i,a,b) for (int i=a;i<b;i++)
#define per(i,a,b) for (int i=a;i>=b;i--)
#define intmid int mid=(left+right)>>1
using namespace std;
ll a[200000];
int book[20000];
int ql, qr;
ll val, pre = -1;
struct node
{
	int l;
	int r;
	ll mark;
}que[200000 * 4];
void pushdown(int k)
{
	if (que[k].mark != -1)
	{
		que[k << 1].mark = que[k].mark;
		que[k << 1 | 1].mark = que[k].mark;
		que[k].mark = -1;
	}
}
void build(int left, int right, int k)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = -1;
	if (left == right)
		return;
	intmid;
	build(lson);
	build(rson);
}
void update(int left, int right, int k)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark = val;
		return;
	}
	pushdown(k);
	intmid;
	update(lson);
	update(rson);
}
void query(int left, int right, int k)
{
	if (que[k].mark != -1)
	{
		if (pre != que[k].mark)
		{
			book[que[k].mark]++;
			pre = que[k].mark;
		}
		return;
	}
	if (left == right)
	{
		pre = -1;
		return;
	}
	intmid;
	query(lson);
	query(rson);
}
int main()
{
	int n;
	while (sc("%d", &n) > 0)
	{
		pre = -1;
		memset(book, 0, sizeof book);
		build(1, 8000, 1);
		ll maxn = 0;
		for (int i = 0; i < n; i++)
		{
			sc("%d%d%lld", &ql, &qr, &val);
			/* if (ql > qr) { int tt = ql; ql = qr; qr = tt; } */
			ql++;
			val++;
			maxn = max(maxn, val);
			update(1, 8000, 1);
		}
		ql = 1;
		qr = n;
		query(1, 8000, 1);
		for (int i = 1; i <= maxn; i++)
			if (book[i])
				pr("%d %d\n", i - 1, book[i]);
		pr("\n");
	}
}