BZOJ3295 [Cqoi2011]动态逆序对

2014.12.31 10:52 Wed| 7 visits oi_2015| 2015_刷题日常| Text

Solution

刚想起好像好久没有写大型数据结构了,然后就刷了一大堆树套树。

封装好的模板真是好用……啦啦啦~

可惜Splay会TLE,用了大神的Fio后就差一点点就可以卡时限AC T^T

于是发愤又敲了一棵Treap模板 23333

嘲讽没进排行榜的16bitwar同学,树套树写得比我的模板还慢……

Code

注:Treap的模板请参见本人其他博客。

#include <bits/stdc++.h>
using namespace std;

namespace Treap
{
}

#define N 100005
#define lson (pos<<1)
#define rson (pos<<1|1)
typedef Treap::treap<int> treap;
long long ans;
int n,m,a[N],p[N],f[N];
treap s[N<<2];

inline int read()
{
    int x=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); }
    return x*f;
}

void build(int pos,int l,int r)
{
    if(l==r)
    {
        s[pos].insert(a[l]);
        return ;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid); build(rson,mid+1,r);
    s[pos].insert(s[lson]); s[pos].insert(s[rson]);
}

int query1(int pos,int l,int r,int x,int y,int z)
{
    if(x<=l&&r<=y)
        return s[pos].find(z)-1;
    int mid=(l+r)>>1, re=0;
    if(x<=mid) re+=query1(lson,l,mid,x,y,z);
    if(y>mid) re+=query1(rson,mid+1,r,x,y,z);
    return re;
}

int query2(int pos,int l,int r,int x,int y,int z)
{
    if(x<=l&&r<=y)
        return s[pos].size()-s[pos].find(z)+1;
    int mid=(l+r)>>1, re=0;
    if(x<=mid) re+=query2(lson,l,mid,x,y,z);
    if(y>mid) re+=query2(rson,mid+1,r,x,y,z);
    return re;
}

void remove(int pos,int l,int r,int x,int y)
{
    s[pos].erase(y);
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) remove(lson,l,mid,x,y);
    else remove(rson,mid+1,r,x,y);
}

void modify(int x)
{
    for(int i=x;i<=n;i+=i&-i)
        f[i]++;
}

int query(int x)
{
    int re=0;
    for(int i=x;i;i-=i&-i)
        re+=f[i];
    return re;
}

long long getinv()
{
    long long re=0;
    for(int i=n;i;i--)
        re+=query(a[i]-1),
        modify(a[i]);
    return re;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        a[i] = read(), p[a[i]]=i;
    build(1,1,n);
    ans = getinv();
    for(int x,i=1;i<=m;i++)
    {
        x = read(); printf("%d\n",ans);
        if(p[x]>1) ans-=query2(1,1,n,1,p[x]-1,x);
        if(p[x]<n) ans-=query1(1,1,n,p[x]+1,n,x);
        remove(1,1,n,p[x],x);
    }
}