> #include <iostream>
> #include <algorithm>
> #include <cstdlib>
> #include <cstdio>
> #include <cstring>
> #include <map>
> #define Mid(x) ((tree[(x)].l+tree[(x)].r)/2)
> #define Left(x) ((x)<<1)
> #define Right(x) ((x)<<1|1)
> #define Lson(x) Left(x),tree[(x)].l,Mid(x)
> #define Rson(x) Right(x),Mid(x)+1,tree[(x)].r
> using namespace std;
> const int maxn=10010;
> struct SegTree
> {
>     int l,r,key;
> } tree[maxn<<3];
> struct Poster
> {
>     int l,r;
> } poster[maxn];
> int n,a[maxn<<1],hash[maxn];
> map<int,int>pos;
> void Build(int root,int l,int r)
> {
>     tree[root].l=l,tree[root].r=r,tree[root].key=0;
>     if (l==r)return;
>     Build(Lson(root));
>     Build(Rson(root));
> }
> void Update(int root,int l,int r,int key)
> {
>     if (tree[root].l==l&&tree[root].r==r)
>     {
>         tree[root].key=key;
>         return;
>     }
>     if (tree[root].key)
>     {
>         Update(Lson(root),tree[root].key);
>         Update(Rson(root),tree[root].key);
>         tree[root].key=0;
>     }
>     if (r<=Mid(root))Update(Left(root),l,r,key);
>     else if (l>Mid(root))Update(Right(root),l,r,key);
>     else Update(Left(root),l,Mid(root),key),Update(Right(root),Mid(root)+1,r,key);
>     return;
> }
> int Query(int root)
> {
>     if (tree[root].key)
>     {
>         hash[tree[root].key]++;
>         return hash[tree[root].key]==1;
>     }
>     if (tree[root].l==tree[root].r)return 0;
>     return Query(Left(root))+Query(Right(root));
> }
> int main()
> {
>   //  freopen("input.in","r",stdin);
>    // freopen("output.out","w",stdout);
>     int total,i,tot;
>     scanf("%d",&total);
>     while (total--)
>     {
>         scanf("%d",&n);
>         for (i=0;i<n;i++)
>         {
>             scanf("%d%d",&poster[i].l,&poster[i].r);
>             a[i*2]=poster[i].l;
>             a[i*2+1]=poster[i].r;
>         }
>         sort(a,a+2*n);
>         tot=0;
>         pos.clear();
>         for (i=0;i<2*n;i++)
>         {
>             if (i>0&&a[i]==a[i-1])continue;
>             if (i>0&&abs(a[i]-a[i-1])>1)tot++;
>             pos[a[i]]=++tot;
>         }
>         Build(1,1,tot);
>         for (i=0;i<n;i++)Update(1,pos[poster[i].l],pos[poster[i].r],i+1);
>         memset(hash,0,sizeof(hash));
>         printf("%d\n",Query(1));
>     }
> }
> 
> PS：论坛中各种小数据都过，已经 离散化+点化了，不知哪里出现re问题。

• Re:线段树开大点, 因为点是两倍, 线段树至少得开 maxN * 6 (0) B10330224 2011-12-25 07:35:46