CF414C Mashmokh and Reverse Operation

· · 题解

\text{Links}

cnblogs Luogu Codeforces

题意

给定一个长为 2^n (n\le 20) 的序列 a，有 m (m\le 10^6) 次操作，每次操作给出 q (q\le n)，表示将序列从左至右按 2^q 一段分成连续的 2^{n-q} 段，将每一段反转，然后询问此时序列的逆序对数。

题解

考虑把这个 \text{reverse} 操作放到线段树上，相当于先 \text{reverse} 它的左右两个子区间然后把它俩 \text{swap}。

第一步可以直接递归分治进行，考虑第二步对答案的影响。按块内和块间分开考虑，块内相当于原来的贡献是 \sum [a_i>a_j,i\in left,j\in right]，\text{swap} 之后变成了 \sum [a_i>a_j,i\in right,j\in left]。

那么我们在原序列上进行归并排序，过程中记录 cnt_{i,0/1}，分别表示第 i 层所有的左子区间对右子区间的贡献和右子区间对左子区间的贡献之和，即上面那两个式子。

每次操作相当于把 q 及其以下的所有层的 cnt_{0/1} \text{swap}，然后查询 \sum_{x=1}^{n} cnt_{x,0}。

于是就做完了，实际上并不需要用到线段树，只是利用了线段树上的分治思想。

时间复杂度为 O((n+m)\log n)，其中 n 为序列长度，m 为操作数。

\text{Code}

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
char buf[1<<22],*p1=buf,*p2=buf;
const int N=2e6;
int n,a[N],cnt[22][2],b[N],m;
il int read(){
    re int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
il void solve(int l,int r,int dep){
    if(l==r)return;
    re int mid=(l+r)>>1,i=mid+1,j=l,pos=l;
    solve(l,mid,dep-1),solve(mid+1,r,dep-1);
    while(i<=r){
        while(j<=mid&&a[j]<a[i])b[pos++]=a[j++];
        cnt[dep][1]+=j-l;
        while(j<=mid&&a[j]==a[i])b[pos++]=a[j++];
        cnt[dep][0]+=mid-j+1;
        b[pos++]=a[i++];
    }
    while(j<=mid)b[pos++]=a[j++];
    for(re int i=l;i<=r;i++)a[i]=b[i];
}
signed main(){
    n=read();
    for(re int i=1;i<=(1<<n);i++)a[i]=read();
    solve(1,1<<n,n);
    m=read();
    while(m--){
        int q=read();
        while(q)swap(cnt[q][0],cnt[q][1]),q--;
        re int res=0;
        for(re int i=1;i<=n;i++)res+=cnt[i][0];
        cout<<res<<'\n';
    }
    return 0;
}