우 객 다 교 6 차 전 I 팀 로켓 (선분 수)

링크:https://www.nowcoder.com/acm/contest/144/I 우 객 망 
제목 설명
There are n trains running between Kanto and Johto region. Assuming the railway is a number line, the i-th train travels from coordinate li to coordinate ri (both inclusive). One day, m Team Rocket members invaded the railway system successfully. The i-th Team Rocket member was going to destroy the transportation hub with coordinate xi. Once a transportation hub within the driving range of a train is destroyed, the train's itinerary will be canceled immediately. Giovanni wants to know how many train trips will be firstly canceled after each attack. After all the attacks finished, for each train Giovanni needs to know that in which attack its itinerary was firstly canceled, or it was unaffected at all.
입력 설명:

The input starts with one line containing exactly one integer T, which is the number of test cases.

For each test case, the first line contains two integers n and m, indicating the number of trains and the number of Team Rocket members.

Each of the next n lines contains 2 integers li and ri, indicating the driving range of the i-th train.

Each of the next m lines contains exactly one integer yi. , where xi is the transportation hub that Team Rocket members would destroy in the i-th attack, resi-1 is the product of the indexes of trips cancelled by the (i-1)-th attack and  means exclusive or. 

If no such trip exists, resi-1 is considered to be 0.

- 1 ≤ T ≤ 5.
- 1 ≤ n,m ≤ 2 x 105.
- -109 ≤ li ≤ ri ≤ 109.
- -109 ≤ xi ≤ 109.

출력 설명:

For each test case, output one line "Case #x:" first, where x is the test case number (starting from 1).

Then output m lines, each line of which contains exactly one integer, indicating the number of train trips firstly canceled after the i-th attack.

Finally output one line, containing n integers, where the i-th integer is the time when the i-th train trip is firstly canceled or 0 if it is not affected.

예시 1
입력
복제 하 다.

1
3 4
1 3
2 6
-999 1000000000
-1000
1
5
2

출력
복제 하 다.

Case #1:
0
2
1
0
2 3 2

제목: 두 곳 사이 에 n 대의 기차 가 있 고 기차 마다 운행 구간 [l, r] 이 있다.그 다음 에 m 차례 의 폭격 이 있 을 것 이다. 매번 좌표 가 x 인 곳 을 폭격 할 것 이다. 만약 에 x 가 특정한 기차 의 운행 구간 사이 에 있 으 면 이 기 차 는 운행 을 중단 할 것 이다.지금 은 매번 조작 할 때마다 몇 대의 기차 가 처음으로 운행 을 멈 추 게 하 는 지, 그리고 모든 기 차 는 몇 번 의 폭격 후에 처음으로 운행 을 멈 추 게 하 는 지, 만약 운행 을 멈 추 지 않 았 다 면 0 을 수출 해 야 한다.
제목 사고: 우 리 는 두 곳 을 하나의 직선 으로 볼 수 있 습 니 다. 모든 기차 가 하나의 운행 구간 [l, r] 이 있 기 때문에 우 리 는 모든 기 차 를 구간 의 왼쪽 점 l 에 따라 작은 것 에서 큰 것 으로 정렬 한 다음 에 선분 수 를 통 해 구간 의 오른쪽 점 r 의 최대 치 를 유지 할 수 있 습 니 다.매번 폭격 하 는 x 에 대해 서 는 구간 [l, r] 이 l < = x < = r 를 만족 시 키 는 기차 에 만 영향 을 미 치기 때문에 우 리 는 먼저 2 분 동안 l < = x 를 만족 시 키 는 구간 을 찾 은 다음 에 선분 나무 로 모든 r > = x 구간 을 갱신 할 수 있다. 각 점 마다 첫 번 째 운행 정지 로 인 한 영향 만 기록 해 야 하기 때문에 한 대의 기차 가 운행 이 중단 되면 우 리 는 그 오른쪽 구간 을 - inf 로 설정 할 수 있다.이렇게 하면 공헌 이 반복 되 지 않 을 것 이다.온라인 트 리 업데이트 과정 은 한 구간 의 오른쪽 점 의 최대 치 는 x 보다 작 으 면 계속 업데이트 하지 않 아 도 되 고 많은 시간 을 절약 할 수 있 습 니 다.이렇게 균등 하 게 펼 쳐 진 총 시간의 복잡 도 는 O (nlogn) 일 것 이다.
구체 적 으로 코드 보기:

#include 
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lowbit(x) x&-x
#define pb push_back
#define MP make_pair
#define clr(a) memset(a,0,sizeof(a))
#define _INF(a) memset(a,0x3f,sizeof(a))
#define FIN freopen("in.txt","r",stdin)
#define fuck(x) cout<pii;
typedef pairpll;
typedef vector VI;
const int MX=2e5+7;
const int mod=998244353;
const int inf=0x3f3f3f3f;

int T,n,q;
ll res;
int ret;
struct node{
	int l,r,id;

	bool operator>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int L,int R,int x,int index,int l,int r,int rt){
	if(L>R || l>r) return; 
	if(mxr[rt]>1;
	if(L<=m) update(L,R,x,index,lson);
	if(R>m) update(L,R,x,index,rson);
	push_up(rt);
}

int main(){
	//FIN;
	cin>>T;
	for(int cas=1;cas<=T;cas++){
		clr(ans);
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a[i].l,&a[i].r);
			p[i]=a[i].l;
			a[i].id=i;
		}
		sort(a+1,a+n+1);
		sort(p+1,p+n+1);
		build(1,n,1);
		res=ret=0;
		int x;
		printf("Case #%d:
",cas);
		for(int i=1;i<=q;i++){
			scanf("%d",&x);
			x^=res;
			int pos=upper_bound(p+1,p+n+1,x)-p;pos--;
			res=1;ret=0;
			update(1,pos,x,i,1,n,1);
			printf("%d
",ret);
			if(ret==0) res=0;
		}
		for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'
':' ');
	}
	return 0;
}