HSGO 2020 PERMSWAP (dsu rollback + SQRT Decomposition)

#include<bits/stdc++.h>
using namespace std;

#define ll int
#define pb push_back
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=1e5+10;
const ll base=700;
const ll mod=998244353;
const long double eps=1e-10;

ll a[maxn];
ll x[maxn];
ll y[maxn];
ll n, q;
bool dd[maxn];
ll get()
{
    ll ans=0;
    for (int i=1; i<=n; i++)
    {
        if (dd[i])
            continue;
        ll h=i;
        dd[i]=1;
        while (1)
        {
            ll nxt=a[h];
            if (nxt==i)
                break;
            dd[nxt]=1;
            h=nxt;
        }
        ans++;
    }
    return n-ans;
}

bool chk[maxn];
ll res[maxn];
ll nxt[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout) ;
    }
    cin>> n>> q;
    for (int i=1; i<=n; i++)
        cin>>a[i];
    ll ans=get();
    for (int i=1; i<=q; i++)
    {
        cin>>x[i]>>y[i];
    }
    for (int i=1; i<=n; i++)
        dd[i]=0;
    //  cout <<ans<<endl;
    for (int i=1; i<=q; i+=base)
    {
        vector<ll> vt;
        ll l=i;
        ll r=min(i+base-1,q);
        for (int j=l; j<=r; j++)
        {
            dd[x[j]]=1;
            dd[a[x[j]]]=1;
            dd[y[j]]=1;
            dd[a[y[j]]]=1;
            vt.pb(x[j]);
            vt.pb(a[x[j]]);
            vt.pb(y[j]);
            vt.pb(a[y[j]]);
            swap(a[x[j]],a[y[j]]);
        }
        for (int j=r;j>=l;j--) swap(a[x[j]],a[y[j]]);

        ll cnt=0;
        for (int i=1; i<=n; i++)
        {
            if (chk[i])
                continue;
            if (!dd[i])
                continue;
            ll h=i;
            chk[i]=1;
            ll pre=i;
            while (1)
            {
                ll nxt1=a[h];
                if (dd[nxt1])
                {
                    nxt[pre]=nxt1;
                    pre=nxt1;
                }
                if (nxt1==i)
                    break;

                chk[nxt1]=1;
                h=nxt1;
            }
        }
        //for (int i=1;i<=n;i++) cout <<nxt[i]<<endl;
     //   cout <<"WTF"<<endl;
        for (int j=l; j<=r; j++)
        {
            ll p=x[j];
            bool kt=false;
            while (1)
            {
                if (p==y[j])
                {
                    kt=true;
                    break;
                }
                if (nxt[p]==x[j]) break;
                p=nxt[p];
            }
            if (!kt) ans++;
            else ans--;
            res[j]=ans;
            nxt[x[j]]=a[y[j]];
            nxt[y[j]]=a[x[j]];
            swap(a[x[j]],a[y[j]]);
        }

        for (int i=1; i<=n; i++)
            chk[i]=0;
        for (auto to:vt) dd[to]=0;


    }
    for (int i=1; i<=q; i++)
        cout <<res[i]<<endl;



}