Collecting Numbers II

原题链接

题解

首先，对于数字 i 如果location[ i ] < location[ i -1 ] 那么遍历次数需要+1，否则不变。

因此，对于交换的数字 x ， y 而言，他们只能影响 x-1 ， x+1 , y-1 , y+1 的遍历次数，只需要考虑有限的几种情况即可（需要特判 abs(x-y)==1 的情况）。

code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,a[N],loc[N],ans=1;

void solve(int x,int y){
    if (a[x]>1 && loc[a[x]-1]>loc[a[x]] && loc[a[x]-1]<=y) ans--;
    if (a[x]<n && loc[a[x]+1]>loc[a[x]] && loc[a[x]+1]<=y) ans++;
    
    
    if (a[y]>1 && loc[a[y]-1]<loc[a[y]] && loc[a[y]-1]>=x) ans++;
    if (a[y]<n && loc[a[y]+1]<loc[a[y]] && loc[a[y]+1]>=x) ans--;

    if (a[x]-a[y]==1) ans++;
    if (a[y]-a[x]==1) ans--;
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        loc[a[i]]=i;
    }
    for (int i=2;i<=n;i++){
        ans+=loc[i]>loc[i-1] ? 0 : 1;
    }
//    cout<<ans<<endl;
    
    int x,y;
    while (m--){
        cin>>x>>y;
        if (x>y) swap(x,y);
        
        solve(x,y);
        
        swap(loc[a[x]],loc[a[y]]);
        swap(a[x],a[y]);
        cout<<ans<<endl;
    }
    return 0;
}