poj 2528 poster经典线段树+lazy+离散化

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int maxn=10010;
  6 #define lson l,m,rt<<1
  7 #define rson m+1,r,rt<<1|1
  8 int a[maxn];int b[maxn];int x[maxn*3];int flag[maxn];
  9 int cor[maxn<<4];
 10 int cnt=0;
 11 int trans(int num,int l,int r)
 12 {
 13    // int m=(l+r)>>1;
 14   //  if(num==x[m]) return m;
 15   //  if(num>x[m]) return trans(num,m+1,r);
 16    // if(num<trans) return trans(num,l,m);
 17     while(l<=r)
 18     {
 19         int m=(l+r)>>1;
 20         if(x[m]==num) return m;
 21         if(num>x[m]) l=m+1;
 22         else r=m;
 23     }
 24     return -1;
 25 }
 26 void pushdown(int rt)
 27 {
 28     if(cor[rt]!=-1)
 29     {
 30         cor[rt<<1]=cor[rt];
 31         cor[rt<<1|1]=cor[rt];
 32         cor[rt]=-1;
 33     }
 34 }
 35 void update(int a,int b,int i,int l,int r,int rt)
 36 {
 37     if(a<=l&&b>=r)
 38     {
 39         cor[rt]=i;
 40         return;
 41     }
 42     pushdown(rt);
 43     int m=(r+l)>>1;
 44     if(a<=m) update(a,b,i,lson);
 45     if(b>m) update(a,b,i,rson);
 46 }
 47 void query(int l,int r,int rt)
 48 {
 49     if(cor[rt]!=-1)
 50     {
 51         if(!flag[cor[rt]])
 52         {
 53             cnt++;
 54             flag[cor[rt]]=1;
 55         }
 56         return;
 57     }
 58     if(l==r) return;
 59     int m=(r+l)>>1;
 60     query(lson);
 61     query(rson);
 62 }
 63 int main()
 64 {
 65     int cases,n;
 66     scanf("%d",&cases);
 67     while(cases--)
 68     {
 69         scanf("%d",&n);
 70         memset(cor,-1,sizeof(cor));
 71         int pointer=0;
 72         for(int i=0;i<n;i++)
 73         {
 74             scanf("%d%d",&a[i],&b[i]);
 75             x[pointer++]=a[i];
 76             x[pointer++]=b[i];
 77         }
 78         sort(x+1,x+pointer);
 79         int pointer2=1;
 80         for(int i=1;i<pointer;i++)
 81         {
 82             if(x[i]!=x[i-1]) x[pointer2++]=x[i];
 83         }
 84         for(int i=pointer2-1;i>=0;i--)
 85         {
 86             if(x[i]!=x[i-1]+1) x[pointer2++]=x[i-1]+1;
 87         }
 88         sort(x,x+pointer2);
 89         for(int i=0;i<n;i++)
 90         {
 91             int l=trans(a[i],0,pointer2-1);
 92             int r=trans(b[i],0,pointer2-1);
 93             update(l,r,i,0,pointer2-1,1);
 94         }
 95         cnt=0;
 96         memset(flag,0,sizeof(flag));
 97         query(0,pointer2-1,1);
 98         printf("%d
",cnt);
 99     }
100     return 0;
101 }