M_sea

洛谷3157 [CQOI2011]动态逆序对
LuoguBZOJ分析$\mathscr{CDQ}$分治。考虑一个点对 $(i,j)$ 在什么情况下有贡献。显然要...
扫描右侧二维码阅读全文
25
2019/03

洛谷3157 [CQOI2011]动态逆序对

Luogu

BZOJ

分析

$\mathscr{CDQ}$分治。

考虑一个点对 $(i,j)$ 在什么情况下有贡献。显然要满足 $t_i<t_j,a_i>a_j,pos_i<pos_j$ 。

那么这就是一个经典的三维偏序问题,可以用 $\mathrm{CDQ}$ 分治解决。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,tot=0;
int a[N],p[N]; ll ans[N];
struct query { int x,v,w,id; } q[N<<1];
inline int cmp(query a,query b) { return a.x<b.x; }

int c[N];
inline int lowbit(int x) { return x&-x; }
inline void add(int x,int v) {
    for (;x<=n;x+=lowbit(x)) c[x]+=v;
}
inline int sum(int x) {
    int ans=0;
    for (;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

inline void CDQ(int l,int r) {
    if (l==r) return;
    int mid=(l+r)>>1;
    CDQ(l,mid),CDQ(mid+1,r);
    sort(q+l,q+mid+1,cmp),sort(q+mid+1,q+r+1,cmp);
    int i=l;
    for (re int j=mid+1;j<=r;++j) {
        while (i<=mid&&q[i].x<=q[j].x) add(q[i].v,q[i].w),++i;
        ans[q[j].id]+=q[j].w*(sum(n)-sum(q[j].v));
    }
    for (re int j=l;j<i;++j) add(q[j].v,-q[j].w);
    i=mid;
    for (re int j=r;j>mid;--j) {
        while (i>=l&&q[i].x>=q[j].x) add(q[i].v,q[i].w),--i;
        ans[q[j].id]+=q[j].w*sum(q[j].v-1);
    }
    for (re int j=mid;j>i;--j) add(q[j].v,-q[j].w);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) {
        a[i]=read(),p[a[i]]=i;
        q[++tot]=(query){i,a[i],1,0};
    }
    for (re int i=1;i<=m;++i) {
        int x=read();
        q[++tot]=(query){p[x],x,-1,i};
    }
    CDQ(1,tot);
    for (re int i=1;i<=m;++i) ans[i]+=ans[i-1];
    for (re int i=0;i<m;++i) printf("%lld\n",ans[i]);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 22 PM

5 条评论

  1. ZCDHJ

    orz!

    1. M_sea
      @ZCDHJ

      Orz

  2. smy

    那个$\mathcal{CDQ}$也太花了把qwq

    1. Karry5307
      @smy

      赞同!顺便orz smy神仙

      1. smy
        @Karry5307

        ?????????????????????

发表评论