题目链接:https://nanti.jisuanke.com/t/41384
题目大意:
这里线段树不能离散化,n<1e9。但是我们发现询问只有1e6。最多修改1e6次。
如果用动态开点。每次最多修改logn个点。空间复杂度O(1e6*log(1e6))。
或者用并查集
#include<bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
int L[15000005]={0}, R[15000005]={0}, sum[15000005]={0}, add[15000005]={0};
int tot=1, n;
int build(int l, int r, int i)//开点
{
++tot;
L[tot]=R[tot]=0;
sum[tot]=n+1;
return tot;
}
int update(int p, int l, int r, int i, int v)//更新
{
if(l==r)//找到点
{
sum[p]=n+1;
return 0;
}
if(i<=mid)
{
if(!L[p])
{
L[p]=build(l, mid, i);
}
update(L[p], l, mid, i, v);
}
else
{
if(!R[p])
{
R[p]=build(mid+1, r, i);
}
update(R[p], mid+1, r, i, v);
}
if(L[p]==0){
sum[p]=l;
}
else if(R[p]==0)
{
sum[p]=min(sum[L[p]], mid+1);//递归求和
}
else
sum[p]=min(sum[L[p]], sum[R[p]]);//递归求和
}
int ans=n+1;
int cx(int p, int l, int r, int LL, int RR)
{
if(LL>RR){
ans=min(ans, n+1);
return 0;
}
if(l==LL&&r==RR)//区间查询
{
ans=min(ans, sum[p]);
return 0;
}
if(RR<=mid)
{
if(L[p]==0){
ans=min(ans, LL);
return 0;
}
cx(L[p], l, mid, LL, RR);
}
else if(LL>=mid+1)
{
if(R[p]==0){
ans=min(ans, LL);
return 0;
}
cx(R[p], mid+1, r, LL, RR);
}
else
{
if(L[p]==0){
ans=min(ans, LL);
}
else
cx(L[p], l, mid, LL, mid);
if(R[p]==0){
ans=min(ans, mid+1);
}
else
ans=min(ans, sum[R[p]]);
}
}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main()
{
int m;
scanf("%d%d",&n, &m);
tot=1;
memset(L, 0, sizeof(L));
memset(R, 0, sizeof(R));
while(m--){
ans=n+1;
int x, y;
x=read(), y=read();
if(x==1){
update(1, 1, n, y, 1);
}
else{
cx(1, 1, n, y, n);
printf("%d\n", (ans==n+1)?-1:ans);
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> mp;
int Find(int x){
if(!mp.count(x)){
return x;
}
return mp[x]=Find(mp[x]);
}
int main()
{
int n, m, x, y;
scanf("%d%d", &n, &m);
while(m--){
scanf("%d%d", &x, &y);
if(x==1){
mp[y]=Find(y+1);
}
else{
int ans=Find(y);
if(ans>n){
ans=-1;
}
printf("%d\n", ans);
}
}
return 0;
}