题解 P1774 【最接近神的人_NOI导刊2010提高（02）】

这道题很明显是求逆序对。

所谓逆序对，就是逆序的数对。

譬如在下面这个数列中：

1 2 3 4 6 5

6 5就是一个逆序对。

求逆序对的方法比较多，常见的有归并排序和树状数组（线段树当然也行）。

本题采用平衡树（leafy tree）解决。（之所以写这个才不是因为我懒呢！）

对于数列中的每一项，插入，然后查询它的rank。

累加即为答案。

写的时候因为直接黏贴模板被坑了好几次（尴尬至极），大概告诉我两件事：

这题得开long long
不注释文件输入可能不是RE而是TLE

速度很慢，效率很低，2212ms。

代码如下：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

const long long N=500500;

namespace LeafyTree{

    const long long alpha=4;

    long long n,cnt,father,root;

    long long val[N<<2],size[N<<2],ls[N<<2],rs[N<<2];

    inline void newNode(long long &pos,long long v){

        pos=++cnt,size[pos]=1,val[pos]=v;

    }

    inline void copyNode(long long x,long long y){

        size[x]=size[y],ls[x]=ls[y],rs[x]=rs[y],val[x]=val[y];

    }

    void merge(long long l,long long r){

        size[++cnt]=size[l]+size[r],val[cnt]=val[r],ls[cnt]=l,rs[cnt]=r;

    }

    void rotate(long long pos,bool flag){

        if(flag){

            merge(ls[pos],ls[rs[pos]]);

            ls[pos]=cnt,rs[pos]=rs[rs[pos]];

        }else{

            merge(rs[ls[pos]],rs[pos]);

            rs[pos]=cnt,ls[pos]=ls[ls[pos]];

        }

    }

    void maintain(long long pos){

        if(size[ls[pos]]>size[rs[pos]]*alpha)rotate(pos,0);

        else if(size[rs[pos]]>size[ls[pos]]*alpha)rotate(pos,1);

        if(size[ls[pos]]>size[rs[pos]]*alpha)rotate(ls[pos],1),rotate(pos,0);

        else if(size[rs[pos]]>size[ls[pos]]*alpha)rotate(rs[pos],0),rotate(pos,1);

    }

    void pushup(long long pos){

        if(!size[ls[pos]])return;

        size[pos]=size[ls[pos]]+size[rs[pos]];

        val[pos]=val[rs[pos]];

    }

    void insert(long long pos,long long v){

        if(size[pos]==1){

            newNode(ls[pos],min(v,val[pos]));

            newNode(rs[pos],max(v,val[pos]));

            pushup(pos);

            return;

        }

        if(v>val[ls[pos]])insert(rs[pos],v);

        else insert(ls[pos],v);

        pushup(pos);

        maintain(pos);

    }

    void erase(long long pos,long long v){

        if(size[pos]==1){

            if(ls[father]==pos)copyNode(father,rs[father]);

            else copyNode(father,ls[father]);

            return;

        }

        father=pos;

        if(v>val[ls[pos]])erase(rs[pos],v);

        else erase(ls[pos],v);

        pushup(pos);

        maintain(pos);

    }

    long long kth(long long pos,long long v){

        if(size[pos]==v)return val[pos];

        if(v>size[ls[pos]])return kth(rs[pos],v-size[ls[pos]]);

        return kth(ls[pos],v);

    }

    long long rank(long long pos,long long v){

        if(size[pos]==1)return 1;

        if(v>val[ls[pos]])return rank(rs[pos],v)+size[ls[pos]];

        return rank(ls[pos],v);

    }

}

using namespace LeafyTree;

namespace Solve{

	template<typename T>inline void read(T &x){

		x=0;T f=1;char c=getchar();

		for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

		for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';

		x*=f;

	}

	template<typename T>inline void write(T x){

		if(x>=10)write(x/10);

		putchar(x%10+'0');

	}

	const long long INF=9223372036854775807;

	long long n,ans;

	long long a[N];

	inline void solve(){

		read(n);

    	newNode(root,INF);

		for(register long long i=1;i<=n;++i){

			read(a[i]),insert(root,a[i]);

			ans+=i-rank(root,a[i]+1)+1;

		}

		write(ans);

	}

}

using namespace Solve;

int main(){

//	freopen("testdata.in","r",stdin);

	solve();

}

巴特西

题解 P1774 【最接近神的人_NOI导刊2010提高（02）】

最新文章

热门文章