吉林沈阳网站建设/中国制造网

就是看区间内有多少张不同的海报，唯一的问题是墙太长，需要离散化一下海报的宽度；

最好的理解方式就是阅读代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<climits>
#define LL long longusing namespace std;#define maxn 500010
#define ls o*2,l,m
#define rs o*2+1,m+1,r
#define GETM (l+r)/2using namespace std;
int _set[maxn*2];
bool vis[11000];
int fin_ans;
void pushdown(int o,int l,int r)
{if(_set[o]!=-1){_set[o*2]=_set[o];_set[o*2+1]=_set[o];_set[o]=-1;}
}
void updata(int o,int l,int r,int tl,int tr,int setv)
{if(tl<=l && r<=tr){_set[o]=setv;return ;}int m=GETM;pushdown(o,l,r);if(tl<=m)updata(ls,tl,tr,setv);if(m<tr)updata(rs,tl,tr,setv);
}//void query(int o,int l,int r)//不必一直pushdown
//{
//    if(l==r){
//        if(!vis[_set[o]]) {
//            fin_ans++;
//            vis[_set[o]]=true;
//        }
//        return ;
//    }
//    pushdown(o,l,r);
//    int m=(l+r)/2;
//    query(o*2,l,m);
//    query(o*2+1,m+1,r);
//}void query(int o,int l,int r) {if (_set[o] != -1) {if (!vis[_set[o]]) fin_ans ++;vis[_set[o] ] = true;return ;}if (l == r) return ;int m = GETM;query(ls);query(rs);
}
int arr_l[11000];
int arr_r[11000];
int temp[41000];
int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);int i,pos=0;for(i=0;i<n;++i){scanf("%d%d",&arr_l[i],&arr_r[i]);temp[pos++]=arr_l[i];temp[pos++]=arr_r[i];}int t=1;sort(temp,temp+pos);int tt=unique(temp,temp+pos)-temp;memset(_set,-1,sizeof(_set));memset(vis,false,sizeof(vis));for(i=0;i<n;++i){int l=lower_bound(temp,temp+tt,arr_l[i])-temp;int r=lower_bound(temp,temp+tt,arr_r[i])-temp;updata(1,0,tt-1,l,r,i);}fin_ans=0;query(1,0,tt-1);printf("%d\n",fin_ans);}
}