当前位置: 首页 > >

bzoj 3295: [Cqoi2011]动态逆序对 (主席树+树状数组, or CDQ)

发布时间:

?


Description

对于序列A,它的逆序对数定义为满足iAj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删


除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数


Input

输入第一行包含两个整数n和m,即初始元素的个数和删除的元素个数。


以下n行每行包含一个1到n之间的正整数,即初始排列。


以下m行每行一个正整数,依次为每次删除的元素。


N<=100000 M<=50000


Output

输出包含m行,依次为删除每个元素之前,逆序对的个数。


Sample Input

5 4
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)。


思路:


这个主席树和以前的主席树不一样,因为这个主席树是有区间内的个数。 要 log 个query,


而之前的主席树是求 第 k 大的,只要一次query ,然后数组记录 树状数组的 log 个节点。


?


这个题可以用 树套树,也可以用 CDQ 分治做。?


这里我们用 主席树 + 树状数组做。?


我们要怎么维护逆序对的个数呢。?


我们知道,如果第i 个数被删除了,那么逆序对总数会减少在i 之前没被删除的且比ai??大的数的总数加上


在 i 之后没被删除的且比ai??小的数的总数。


?


我们首先把所有数加入到树状数组中, 并且求出来第 i 个位置,前面有多少个数比 a[i] 大,后边有多少个数 比 a[i] 小。


这个我们可以一遍树状数组求出来。?


然后就是用带修改的主席树维护删除的值。?


其实主席树特别类似 树状数组。都是在 a[i] 的位置上 + 1、?


假设删除 i 这个位置。


那么我们就要找之前删除的值中, 在 i 这个位置之前,而且值比 a[i] 大 的个数。


这个就需要查询主席树中 区间? 【a[i]+1 , n 】, 要得到正确的值,我们还要用树状数组求和区间 [ 0 , i ] 这个区间的值的位置都是在 i 这个位置之前。


在 i 这个位置之后,且比 a[i] 小的个数。这个就需要查询 主席树 区间 【1,a[i]-1】, 要得到正确的值,我们要用树状数组求和区间


【i+1,n】,这个区间所有的值的位置都是在 i 这个位置之后的。?


?


#include
#define low(x) (x & (-x))
using namespace std;
const int N = 1e5+10;
typedef long long LL;
int ls[N*50],rs[N*50],rt[N*50],cnt;
LL c[N],val[N*50],ans1[N],ans2[N],ans;
int n,m,a[N],mp[N];

void add(int x){for (; x <= n; x += low(x)) c[x]++; }
LL sum(int x){LL sum = 0; for (; x; x -= low(x)) sum += c[x]; return sum;}

void update(int &now, int l, int r, int k){
if (!now) now = ++cnt;
val[now]++;
if (l + 1 == r) return;
int mid = (l + r) / 2;
if (k < mid) update(ls[now],l,mid,k);
if (k >= mid) update(rs[now],mid,r,k);
}

LL query(int now, int l, int r, int a, int b){
LL res = 0;
if (a <= l && b >= r - 1) return val[now];
int mid = (l + r) / 2;
if (a < mid) res += query(ls[now],l,mid,a,b);
if (b >= mid) res += query(rs[now],mid,r,a,b);
return res;
}

LL ask(int l, int r, int ll, int rr){
if (ll > rr) return 0;
LL res = 0;
for (int i = l; i; i -= low(i)) res -= query(rt[i],1,n+1,ll,rr);
for (int i = r; i; i -= low(i)) res += query(rt[i],1,1+n,ll,rr);
return res;
}
int main(){
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; ++i){
scanf("%d",&a[i]);
mp[a[i]] = i;
ans1[i] = sum(n) - sum(a[i]);
ans += ans1[i];
ans2[i] = a[i] - sum(a[i]) - 1;
add(a[i]);
}

for (int i = 0; i < m; ++i){
printf("%lld
",ans);
int now,pos;
scanf("%d",&now);
pos = mp[now];
ans -= (ans1[pos] + ans2[pos]) - ask(0,pos,now+1,n) - ask(pos,n,1,now-1);
for (int j = pos; j <= n; j += low(j))
update(rt[j],1,n+1,now);
}
return 0;
}

CDQ 的做法就是,?


一共三个变量。 时间,下标,价值。? 我们要找的值就是。?


t < t0, x < x0, y >y0, or? t < t0, x > x0, y < y0 两种情况。?


我们在 CDQ 中把两种情况都处理一下。?


?


?


#include
#define low(x) (x&(-x))
using namespace std;
const int N = 1e5+10;
struct node { int x,y,t; bool vis;} f[N], g[N];
bool cmp(const node A, const node B){
if (A.t != B.t) return A.t < B.t;
if (A.x != B.x) return A.x < B.x;
return A.y >B.y;
}
bool cmp1(const node A, const node B){
if (A.x == B.x) return A.y < B.y;
return A.x < B.x;
}

bool vis[N];
int a[N],n,m,mp[N];
long long ans[N],c[N];
void add(int x,int w){for(; x <= n; x += low(x)) c[x]+=w;}
long long sum(int x){long long sum = 0; for(; x; x -= low(x)) sum += c[x]; return sum;}

void CDQ(int l, int r){
if (l >= r) return;
int mid = (l + r) >> 1,cnt = 0;

for (int i = l; i <= mid; ++i) g[++cnt] = f[i],g[cnt].vis = 0;
for (int i = mid + 1; i <= r; ++i) g[++cnt] = f[i],g[cnt].vis = 1;
sort(g+1,g+cnt+1,cmp1);

for (int i = 1; i <= cnt; ++i)
if (g[i].vis == 0) add(g[i].y,1);
else ans[g[i].t] += sum(n) - sum(g[i].y);
for (int i = 1; i <= cnt; ++i) if (!g[i].vis) add(g[i].y,-1);

for (int i = cnt; i > 0; --i)
if (!g[i].vis) add(g[i].y,1);
else ans[g[i].t] += sum(g[i].y);
for (int i = 1; i <= cnt; ++i) if (!g[i].vis) add(g[i].y,-1);
CDQ(l,mid); if (mid < r) CDQ(mid+1,r);


}
int main(){
int k;
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; ++i){
scanf("%d",&f[i].y); f[i].x = i; mp[f[i].y] = i;
}
for (int i = 0; i < m; ++i){
scanf("%d",&k);
f[mp[k]].t = n - i;
}
int top = n - m;
for (int i = 1; i <= n; ++i)
if (f[i].t == 0) f[i].t = top--;
sort(f+1,f+n+1,cmp);
CDQ(1,n);

for (int i = 1; i <= n; ++i) ans[i] += ans[i-1];
for (int i = n; i > n-m; --i)
printf("%lld
",ans[i]);
return 0;
}


?



友情链接: