AC日记——Mato的文件管理 bzoj 3289

3289

思路：

　　莫队求区间逆序对个数，树状数组维护；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 50005

int bel[maxn],blo;

struct QueryType {

    int l,r,id;

    bool operator<(const QueryType pos)const

    {

        if(bel[l]==bel[pos.l]) return r<pos.r;

        return bel[l]<bel[pos.l];

    }

};

struct QueryType qu[maxn];

int n,m,ai[maxn],bi[maxn],tree[maxn],size,now,ans[maxn];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline int lowbit(int x)

{

    return x&(-x);

}

inline void add(int x,int di)

{

    while(x<=n)

    {

        tree[x]+=di;

        x+=lowbit(x);

    }

}

inline int sum(int l,int r)

{

    int res=;l--;

    while(r) res+=tree[r],r-=lowbit(r);

    while(l) res-=tree[l],l-=lowbit(l);

    return res;

}

inline void updatar(int x,bool di)

{

    x=ai[x];

    if(di)

    {

        if(x<size) now+=sum(x+,size);

        add(x,);

    }

    else

    {

        if(x<size) now-=sum(x+,size);

        add(x,-);

    }

}

inline void updatal(int x,bool di)

{

    x=ai[x];

    if(di)

    {

        if(x>) now+=sum(,x-);

        add(x,);

    }

    else

    {

        if(x>) now-=sum(,x-);

        add(x,-);

    }

}

int main()

{

    in(n),blo=sqrt(n);

    for(int i=;i<=n;i++) in(ai[i]),bi[i]=ai[i],bel[i]=(i+)/blo;

    sort(bi+,bi+n+),size=unique(bi+,bi+n+)-bi-;

    for(int i=;i<=n;i++) ai[i]=lower_bound(bi+,bi+size+,ai[i])-bi;

    in(m);

    for(int i=;i<=m;i++) in(qu[i].l),in(qu[i].r),qu[i].id=i;

    sort(qu+,qu+m+);int l=,r=;

    for(int i=;i<=m;i++)

    {

        while(r<qu[i].r) updatar(++r,true);

        while(r>qu[i].r) updatar(r--,false);

        while(l>qu[i].l) updatal(--l,true);

        while(l<qu[i].l) updatal(l++,false);

        ans[qu[i].id]=now;

    }

    for(int i=;i<=m;i++) printf("%d\n",ans[i]);

    return ;

}