狗屎ds题。
写了一个平衡树调了一天没调明白。
转为写分块了。
依然不理解平衡树挂在哪里了。
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define e_b emplace_back
#define p_b push_back
#define fir first
#define sec second
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define gc getchar
using namespace std;
const int N=1e5+5;
struct node{int sz,cnt,ch[2],fa,l,r,id;node(){l=r=sz=cnt=fa=ch[0]=ch[1]=0;}
}t[N<<1];
int tot;
void upd(int p){t[p].sz=t[t[p].ch[0]].sz+t[t[p].ch[1]].sz+t[p].cnt;}
void rotate(int p){int f=t[p].fa,ff=t[f].fa;bool k=(p==t[f].ch[1]),k1=(f==t[ff].ch[1]);int s=t[p].ch[k^1];t[f].ch[k]=s,t[s].fa=f,t[p].ch[k^1]=f,t[f].fa=p;t[ff].ch[k1]=p,t[p].fa=ff;
}
void splay(int p,int g){while(t[p].fa!=g){int f=t[p].fa,ff=t[f].fa;if(ff!=g)(f==t[ff].ch[0])^(p==t[f].ch[0])?rotate(p):rotate(f);rotate(p);}
}
int add(int fa,int l,int r,int id){t[++tot].sz=r-l+1,t[tot].cnt=r-l+1,t[tot].fa=fa,t[tot].l=l,t[tot].r=r,t[tot].id=id;return tot;}
int find(int k,int rt){int now=rt;while(1){if(k>=t[now].l){if(t[now].l<=k&&k<=t[now].r){splay(now,0);return now;}now=t[now].ch[1];}else now=t[now].ch[0];if(!now)return now;}
}
int lst(int rt){int now=rt;while(t[now].ch[1])now=t[now].ch[1];return t[now].id;
}
void split(int p,int k){int l=t[p].l,r=t[p].r,s=t[p].ch[1];int p2=add(p,k,r,t[p].id);t[p].r=k-1;if(s)t[s].fa=p2;t[p2].ch[1]=s;t[p].ch[1]=p2;upd(p),upd(p2);
}
map<int,int>mp[N];
int n,m,q;
signed main(){IOS;cin>>n>>m>>q;m++;for(int i=1;i<=n;i++)add(0,1,m,i),mp[i][0]=i;while(q--){int op,x,b;cin>>op;if(op==1){cin>>x>>b;int y=x+1;auto k1=mp[x].upper_bound(b);k1--;int rx=k1->sec;auto k2=mp[y].upper_bound(b);k2--;int ry=k2->sec;splay(rx,0),splay(ry,0);int rt_x=find(b,rx),rt_y=find(b,rx);split(rt_x,b),split(rt_y,b);swap(t[rt_x].ch[1],t[rt_y].ch[1]);t[t[rt_x].ch[1]].fa=rt_x,t[t[rt_y].ch[1]].fa=rt_y;mp[x][b]=t[rt_y].ch[1],mp[y][b]=t[rt_x].ch[1];//mp[x][k1->fir]=rt_x,mp[y][k2->fir]=rt_y;}else{cin>>x;cout<<lst(x)<<'\n';}}
}
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define e_b emplace_back
#define p_b push_back
#define fir first
#define sec second
#define gc getchar
using namespace std;
const int N=1e5+5;
int rd(){int x=0,f=1;char c=gc();while(c>'9'||c<'0'){if(c=='-')f=-1;c=gc();}while(c<='9'&&c>='0')x=x*10+c-'0',c=gc();return x;
}
int fin[350][N],n,m,q,B,cb;
map<int,int>mp[N];
signed main(){n=rd(),m=rd(),q=rd();B=sqrt(m);cb=m/B+bool(m%B);for(int i=1;i<=n;i++)for(int j=0;j<=cb;j++)fin[j][i]=i;while(q--){int op,a,b;cin>>op>>a;if(op==1){cin>>b;int blk=(b-1)/B+1;int x=a,y=a+1;for(int i=b;i>(blk-1)*B;i--){if(mp[x].count(i))x=mp[x][i];if(mp[y].count(i))y=mp[y][i];}swap(fin[blk][x],fin[blk][y]);mp[a][b]=a+1,mp[a+1][b]=a;}else{//for(int i=1;i<=n;i++){for(int j=0;j<=cb;j++)cout<<fin[j][i]<<' ';cout<<'\n';}for(int i=0;i<=cb;i++)a=fin[i][a];cout<<a<<'\n';}}}
upd:一开始犯了跟永无乡一样的问题