题目描述
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被称为逆序对当且仅当i<j且ai>aj。
输入格式(pair.in)
第一行一个数n。
接下来一行2^n个数ai表示一开始的数组。
接下来一行一个数Q，表示操作的次数。
接下来一行Q个数，表示每次操作的参数k。
输出格式(pair.out)
Q行，表示每次操作后的答案。
输入样例
2
2 1 4 3
4
1 2 0 2
输出样例
0
6
6
0
样例解释
第一次操作，{2,1,4,3}->{1,2,3,4}
第二次操作，{1,2,3,4}->{4,3,2,1}
第三次操作，{4,3,2,1}->{4,3,2,1}
第四次操作，{4,3,2,1}->{1,2,3,4}
对于30%的数据n<=10，Q<=10。
对于50%的数据n<=10，Q<=1000。
对于80%的数据n<=10，Q<=200000。
对于100%的数据n<=17，Q<=200000，1<=ai<=2^n。
分析：比较巧妙的一道题。每次翻转操作其实就是将一个区间的逆序对个数与顺序对个数交换,那么先用归并排序求出逆序对的同时求出顺序对。接下来可以把翻转操作进行分解:假设交换翻转1234
1,2,3,4 ---> 1,2 3,4 ---> 3,4 1,2 --->4,3,2,1.对每一个子区间的逆序对进行分析，可以知道每个元素的贡献是这个元素在区间长度为1的逆序对数+区间长度为2的逆序对数+区间长度为4的逆序数......
每次修改操作只是更改了长度小于等于2^k的区间的逆序对数，对于长度大于2^k的区间就不用修改了.统计的时候把各个长度的区间答案加起来就是了.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; long long n, a[( << ) + ],q,cnt[( << ) + ][],b[( << ) + ],k;
long long ans; void Sort(int l, int r, int dep)
{
if (l >= r)
return;
int mid = (l + r) >> ;
Sort(l, mid, dep - );
Sort(mid + , r, dep - );
int i = l, j = mid + , res = ;
while (i <= mid && j <= r)
{
if (a[i] < a[j])
{
cnt[dep][] += r - j + ;
i++;
}
else
j++;
}
i = l, j = mid + ;
while (i <= mid && j <= r)
{
if (a[i] > a[j])
{
cnt[dep][] += mid - i + ;
b[++res] = a[j++];
}
else
b[++res] = a[i++];
}
while (i <= mid)
b[++res] = a[i++];
while (j <= r)
b[++res] = a[j++];
for (int i = l; i <= r; i++)
a[i] = b[i - l + ];
} int main()
{
scanf("%lld", &n);
for (int i = ; i <= ( << n); i++)
scanf("%lld", &a[i]);
Sort(, << n, n);
scanf("%lld", &q);
while (q--)
{
scanf("%lld", &k);
ans = ;
for (int i = ; i <= n; i++)
{
if (i <= k)
swap(cnt[i][], cnt[i][]);
ans += cnt[i][];
}
printf("%lld\n", ans);
} return ;
}