BZOJ3295: [Cqoi2011]動态逆序對（洛谷P3157）

CDQ分治

BZOJ題目傳送門

洛谷題目傳送門

我們可以把删除給反過來，變成從最終序列不斷加入元素成為原始序列。

于是這道題就變成了元素下标分别為（時間、位置、值）的一個三維偏序問題（ tj<ti,xj<xi,yj>yi t j < t i , x j < x i , y j > y i ）。沒有查詢的元素 t t 随便給。

然後就變成CDQ分治裸題了。

先按照tt排序，在區間内按照 x x 排，用樹狀數組維護yy。統計時正着掃一遍計算大于 y y 的逆序對數，倒着掃一遍計算小于yy的逆序對數。然後遞歸就行了。

注意要開 long long l o n g   l o n g

代碼：

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define F inline
using namespace std;
typedef long long LL;
struct px{ int x,y,t,z; }q[N],tem[N];
int n,m,i,t[N],ans[N],mp[N];
F char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    if (l==r) return EOF; return *l++;
}
F int _read(){
    int x=; char ch=readc();
    while (!isdigit(ch)) ch=readc();
    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
    return x;
}
F void writec(LL x){ if (x>) writec(x/); putchar(x%10+); }
F void _write(LL x){ writec(x),putchar('\n'); }
#define lbt(x) (x&-x)
F void nsrt(int x,int p){ while (x<=n) t[x]+=p,x+=lbt(x); }
F int srch(int x){ for (i=;x;i+=t[x],x-=lbt(x)); return i; }
F bool cmp1(px a,px b){ return a.x==b.x?a.y<b.y:a.x<b.x; }
F bool cmp2(px a,px b){ return a.t<b.t; }
F void cdq(int l,int r){
    if (l==r) return; int mid=l+r>>;
    for (int i=l;i<=mid;i++) tem[i]=q[i],tem[i].z=;
    for (int i=mid+;i<=r;i++) tem[i]=q[i],tem[i].z=;
    sort(tem+l,tem+r+,cmp1);
    for (int i=l;i<=r;i++)
        if (!tem[i].z) nsrt(tem[i].y,); 
        else ans[tem[i].t]+=srch(n)-srch(tem[i].y);
    for (int i=l;i<=r;i++) if (!tem[i].z) nsrt(tem[i].y,-);
    for (int i=r;i>=l;i--)
        if (!tem[i].z) nsrt(tem[i].y,);
        else ans[tem[i].t]+=srch(tem[i].y);
    for (int i=l;i<=r;i++) if (!tem[i].z) nsrt(tem[i].y,-);
    cdq(l,mid),cdq(mid+1,r);
}
int main(){
    n=_read(),m=_read(); int ti=n; LL sum=;
    for (int i=;i<=n;i++) q[i].x=i,mp[q[i].y=_read()]=i;
    for (int i=;i<=m;i++) q[mp[_read()]].t=ti--;
    for (int i=;i<=n;i++) if (!q[i].t) q[i].t=ti--;
    sort(q+,q+n+,cmp2),cdq(1,n);
    for (int i=;i<=n;i++) sum+=ans[i];
    for (int i=n;i>n-m;i--) _write(sum),sum-=ans[i];
    return ;
}