3295: [Cqoi2011]动态逆序对
Description
对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。
Output
输出包含m行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
2
2
1
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
HINT
N<=
CDQ分治
先预处理出 逆序对总数ans 和 每个元素所在的逆序对数fi
每删除元素i,逆序对总数ans -= fi
但是由于一个逆序对有两个元素决定，所以可能会出现重复删的情况
我们二分求元素i是某逆序对中后删的元素的情况数
我们用a,b,c 分别表示元素的删除时间，元素大小，元素位置
元素a是某个逆序对后删的元素
当且仅当有b满足 b.a < a.a 且 b.b < a.b 且 b.c > a.c
或b.a < a.a 且 b.b > a.b 且 b.c < a.c
所以求元素i是某逆序对中后删的元素的情况数
即为求满足 k.a < i.a 且 k.b < i.b 且 k.c > i.c
或k.a < i.a 且 k.b > i.b 且 k.c < i.c 的k的个数
这样这道题就和 BZOJ3262 一样了
#include <cstdio>
#include <algorithm>
using namespace std;
const int MaxN = 100010;
const int MaxM = 50010;
int N, M;
long long Ans;
int delta[MaxN];
int a[MaxN], f[MaxN];
struct point{
int a, b, c, key;
inline point(int x = 0, int y = 0, int z = 0, int k = 0){
a = x, b = y, c = z, k = key;
}
}p[MaxM], q[MaxM];
inline int lowbit(int x){
return x & -x;
}
inline void ins(int x){
for (; x <= N; x += lowbit(x))
++delta[x];
}
inline int query(int x){
int res = 0;
for (; x; x -= lowbit(x))
res += delta[x];
return res;
}
inline void New(int x){
for (; x <= N; x += lowbit(x))
if (delta[x]) delta[x] = 0;
else break;
}
inline void solve1(int l, int r){
if (l == r) return;
int mid = l + r >> 1;
solve1(l, mid), solve1(mid + 1, r);
int t1 = l, t2 = mid + 1;
for (int i = l; i <= r; ++i)
if (t1<= mid && p[t1].b < p[t2].b || t2 > r) {
q[i] = p[t1++];
ins(q[i].c);
}
else {
q[i] = p[t2++];
int res = t1 - l - query(q[i].c);
q[i].key += res;
}
for (int i = l; i <= r; ++i)
p[i] = q[i], New(p[i].c);
}
inline void solve2(int l, int r){
if (l == r) return;
int mid = l + r >> 1;
solve2(l, mid), solve2(mid + 1, r);
int t1 = l, t2 = mid + 1;
for (int i = l; i <= r; ++i)
if (t1<= mid && p[t1].b > p[t2].b || t2 > r) {
q[i] = p[t1++];
ins(q[i].c);
}
else {
q[i] = p[t2++];
int res = query(q[i].c);
q[i].key += res;
}
for (int i = l; i <= r; ++i)
p[i] = q[i], New(p[i].c);
}
inline bool cmp(const point &a, const point &b){
return a.a < b.a;
}
inline int Get(){
char Ch;
while ((Ch = getchar()) < '0' || Ch > '9');
int Num = Ch - '0';
while ((Ch = getchar()) >= '0' && Ch <='9')
Num = Num * 10 + Ch - '0';
return Num;
}
int main(){
N = Get(); M = Get();
for (int i = 1; i <= N; ++i){
int x = Get();
a[x] = i;
}
for (int i = 1; i <= M; ++i){
int x = Get();
p[i] = point(i, x, a[x], 0);
}
for (int i = 1; i <= N; ++i){
ins(a[i]);
int res = i - query(a[i]);
Ans += (f[i] = res);
}
for (int i = 1; i <= N; ++i) delta[i] = 0;
for (int i = N; i; --i){
int res = query(a[i]);
f[i] += res;
ins(a[i]);
}
for (int i = 1; i <= N; ++i) delta[i] = 0;
solve1(1, M);
sort(p + 1, p + M + 1,cmp);
solve2(1, M);
sort(p + 1, p + M + 1,cmp);
for (int i = 1; i <= M; ++i){
printf("%lld\n", Ans);
Ans = Ans - f[p[i].b] + p[i].key;
}
}
Ps：答案要开longlong
评论 (0)
