CodeForces 415E

Mashmokh and Reverse Operation

题目大意

传送门

给定$2^n$个数,然后有若干次询问

每次询问给定一个$q$,将原数组的$2^n$个数拆分成$2^{n-q}$个$2^q$的区间,并将每个区间翻转作为新的数组

对于每个询问,输出翻转后整个数组的逆序对个数

思路

首先使用归并,进行初始化,接着我们使用一个$G_{n,2}$数组来记录情况

设$S_{k,i,0}$表示将原数组拆分成$2^{n-k}$个长为$2^k$的区间后

将第$i$个区间再拆分为两个子区间,这两个子区间之间的逆序对个数(P.S. $k=0$不改变数组,故不考虑)

同理,$S_{k,i,1}$则表示相同情况下的顺序对个数

$G_{k,j}=\sum_{i=1}^{2^{n-k}}S_{k,i,j}$其中$j=0,1$

显然我们对整个数组做一遍归并即可得到所有的$G$数组的值

接下来我们考虑一个询问$Q$

易知此时翻转之后的情况会影响$2^p$部分的结构,其中$0\leq p \leq Q$

我们用一个数组$inv$,记录对应的层数是否被翻转

$inv$值为$1$,表示被翻转,此时逆序对变为顺序对,顺序对变为逆序对

$inv$值为$0$,表示未被翻转

那么一开始的$ans$就等于$\sum_{i=1}^nG_{k,0}$

对于每个询问Q,我们需要将第$p$层翻转,其中$0\leq p \leq Q$

对每一层,我们要将顺序对变为逆序对,逆序对变为顺序对,因此对$ans$做$G$数组的加减即可

P.S. 如果有能在一遍while里同时统计顺序对和逆序对的做法,请务必在评论区留言

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
const int maxn=1200005;

map<int,int> mp;
LL g[25][2];//0逆序对,1顺序对,相等特殊判断
int inv[25];
int a[maxn],temp[maxn];
LL i,j,n,m,q,ans;

void solve(LL x,LL y)
{
if(x==y)return;
LL mid=(x+y)>>1;
solve(x,mid);solve(mid+1,y);
LL l=x,r=mid+1;
LL i=x,now=mp[y-x+1];
while(l<=mid && r<=y)
{
if(a[l]>a[r])
{
temp[i++]=a[r++];
g[now][0]+=mid-l+1;
continue;
}
temp[i++]=a[l++];
}
l=x,r=mid+1,i=x;
while(l<=mid && r<=y)
{
if(a[l]<a[r])
{
temp[i++]=a[l++];
g[now][1]+=y-r+1;
continue;
}
temp[i++]=a[r++];
}
while(l<=mid)temp[i++]=a[l++];
while(r<=y)temp[i++]=a[r++];
for(LL i=x;i<=y;i++)a[i]=temp[i];
}

int main()
{
mp[1]=0;for(i=1;i<=20;i++)mp[1<<i]=i;
scanf("%lld",&n);
for(i=1;i<=(1<<n);i++)scanf("%d",&a[i]);
solve(1,1<<n);
memset(inv,0,sizeof(inv));
for(i=0;i<=n;i++)ans+=g[i][0];
scanf("%lld",&m);
for(i=1;i<=m;i++)
{
scanf("%lld",&q);
for(j=q;j>=0;j--)
{
ans=ans-g[j][inv[j]]+g[j][1-inv[j]];
inv[j]=1-inv[j];
}
printf("%lld\n",ans);
}
return 0;
}