Input
Output
Sample Input
1 5 1 4 2 6 8 10 3 4 7 10
Sample Output
4
题解
这道题老师是放在线段树专题的，很久前做一直没有A，今天想再做做看，发现之前我有一个数组没有清零之前还没有查出来。
这道题给你墙的长度有10000000，如果直接线段树上的话肯定是不行，我们看到n才10000，所以我们可以离散化一下，这样只有20000的长度了
每次区间的时候就用lazy tag就可以了
最后统计有多少种海报数的时候我们可以dfs搜一下
不是叶子结点就下放标记
当搜到叶子节点的时候我们判断一下这种海报出现过没有就可以了
1 #include<algorithm> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define N 10005 6 #define maxn 20000 7 using namespace std; 8 int T,n,cnt,num,ans; 9 int l[N],r[N]; 10 bool t[maxn]; 11 int mark[4*maxn]; 12 struct node{ 13 int num,id,p; 14 }a[2*N]; 15 bool cmp(node x,node y){ 16 if (x.num!=y.num) return x.num<y.num; 17 else return x.id<y.id; 18 } 19 void change(int v,int l,int r,int x,int y,int k){ 20 if (l==x&&r==y){ 21 mark[v]=k; 22 return; 23 } 24 if (mark[v]>0){ 25 mark[v<<1]=mark[v]; 26 mark[1+(v<<1)]=mark[v]; 27 mark[v]=0; 28 } 29 int mid=(l+r)>>1; 30 if (mid>=y) change(v<<1,l,mid,x,y,k); else 31 if (x>mid) change(1+(v<<1),mid+1,r,x,y,k); else{ 32 change(v<<1,l,mid,x,mid,k); 33 change(1+(v<<1),mid+1,r,mid+1,y,k); 34 } 35 } 36 void find(int v,int l,int r){ 37 int mid=(l+r)>>1; 38 if (l==r){ 39 if (!t[mark[v]]){ 40 t[mark[v]]=true; 41 ans++; 42 } 43 return; 44 } 45 if (mark[v]>0){ 46 mark[v<<1]=mark[v]; 47 mark[1+(v<<1)]=mark[v]; 48 mark[v]=0; 49 } 50 find(v<<1,l,mid); 51 find(1+(v<<1),mid+1,r); 52 } 53 int main(){ 54 scanf("%d",&T); 55 while (T--){ 56 memset(mark,0,sizeof(mark)); 57 memset(t,0,sizeof(t)); 58 cnt=0; 59 scanf("%d",&n); 60 for (int i=1;i<=n;i++){ 61 scanf("%d%d",&l[i],&r[i]); 62 a[++cnt].num=l[i]; a[cnt].id=i; a[cnt].p=cnt; 63 a[++cnt].num=r[i]; a[cnt].id=i; a[cnt].p=cnt; 64 } 65 sort(a+1,a+1+cnt,cmp); 66 int s; 67 num=1; 68 for (int i=2;i<=cnt;i++){ 69 s=a[i-1].id; 70 if (a[i-1].p%2) l[s]=num; 71 else r[s]=num; 72 if (a[i].num!=a[i-1].num) num++; 73 } 74 s=a[cnt].id; 75 if (a[cnt].p%2) l[s]=num; 76 else r[s]=num; 77 for (int i=1;i<=n;i++) 78 change(1,1,num,l[i],r[i],i); 79 ans=0; 80 find(1,1,num); 81 printf("%d\n",ans); 82 } 83 return 0; 84 }
原文：http://www.cnblogs.com/zhuchenrui/p/7592588.html
