牛客NOIP暑期七天营-普及组2D

链接：https://ac.nowcoder.com/acm/contest/926/D
来源：牛客网

在一维坐标系中，给定 n条有颜色的线段，第 i条线段的左右端点分别为 li和 ri,此外它的颜色为 ci。

给定m个查询，每个查询给定一个区间 [a,b]，需要求出这个区间完全包含的线段中有多少种不同颜色的线段。

题解：说是普及组，还是需要一些水平的。简单的版本可以参考：最开始学主席树的时候的题目：SPOJ：D-query这些说起来之前那个题也可以这样做的。即是离线操作，把询问和线段一起按右端点排序，然后依次处理，对于同一种颜色，树状数组里面保存最右边的那个。

这样保证了包含的的优先级，而且只统计了依次。

（copy了一份初中生的代码。

#include<bits/stdc++.h>

using namespace std;

const int M = ;

int C,n,m,k,a[M],b[M],c[M],cnt,res[M];

void add(int x,int y)

{

    for(int i=x;i<=C+;i+=i&-i) c[i]+=y;

}

int ask(int x)

{

    int ans=;

    for(int i=x;i;i-=i&-i) ans+=c[i];

    return ans;

}

struct vv

{

    int l,r,c;

} s[M],q[M];

bool cmp(vv a,vv b)

{

    return a.r<b.r;

}

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].c);

        C=max(C,s[i].r);

    }

    for(int i=;i<=m;i++)

    {

        scanf("%d%d",&q[i].l,&q[i].r);

        q[i].c=i;

    }

    sort(s+,s++n,cmp);

    sort(q+,q++m,cmp);

    int l=;

    for(int i=;i<=m;i++)

    {

        while(s[l].r<=q[i].r && l<=n)

        {

            if(b[s[l].c]<s[l].l+)

            {

                if(!b[s[l].c]) cnt++;

                if(b[s[l].c]) add(b[s[l].c],-);

                add(s[l].l+,);

                b[s[l].c]=s[l].l+;

            }

            l++;

        }

        res[q[i].c]=cnt-ask(q[i].l);

    }

    for(int i=;i<=m;i++) printf("%d\n",res[i]);

}

巴特西

牛客NOIP暑期七天营-普及组2D

最新文章

热门文章