求调!
查看原帖
求调!
528401
cybermage_liu楼主2025/1/16 20:13

恳请巨佬路过调一下

orz orz orz

#include<bits/stdc++.h>
using namespace std;
const int N=20005;
int t[N<<4],a[10005<<4],b[10005<<4],c[N<<4],ans;
bool vis[N<<4];
void pushdown(int k){
	if(t[k]!=-1){
		t[k<<1]=t[k<<1|1]=t[k];
		t[k]=-1;
	}
}
void build(int k,int l,int r){
	t[k]=0;
	if(l==r) return;
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void update(int k,int l,int r,int x,int y,int v){
	if(x<=l && r<=y){
		t[k]=v;
		return;
	}
	pushdown(k);
	int mid=l+r>>1;
	if(x<=mid) update(k<<1,l,mid,x,y,v);
	if(mid<y) update(k<<1|1,mid+1,r,x,y,v);
}
void query(int k,int l,int r){
	if(t[k]!=-1){
		if(!vis[t[k]]){
			vis[t[k]]=1;
			ans++;
		}
		return;
	}
	if(l==r) return;
	pushdown(k);
	int mid=l+r>>1;
	query(k<<1,l,mid);
	query(k<<1|1,mid+1,r);
}
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<48 || ch>57){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>=48 && ch<=57) x=x*10+ch-48,ch=getchar();
	return x*f;
}
void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int main(){
	int T=read();
	while(T--){
		memset(vis,0,sizeof(vis));
		vis[0]=1;
		ans=0;
		int n=read(),m=0;
		for(int i=1;i<=n;i++){
			a[i]=read();
			b[i]=read();
			c[++m]=a[i];
			c[++m]=b[i];
			c[++m]=b[i]+1;
		}
		sort(c+1,c+1+m);
		int len=unique(c+1,c+1+m)-c-1;
		build(1,1,len);
		for(int i=1;i<=n;i++){
			int x=lower_bound(c+1,c+1+len,a[i])-c;
			int y=lower_bound(c+1,c+1+len,b[i])-c;
			update(1,1,len,x,y,i);
		}
		query(1,1,len);
		write(ans);
		putchar('\n');
	}
	return 0;
}
2025/1/16 20:13
加载中...