線段樹。做了很長(zhǎng)時(shí)間。怎么寫都不對(duì)，看了解題報(bào)告后，發(fā)現(xiàn)題意理解錯(cuò)了。、
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=8003;
int ans[MAXN],color[MAXN];
typedef struct
{
int left,right,col;
}line;
line tree[4*MAXN];
void Create(int l,int r,int root)
{
int mid=(l+r)>>1;
tree[root].left=l;
tree[root].right=r;
tree[root].col=-1;
if(l==r-1) return;
Create(l,mid,root<<1);
Create(mid,r,(root<<1)+1);
}
void Updata(int l,int r,int col,int root)
{
int mid=(tree[root].left+tree[root].right)>>1;
if(l<=tree[root].left&&tree[root].right<=r)
{
tree[root].col=col;
return;
}
if(tree[root].col==col) return;
if(tree[root].col>=0)
{
tree[root<<1].col=tree[root].col;
tree[(root<<1)+1].col=tree[root].col;
tree[root].col=-1;
}
if(l>=mid) Updata(l,r,col,(root<<1)+1);
else if(r<=mid) Updata(l,r,col,root<<1);
else
{
Updata(l,mid,col,root<<1);
Updata(mid,r,col,(root<<1)+1);
}
}
void solve(int l,int r,int root)
{
int mid=(tree[root].left+tree[root].right)>>1;
if(tree[root].col>=0)
{
for(int i=l;i<r;i++)
color[i]=tree[root].col;
return;
}
if(tree[root].left==tree[root].right-1) return;
if(l>=mid) solve(l,r,(root<<1)+1);
else if(r<=mid) solve(l,r,root<<1);
else
{
solve(l,mid,root<<1);
solve(mid,r,(root<<1)+1);
}
}
int main()
{
//freopen("input","r",stdin);
int n;
while(scanf("%d",&n)!=EOF)
{
memset(ans,0,sizeof(ans));
memset(color,-1,sizeof(color));
Create(0,MAXN,1);
int tl,tr,tc;
for(int i=0;i<n;i++)
{
scanf("%d %d %d",&tl,&tr,&tc);
Updata(tl,tr,tc,1);
}
solve(0,MAXN,1);
for(int i=0;i<MAXN;i++)
{
if(color[i+1]!=color[i]&&color[i]!=-1)
{
ans[color[i]]++;
}
}
for(int i=0;i<MAXN;i++)
{
if(ans[i])
{
printf("%d %d\n",i,ans[i]);
}
}
printf("\n");
}
return 0;
}