题解
对于数 \(i\) 来说,如果其当前位置到最终位置上,有 \(k\) 个数不在最终位置,那么数 \(i\) 至少要走 \(k\) 次
如果这 \(k\) 个数里,有 \(m\) 个在数 \(i\) 回到最终位置时,提前回到了最终位置,那么数 \(i\) 要走 \(k-m\) 次
具象化就是一个一个的区间(起点为当前位置,终点为最终位置),数 \(i\) 要走的步数,就是其区间内不匹配的个数减去完全包裹住的小区间个数
由于环状,所以还要拆环成链
如何统计大区间内有多少完全包裹的小区间?
我么倒叙遍历,如果一个区间的左端点出现,那就令其右端点呈现
然后统计区间和,有几个右端点呈现
code
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
int n;
int ans[1000006];
int tree[2000005]={0};
int cnt[2000005]={0};
int a[200005];
void update(int now)
{
while(now<=2*n)
{
tree[now]++;
now+=lowbit(now);
}
}
int query(int now)
{
int res=0;
while(now)
{
res+=tree[now];
now-=lowbit(now);
}
return res;
}
int r[2000006];
void solve()
{
cin>>n;
memset(tree, 0, sizeof(int) * (2*n + 1));
memset(cnt, 0, sizeof(int) * (2*n + 1));
memset(r, 0, sizeof(int) * (2*n + 1));
memset(ans, 0, sizeof(int) * (n + 1));
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>i)
{
r[i]=a[i];
r[i+n]=a[i]+n;
}
else if(a[i]<i) r[i]=a[i]+n;
}
cnt[2*n+1]=0;
for(int i=2*n;i>=1;i--)
{
cnt[i]=cnt[i+1]+(a[(i-1)%n+1]!=(i-1)%n+1);
}
for(int i=2*n;i>=1;i--)
{
if(r[i])
{
int now=(r[i]-1)%n+1;
ans[now]=cnt[i+1]-cnt[r[i]+1]-(query(r[i])-query(i));
update(r[i]);
}
}
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<' ';
}
cout<<'\n';
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
标签:cnt,Sorting,int,memset,Permutation,区间,sizeof,now
From: https://www.cnblogs.com/pure4knowledge/p/18295524