1
3
1 10
1 3
6 10

这数据结果显然是3

下面AC代码算出是 2

后面那个代码算出是 3  提交确实WA 


#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

#define inr  30010

using namespace std;

typedef struct
{
    int s;
    int left,right;
} Node;

int vis[2*inr];
Node tree[8*inr];
int mp[inr][2];
int can[2*inr],sum;
int h[10000020];

int Build(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    tree[root].s=0;
    if(left==right)
        return 0;
    int mid=(left+right)/2;
    Build(2*root,left,mid);
    Build(2*root+1,mid+1,right);
}

int Update(int root,int left,int right,int x)
{
    if(tree[root].left>right||tree[root].right<left)
        return 0;
    if(tree[root].left>=left&&tree[root].right<=right)
    {
        tree[root].s=x;
        return 0;
    }
    if(tree[root].s!=0)
    {
        tree[2*root].s=tree[root].s;
        tree[2*root+1].s=tree[root].s;
        tree[root].s=0;
    }
    Update(2*root,left,right,x);
    Update(2*root+1,left,right,x);
}


int Find(int root)
{
    if(tree[root].s!=0)         //切记两个if分开写
    {
        if(vis[tree[root].s]==0)
        {
            sum++;
            vis[tree[root].s]=1;
        }
        return 0;
    }
    if(tree[root].left==tree[root].right)
        return 0;
    Find(2*root);
    Find(2*root+1);
}

int main()
{
    int T,m,n,a,b;
    cin>>T;
    while(T--)
    {
        sum=n=0;
        scanf("%d",&m);
        memset(vis,0,sizeof(vis));
        memset(h,0,sizeof(h));
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&mp[i][0],&mp[i][1]);
            if(!h[mp[i][0]])
            {
                can[n++]=mp[i][0];
                h[mp[i][0]]=1;
            }
            if(!h[mp[i][1]])
            {
                can[n++]=mp[i][1];
                h[mp[i][1]]=1;
            }
        }
        sort(can,can+n);
        Build(1,1,n+1);
        for(int i=1; i<=n; i++)
        {
            h[can[i-1]]=i;                  //此处不同
        }
        for(int i=1; i<=m; i++)
        {
            mp[i][0]=h[mp[i][0]];
            mp[i][1]=h[mp[i][1]];
            Update(1,mp[i][0],mp[i][1],i);
        }
        Find(1);
        printf("%d\n",sum);
    }
    return 0;
}


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>

#define inr 20010

using namespace std;

typedef struct
{
    int color;
    int left,right;
}Node;

int can[2*inr];
Node tree[12*inr];
int hs[10000025],sum;
int mp[inr][2],vis[inr];

int Build(int root,int left ,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    tree[root].color=0;
    if(left==right)
        return 0;
    int mid=(left+right)>>1;
    Build(root<<1,left,mid);
    Build(root<<1|1,mid+1,right);
}

int Update(int root,int left,int right,int x)
{
    if(tree[root].left>right||tree[root].right<left)
        return 0;
    if(tree[root].left>=left&&tree[root].right<=right)
    {
        tree[root].color=x;
        return 0;
    }
    if(tree[root].color!=0)
    {
        tree[root<<1].color=tree[root].color;
        tree[root<<1|1].color=tree[root].color;
        tree[root].color=0;
    }
    Update(root<<1,left,right,x);
    Update(root<<1|1,left,right,x);
}

int Find(int root)
{
    if(tree[root].color!=0)
    {
        if(vis[tree[root].color]==0)
        {
            sum++;
            vis[tree[root].color]=1;
        }
        return 0;
    }
    if(tree[root].left==tree[root].right)
        return 0;
    Find(root<<1);
    Find(root<<1|1);
}

int main()
{
    int T,m,n;
    cin>>T;
    while(T--)
    {
        sum=m=0;
        scanf("%d",&n);
        memset (vis,0,sizeof(vis));
        memset (hs,0,sizeof(hs));
        for(int i=1; i<=n;i++)
        {
            scanf("%d%d",&mp[i][0],&mp[i][1]);
            if(!hs[mp[i][0]])
            {
                can[m++]=mp[i][0];
                hs[mp[i][0]]=1;
            }
            if(!hs[mp[i][1]])
            {
                can[m++]=mp[i][1];
                hs[mp[i][1]]=1;
            }
        }
        sort(can,can+m);
        for(int i=1;i<=m;i++)
        {
            hs[can[i-1]]=2*i-1;             //次处不同
        }
        Build(1,1,2*(m+1));
        for(int i=1;i<=n;i++)
        {
            mp[i][0]=hs[mp[i][0]];
            mp[i][1]=hs[mp[i][1]];
            Update(1,mp[i][0],mp[i][1],i);
        }
        Find(1);
        printf("%d\n",sum);
    }
    return 0;
}