题解
如果一个 \(k\) ,其前面没有出现过 \(k-1\) ,那么回合数+1,我们令这样的数叫做断点
因此交换两个数 \(l,r\) 不会影响 \([1,l-1],[r+1,n]\) 内的断点
code
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
ll a[200005];
ll pos[200005];
void solve()
{
ll n,m;
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
ll x;
cin>>x;
pos[x]=i;
a[i]=x;
}
ll ans=1;
for(ll i=2;i<=n;i++) ans+=pos[i-1]>pos[i];
while(m--)
{
ll x,y;
cin>>x>>y;
if(x>y) swap(x,y);
ll vx=a[x],vy=a[y];
if(vx>1&&pos[vx-1]>x&&pos[vx-1]<y) ans--;
if(vx<n&&pos[vx+1]>x&&pos[vx+1]<y) ans++;
if(vy>1&&pos[vy-1]>x&&pos[vy-1]<y) ans++;
if(vy<n&&pos[vy+1]>x&&pos[vy+1]<y) ans--;
if(abs(vx-vy)==1)
{
if(vx>vy) ans--;
else ans++;
}
swap(a[x],a[y]);
swap(pos[vx],pos[vy]);
cout<<ans<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TT=1;
//cin>>TT;
while(TT--) solve();
return 0;
}
标签:Collecting,ll,pos,II,Numbers,&&,ans,vx,vy
From: https://www.cnblogs.com/pure4knowledge/p/18334378