#include <cstdio>
#include <algorithm>
using namespace std;

#define nocol -1
#define mulcol -2

int n, p[10000][2], cn[20000];
bool v[10001];
int Len;

struct segment
{
       int l, r, col;
       segment *lchild, *rchild;
       void construct (int , int);
       void insert (int ,int , int);
       int find ();
}*root, tree[320010];

void segment :: construct (int left, int right)
{
     if (left == right) {l = left; r= right; lchild = rchild = NULL; return;}
     l = left; r = right;
     lchild = &tree[Len ++]; rchild = &tree[Len ++];
     if (left + 1 < right)
     {
              lchild->construct (left, (left + right)/2);
              rchild->construct ((left + right)/2 + 1, right);
     }
     else
     {
         lchild->construct (left, left);
         rchild->construct (right, right);
     }
}

void segment :: insert (int left, int right, int k)
{
     if (left <= cn[l] && cn[r] <= right)
     {
           col = k;
     }
     else
     {
         if (col != k) col = mulcol;
         int mid = (l + r) / 2;
         if (left <= cn[mid] && lchild) lchild->insert (left, right, k);
         if (right >= cn[mid + 1] && rchild) rchild->insert (left, right, k);
     }
}

int segment :: find ()
{
    int tmp1, tmp2;
    if (col >= 0 && !v[col]) {v[col] = true; return 1;}
    
    if (col == nocol || v[col]) return 0;
    else if (col == mulcol)
    {
         tmp1 = tmp2 = 0;
         if (lchild) tmp1 += lchild->find ();
         if (rchild) tmp2 += rchild->find ();
         return tmp1 + tmp2;
    }
}

void solve ()
{
    int i, j, k, num;
    scanf ("%d", &n);
    for (i = 0, j = 0; i < n; i ++)
    {
        scanf ("%d %d", &p[i][0], &p[i][1]);
        cn[j ++] = p[i][0]; cn[j ++] = p[i][1];
    }
    num = j;
    sort(cn, cn + num);
    int tmp;
    for (i = 0; i < num; i ++)
    {
        for (j = i + 1; j < num; j ++)
        if (cn[i] != cn[j]) break;
        tmp = j - i - 1;
        for (; j < num; j ++)
        cn[j - tmp] = cn[j];
        num -= tmp;
    }
    Len = 0;
    root = &tree[Len ++];
    root->construct(0, num - 1);
    root->col = -1;
    for (i = 0; i < n; i ++)
    {
        root->insert (p[i][0], p[i][1], i);
    }
    memset (v, false, sizeof (v));
    
    int sum = root->find ();
    printf ("%d\n", sum);
}

int main ()
{
    int c;
    scanf ("%d", &c);
    while (c --)
    solve ();
    return 0;
}

• Re:线段树＋离散化超时了　哪位帮忙看看　？ (2745) initial 2007-09-07 19:11:51