题解：P15576 [USACO26FEB] Good Cyclic Shifts G

· · 题解

提供一个抛弃大脑的做法。呈现蒟蒻的所有思路。

::::info[转化]

原题操作等价于给排列排序，根据冒泡排序的原理，最小操作次数等价于排列逆序对数。

::::

然后就有 O(n^2\log n) 做法了，暴力树状数组逆序对，计算 f(p) 即可。考虑优化。

::::info[如何快速计算所有循环位移排列的逆序对？]

我们求出没有位移的排列的逆序对，可以用树状数组 O(n\log n) 求解。

考虑在循环位移 i-1 的排列逆序对转移到循环位移 i 的排列逆序对发生的偏差。

主要变化是我们将 p_i 从排列的第一个位置移动到最后一个位置。

消失的贡献：p_i 只能作为逆序对前面的元素（循环前 p_i 是排列第一个位置），后面 p_i+1\sim n 的元素都会和他产生贡献，这一部分是 n-p_{i}。

产生的贡献：即 p_i 只能作为逆序对后面的元素（循环后 p_i 是排列最后一个位置），前面 1\sim p_i-1 的元素都会和他产生贡献，这一部分是 p_{i}-1。

然后直接递推转移，这部分是 O(n) 的。 ::::

但是我们还需要计算另外一个部分才能得到答案。

::::info[如何快速计算所有循环位移排列的 f(p)？]

考虑一些暴力一点的做法。先维护所有 p_i-i 的值。

循环位移 i 次时的操作等价于先全局加一，删除 p_i，插入 p_i-n。

全局加一可以通过偏移量快速维护，删除的 p_i 其实相当于我们维护的 p_i-i，插入的 p_i 等价于 p_i-n-i。

然后是查询全局绝对值，根据当前的偏移量 \Delta，我们把绝对值拆开：

把所有信息放在值域上维护，记录每个值域区间里数的加和和个数和，然后拿线段树维护即可。

时间复杂度为 O(n\log n)。 ::::

其实看整个题，都是一些很套路的东西，只要套路题做多了就能很自然的想到。

最终时间复杂度为 O(n\log n)。

::::info[Code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
int n,p[N],c[N];
vector<int>ans;
void add(int x,int y){
    for(;x<=n;x+=(x&-x))c[x]+=y;
    return; 
}
int ask(int x,int cnt=0){
    for(;x>0;x-=(x&-x))cnt+=c[x];
    return cnt;
}
ll sum[N<<2],val[N<<2],f[N],g[N];
#define ls (p<<1)
#define rs (p<<1|1)
void pushup(int p){
    sum[p]=sum[ls]+sum[rs];
    val[p]=val[ls]+val[rs];
}
void upd(int p,int l,int r,int x,int v){
    if(l==r){
        sum[p]+=v*x,val[p]+=v;
    }else{
        int mid=(l+r)>>1;
        if(x<=mid)upd(ls,l,mid,x,v);
        if(x>mid)upd(rs,mid+1,r,x,v);
        pushup(p);
    }
    return;
}
ll ask(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R)return sum[p];
    int mid=(l+r)>>1;ll cnt=0;
    if(L<=mid)cnt+=ask(ls,l,mid,L,R);
    if(R>mid)cnt+=ask(rs,mid+1,r,L,R);
    return cnt;
}
ll count(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R)return val[p];
    int mid=(l+r)>>1;ll cnt=0;
    if(L<=mid)cnt+=count(ls,l,mid,L,R);
    if(R>mid)cnt+=count(rs,mid+1,r,L,R);
    return cnt;
}
void build(int p,int l,int r){
    sum[p]=val[p]=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    return;
}
#undef ls
#undef rs
void work(){
    scanf("%d",&n);
    build(1,-n,n);
    for(int i=1;i<=n;i++){
        scanf("%d",p+i);
        f[i]=g[i]=0;
    }
    for(int i=1;i<=n;i++){
        f[1]+=i-1-ask(p[i]);
        add(p[i],1);
    }
    for(int i=1;i<=n;i++)c[i]=0;
    for(int i=1;i<n;i++){
        f[i+1]=f[i]+n-2*p[i]+1;
    }
    for(int i=1;i<=n;i++){
        upd(1,-n,n,p[i]-i,1);
        g[1]+=abs(p[i]-i);
    }
    for(int i=1,k;i<n;i++){
        upd(1,-n,n,p[i]-i,-1);k=i;
        upd(1,-n,n,p[i]-n-k,1);
        ll cnt0=count(1,-n,n,-n,-k);
        ll sum0=ask(1,-n,n,-n,-k);
        ll cnt1=count(1,-n,n,-k+1,n);
        ll sum1=ask(1,-n,n,-k+1,n);
        g[i+1]=-sum0-cnt0*k+cnt1*k+sum1;
    }
    ans.clear();
    for(int i=1;i<=n;i++){
        g[i]/=2;
        if(f[i]<=g[i])ans.push_back((n-i+1)%n);
    }
    sort(ans.begin(),ans.end());
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++){
        if(i)printf(" ");
        printf("%d",ans[i]);
    }
    printf("\n");
    return;
}
int main(){
    //freopen("Shifts.in","r",stdin);
    //freopen("Shifts.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)work();
    return 0;
}

::::

如有错误，请指出。