전송문

제목: 두 가지 동작입니다. 1: x점을 무효화시키고, 2: x보다 큰 최소 유효점을 찾습니다.
해: 데이터가 1e9에 이르면 set이 좋지 않기 때문에 라인 트리에 따라 노드 유지보수 구간과 존재하는 유효점수를 조작하고 조회할 때 존재하는 유효점수로 가지를 자르면 된다.스케줄러:폭력이 있었던것 같은데???

#include
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e6+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,m;
ll b[N];
struct node{
	int op,x;
}qu[N];
struct T{
	int l,r;
	ll sum;
}s[N<<2];
il void pushup(int rt){
	s[rt].sum=s[rt<<1].sum+s[rt<<1|1].sum;
}
il void build(int l,int r,int rt){
	if(l==r){ //  
		s[rt].l=b[l],s[rt].r=b[l+1];
		s[rt].sum=s[rt].r-s[rt].l;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	s[rt].l=s[rt<<1].l,s[rt].r=s[rt<<1|1].r;
	pushup(rt);
}
il void update(int l,int r,int rt,int X){
	if(l==r){
		s[rt].sum--;
		return ;
	}
	int mid=(l+r)>>1;
	if(X>1;
	if(Xn) continue;
		b[++cnt]=qu[i].x;
	}
	b[++cnt]=n+5;
	sort(b+1,b+cnt+1);
	int sz=unique(b+1,b+cnt+1)-(b+1); 
	build(1,sz-1,1);	
	for(int i=1;i<=m;++i){
		if(qu[i].op==2){
			if(qu[i].x>n) printf("-1
");
			res=0;
			query(1,sz-1,1,qu[i].x);
			if(res!=0) printf("%lld
",res);
			else printf("-1
");
		}
		else{
			if(qu[i].x>n) continue;
			update(1,sz-1,1,qu[i].x);
		}
	}
	return 0;
}

문제풀이는 맵으로 시뮬레이션하고 쉽게 쓸 수 있는 메뉴를 모으기;

#include
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e6+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,m;
unordered_map fa;
il int find(int x){
	if(!fa.count(x)) return x;
	return fa[x]=find(fa[x]);
} 
int main(){
	std::ios::sync_with_stdio(0);cin.tie(0);
	scanf("%d%d",&n,&m);
	int op,x;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&op,&x);
		if(op==1)	fa[x]=find(x+1);
		else{
			int ans=find(x);
			printf("%d
",(ans>n?-1:ans));
		}
	}
	return 0;
}