题目描述
LYK最近在研究逆序对。 这个问题是这样的。 一开始LYK有一个2^n长度的数组ai。 LYK有Q次操作，每次操作都有一个参数k。表示每连续2^k长度作为一个小组。假设 n=4,k=2，则a[1],a[2],a[3],a[4]为一个小组，a[5],a[6],a[7],a[8]为一个小组， a[9],a[10],a[11],a[12]为一个小组，a[13],a[14],a[15],a[16]也为一个小组。 然后LYK对于每个小组都翻转，也就是说原数组会变成 a[4],a[3],a[2],a[1],a[8],a[7],a[6],a[5],a[12],a[11],a[10],a[9],a[16],a[15],a[14],a[13 ]。之后它想求出这2^n个数的逆序对是多少。 因此你需要输出对于每次操作，操作完后这2^n个数的逆序对有多少对。两个数ai,aj被称为逆序对当且仅当iaj。
数据范围
n<=17，Q<=200000，1<=ai<=2^n。
题解：
①尝试将操作转化为可以记录翻转状态的形式
②找规律：
对f[1]+f[2]+f[3]+f[4]+f[5]+f[6]+f[7]+f[8]进行2^3操作
f[1]+f[2]+f[3]+f[4]+f[5]+f[6]+f[7]+f[8]
=f[2]+f[1]+f[4]+f[3]+f[6]+f[5]+f[8]+f[7]
=f[4]+f[3]+f[2]+f[1]+f[8]+f[7]+f[6]+f[5]
=f[8]+f[7]+f[6]+f[5]+f[4]+f[3]+f[2]+f[1]
③然后每次2操作转化为按照上述方式(认真观察上述方式)交换长度为2,2…2子区间
④使用down[i]表示按照上述规律的翻转的长度为2单位区间每一对之间的逆序对数之和。
⑤使用up[i]表示按照上述规律的翻转的长度为2单位区间每一对之间的顺序对数之和。
⑥使用f[i]表示当前区间是否被反转。
⑦每次询问处理：O(logn),小于k的区间就根据f[i]加,大于k的直接加
⑧初始化使用归并排序求出原先的总逆序对数同时初始化down,up,f
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
const int N=(1<<17)+5;
long long st[N][20],ST[N][20];
int p[N],i,sum,o,a[N],b[N],n,T,PP,now,j,A,RR[N];
void gb(int l,int r)
{
if (l==r) return;
int mid=(l+r)/2;
gb(l,mid); gb(mid+1,r);
int i=l,j=mid+1,o=l;
for (i=l; i<=r; i++) b[i]=a[i];
for (i=r; i>=mid; i--) {RR[i]=i; if (i!=r && b[i+1]==b[i]) RR[i]=RR[i+1];}
i=l; j=mid+1;
while (i<=mid && j<=r)
{
if (b[i]<=b[j]) {a[o++]=b[i];if (b[i]==b[j]) ST[l][p[r-l+1]]+=RR[j]-j+1; i++;} else
{
a[o++]=b[j]; st[l][p[r-l+1]]+=mid-i+1; j++;
}
}
if (i<=mid) for (j=i; j<=mid; j++) a[o++]=b[j]; else
if (j<=r) for (i=j; i<=r; i++) a[o++]=b[i];
}
long long t[105],TT[105];
int main()
{
freopen("pair.in","r",stdin);
freopen("pair.out","w",stdout);
scanf("%d",&n);
sum=(1<<n);
for (i=1; i<=sum; i++) scanf("%d",&a[i]);
for (i=1; i<=17; i++) p[1<<i]=i;
gb(1,sum);
scanf("%d",&T);
for (i=1; i<=n; i++)
for (j=1; j<=(1<<n); j+=(1<<i))
{
t[i]+=st[j][i];
TT[i]+=ST[j][i];
}
long long ans=0;
while (T--)
{
int Q;
scanf("%d",&Q);
for (i=1; i<=Q; i++) t[i]=1ll*(1<<i-1)*(1<<i-1)*(1<<n-i)-TT[i]-t[i];
for (i=1; i<=n; i++) ans+=t[i];
printf("%I64d\n",ans); ans=0;
}
return 0;
}//czy020202
No need to doubt all my lost to faded glory,
My soul is small but longs to roam.——————汪峰《Song Of Redemption》