题面
题解
是【CQOI2011】动态逆序对的双倍经验。
区别：
- 这题目没有保证数据$<=n$（所以我们要离散化）
- 给出的是删除的数的位置，而不是数值。
- 先输出总的逆序对个数，然后输出每个删除后逆序对的个数。
这道题的数据弱多了代码
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#include<bits/stdc++.h>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data=0, w=1;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1, ch=getchar();
while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
return data*w;
}
typedef long long ll;
const int maxn(100010);
struct node { int a, b, c; ll ans; } a[maxn];
ll ans[maxn], c[maxn];
int n, m, num[maxn], t, pos, key[maxn];
#define get(a, p) (*(a+(p)))
inline int lowbit(int k) { return k&(-k); }
inline void update(int x, int v) { while(x<=n) get(c, x)+=v, x+=lowbit(x); }
inline ll query(int x) { ll ans=0; while(x) ans+=get(c, x), x-=lowbit(x); return ans; }
inline bool cmpx(const node &a, const node &b) { return (a.a<b.a)||(a.a==b.a&&a.b<b.b)||(a.a==b.a&&a.b==b.b&&a.c<b.c); }
inline bool cmpy(const node &a, const node &b) { return (a.b<b.b)||(a.b==b.b&&a.c<b.c); }
void CDQ(int l, int r)
{
if(l==r) return;
int mid(l+r>>1), j(l);
CDQ(l, mid); CDQ(mid+1, r);
for(RG int i=mid+1;i<=r;i++)
{
while((a+j)->b<=(a+i)->b && j<=mid) update((a+j)->c, 1), j++;
(a+i)->ans+=query((a+i)->c);
}
for(RG int i=l;i<j;i++) update((a+i)->c, -1);
inplace_merge(a+l, a+mid+1, a+r+1, cmpy);
}
int main()
{
n=read(); pos=m=read();
for(RG int i=1;i<=n;i++) (a+i)->b=n-i+1, (a+i)->c=get(key, i)=read();
sort(key+1, key+n+1); t=unique(key+1, key+n+1)-key-1;
for(RG int i=1;i<=n;i++) (a+i)->c=lower_bound(key+1, key+t+1, (a+i)->c)-key;
for(RG int i=1;i<=m;i++) t=read(), get(num, t)=i;
for(RG int i=1;i<=n;i++) if(!get(num, i)) get(num, i)=++pos;
for(RG int i=1;i<=n;i++) (a+i)->a=pos-get(num, i)+1;
sort(a+1, a+n+1, cmpx); CDQ(1, n);
for(RG int i=1;i<=n;i++) get(ans, (a+i)->a)+=(a+i)->ans, (a+i)->b=n-(a+i)->b+1, (a+i)->c=n-(a+i)->c+1, (a+i)->ans=0;
sort(a+1, a+n+1, cmpx); CDQ(1, n);
for(RG int i=1;i<=n;i++) get(ans, (a+i)->a)+=(a+i)->ans;
for(RG int i=1;i<=n;i++) get(ans, i)+=get(ans, i-1);
for(RG int i=n;i>=n-m;i--) printf("%lld ", get(ans, i));
return 0;
}