treap題 debug中

#include <bits/stdc++.h>
#define REP(i,l,r) for(int i=(l);i<(r);i++)
#define debug(x) 1&&(cout<<#x<<':'<<x<<'\n')
#define siz(v) (ll(v.size()))
#define all(v) begin(v),end(v)
#define pb emplace_back
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
constexpr ll N = 100000, INF = 1e18;

struct node{
    int sz,val;
    node *l,*r,*p;
    node(int val=0):l(0),r(0),p(0),sz(1),val(val){}
    void pull(){
        sz = 1, p = nullptr;
        //cout<<"val:"<<val+1<<'\n';
        if(l)sz += l->sz, l->p = this;
        if(r)sz += r->sz, r->p = this;
    }
} *nodes[N+1];
ll n,m,v[N+1] = {},pos[N+1] = {};
ll rseed=712;
ll RAND(){return rseed=(rseed*0xdefaced)%1000000007;}
int size(node *p){return p?p->sz:0;}
node *anc(node *x){
    if(!x)return nullptr;
    while(x->p)x = x->p;
    return x;
}
ll orderof(node *x){
    if(!x)return 0;
    ll c = size(x->l);
    while(x->p){
        if(x==x->p->r) c+=size(x->p->l)+1;
        x = x->p;
    }
    return c;
}
node *merges(node *a,node *b){
    if(!a||!b)return a?a:b;
    if(RAND()&4) return a->r = merges(a->r,b), a->pull(), a;
    else return b->l = merges(a,b->l), b->pull(), b;
}
void split(node *o, node *&a, node *&b, int R){
    if(!o) return a=b=nullptr,void();
    if(R <= size(o->l))b=o,split(o->l,a,b->l,R);
    else a=o,split(o->r,a->r,b,R-size(o->l)-1);
    o->pull();
}
void traversal(node *o,int d=0){
    if(!o)return;
    traversal(o->l,d+1);
    REP(i,0,d) cout << '\t'; cout << "val:" << o->val+1 << '\n';
    traversal(o->r,d+1);
}
signed main(){
    //ios::sync_with_stdio(0),cin.tie(0);
    ll res,x,y;
    cin >> n >> m;
    res = n;
    REP(i,0,n) cin >> v[i], --v[i], pos[v[i]]=i;
    REP(i,0,n) if(!nodes[i]){
        node *r = nullptr;
        int j = i;
        do nodes[j] = new node(j), r = merges(r,nodes[j]), j = v[j];
        while(j != i);
        res--;
    }
    cout << res << '\n';
    //cout << "======================\n";
    //REP(k,0,n) if(nodes[k]==anc(nodes[k]))cout << "......\n",traversal(nodes[k]);
    REP(_,0,m){
        cin >> x >> y, --x, --y;
        x = pos[x], y = pos[y];
        swap(pos[v[x]],pos[v[y]]);
        swap(v[x],v[y]);
        node *u,*v,*t,*w;
        node *a=nodes[x],*b=nodes[y];
        if(anc(a) == anc(b)){
            res--;
            split(anc(a),u,v,orderof(a)+1);
            //cout<<"OAO\n",traversal(anc(u)),cout<<"OAO\n",traversal(anc(v));
            merges(v,u);
            //cout<<"= =\n",traversal(anc(a));
            //orderof(b);
            //debug(orderof(b)+1);
            split(anc(b),u,v,orderof(b)+1);
            //cout<<"OAO\n",traversal(anc(a)),cout<<"OAO\n",traversal(anc(b));
            assert(anc(a)!=anc(b));
        }else{
            res++;
            split(anc(a),u,v,orderof(a)), merges(v,u);
            split(anc(b),u,v,orderof(b)+1),merges(v,u);
            merges(anc(a),anc(b));
            assert(anc(a)==anc(b));
        }
        cout << res << '\n';
        //cout << "======================\n";
        //REP(k,0,n) if(nodes[k]==anc(nodes[k]))cout << "......\n",traversal(nodes[k]);
    }
}