[ZOJ1610]Count the Colors

Description

画一些颜色段在一行上，一些较早的颜色就会被后来的颜色覆盖了。

你的任务就是要数出你随后能看到的不同颜色的段的数目。

Input

每组测试数据第一行只有一个整数n, 1 <= n <= 8000,等于填色的次数

接下来的n行每行有三个非负整数，他们之间用一个空格分开。

x1 x2 c

x1和x2表示填色段最左边的点和最右边的点， c表示填进的颜色。

所有数字都是在[0..8000]这个范围里的整数。

输入有多组测试数据，最后以文件结束符为结束。

Output

输出的每一行都是最后能看到的颜色的数字，还有这种颜色的段数。

如果这种颜色最后不能见到，就不要打印出来。

每组数据后面跟一个空行。

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

线段树维护当前节点的颜色，如果颜色相同则为一个颜色，颜色不同为-1，无颜色为-2，最后统计的时候先序遍历递归即可

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=8e3;

int tree[N*5+100],kind[N*5+100];

int cnt;

int read(){

    int x=0,f=1;char ch=getchar();

    for (;ch<'0'||ch>'9';ch=getchar())    if (ch=='-')    f=-1;

    for (;ch>='0'&&ch<='9';ch=getchar())  x=x*10+ch-'0';

    return x*f;

}

void updata(int p){//标记下传更新

    if (tree[p]>=0){

        tree[p*2]=tree[p];

        tree[p*2+1]=tree[p];

    }

    tree[p]=-2;

}

void change(int p,int l,int r,int x,int y,int t){

    if (tree[p]==t) return;//剪枝

    if (x<=l&&r<=y){

        tree[p]=t;

        return;

    }

    updata(p);

    int mid=(l+r)>>1;

    if (x<mid)   change(p*2,l,mid,x,y,t);

    if (y>mid)   change(p*2+1,mid,r,x,y,t);

}

void get(int p){//统计答案

    if (tree[p]>=0){

        if (tree[p]!=cnt){

            kind[tree[p]]++;

            cnt=tree[p];

        }

        return;

    }

    if (tree[p]==-1){cnt=-1;return;}

    get(p*2);get(p*2+1);

}

int main(){

    int n;

    while (~scanf("%d",&n)){

        memset(tree,255,sizeof(tree));

        memset(kind,0,sizeof(kind));

        for (int i=1;i<=n;i++){

            int x=read(),y=read(),t=read();

            change(1,0,N,x,y,t);

        }

        cnt=-1;

        get(1);

        for (int i=0;i<=N;i++)   if (kind[i])    printf("%d %d\n",i,kind[i]);

        printf("\n");

    }

    return 0;

}

巴特西

[ZOJ1610]Count the Colors

最新文章

热门文章