精华内容
下载资源
问答
  • 树状数组求逆序对

    2017-03-24 17:45:16
    树状数组求逆序对

    http://blog.csdn.net/q573290534/article/details/6664902

    5,2,1,4,3

    1 1 0 1 1 bool
    1 2 3 4 5
    对于4而言,前面有2个比它小的数(bool数组用树状数组去计算),因此对于4而言的逆序对为:4(4所在的原数组下标)-2(前面比它小的数的个数)=2.

    在离散结果的基础上,那么其计算逆序数的过程是这么一个过程。
    1,输入5, 调用upDate(5, 1),把第5位设置为1
    1 2 3 4 5
    0 0 0 0 1
    计算1-5上比5小的数字存在么? 这里用到了树状数组的getSum(5) = 1操作,
    现在用输入的下标1 - getSum(5) = 0 就可以得到对于5的逆序数为0。
    2. 输入2, 调用upDate(2, 1),把第2位设置为1
    1 2 3 4 5
    0 1 0 0 1
    计算1-2上比2小的数字存在么? 这里用到了树状数组的getSum(2) = 1操作,
    现在用输入的下标2 - getSum(2) = 1 就可以得到对于2的逆序数为1。
    3. 输入1, 调用upDate(1, 1),把第1位设置为1
    1 2 3 4 5
    1 1 0 0 1
    计算1-1上比1小的数字存在么? 这里用到了树状数组的getSum(1) = 1操作,
    现在用输入的下标 3 - getSum(1) = 2 就可以得到对于1的逆序数为2。
    4. 输入4, 调用upDate(4, 1),把第5位设置为1
    1 2 3 4 5
    1 1 0 1 1
    计算1-4上比4小的数字存在么? 这里用到了树状数组的getSum(4) = 3操作,
    现在用输入的下标4 - getSum(4) = 1 就可以得到对于4的逆序数为1。
    5. 输入3, 调用upDate(3, 1),把第3位设置为1
    1 2 3 4 5
    1 1 1 1 1
    计算1-3上比3小的数字存在么? 这里用到了树状数组的getSum(3) = 3操作,
    现在用输入的下标5 - getSum(3) = 2 就可以得到对于3的逆序数为2。
    6. 0+1+2+1+2 = 6 这就是最后的逆序数
    分析一下时间复杂度,首先用到快速排序,时间复杂度为O(NlogN),
    后面是循环插入每一个数字,每次插入一个数字,分别调用一次upData()和getSum()
    外循环N, upData()和getSum()时间O(logN) => 时间复杂度还是O(NlogN).
    最后总的还是O(NlogN).

    in:
    5
    33 35 32 31 34
    out:
    6


    //5
    //95 92 91 94 93
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int cnt,n,c[1001],ref[1001];
    struct node{
        int v,p;
    }a[1001];
    bool cmp(node x,node y)
    {
        return x.v<y.v;
    }
    int lowbit(int x)
    {
        return x&(-x);
    }
    void update(int x)
    {
        while(x<=n)
        {
            c[x]+=1;
            x+=lowbit(x);
        }
    }
    int getsum(int x)
    {
        int sum=0;
        while(x>0)
        {
            sum+=c[x];
            x-=lowbit(x);
        }
        return sum;
    }
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].v);
            a[i].p=i;//位置 
        }
        sort(a+1,a+n+1,cmp);//a[2].v
        //原来是
        for(int i=1;i<=n;i++)//先不要着急 update()
        {
            ref[a[i].p]=i;//91这个数原来在3(a[1].p)这个位置,排序以后变成了1 
        }
        for(int i=1;i<=n;i++)
        {
            //先找顺序
            update(ref[i]);//原来在1(95这个数)位置的数排序后移到了5 (95)
            cnt+=i-getsum(ref[i]);  
        } 
        cout<<cnt<<endl;
    }
    展开全文
  • 树状数组求逆序对

    传送门


    题目大意:
    给出t个case,每个case给出k条边,这些边的左右两个端点分别属于n和m两个集合,求出有多少条相交的边(如果两条边有公共端点不算相交)


    分析:
    显然如果两条边相交一定满足(xi-xj)*(yi-yj)<0,所以我们可以把k条边按照x单调递增的顺序排排序,然后求y的逆序对即可(注意:如果两条边x相同,y按照递增的顺序排,因为这样处理时不会把这两条边算为相交的边Notice!!!)


    代码如下:

    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #define LL long long
    using namespace std;
    const int maxn=1000+5;
    int cas,n,m,k,t;
    LL tr[maxn],ans,ONE=1;
    struct road{
        int x,y;
    }s[maxn*maxn];
    bool cmp(road a,road b){
        if(a.x==b.x)
            return a.y<b.y;
        return a.x<b.x;
    }
    void add(int x,LL y){
        for(;x<=m;x+=(x&(-x)))
            tr[x]+=y;
    }
    LL query(int x){
        LL sum=0;
        for(;x;x-=(x&(-x)))
            sum+=tr[x];
        return sum;
    }
    signed main(void){
        scanf("%d",&cas),t=0;
        while(cas--){
            scanf("%d%d%d",&n,&m,&k);
            for(int i=1;i<=k;i++)
                scanf("%d%d",&s[i].x,&s[i].y);
            sort(s+1,s+k+1,cmp);
            ans=0,memset(tr,0,sizeof(tr));
            for(int i=1;i<=k;i++)
                add(s[i].y,ONE),ans+=query(m)-query(s[i].y);
            t++;
            printf("Test case %d: %lld\n",t,ans);
        }
        return 0;
    }

    by >o< neighthorn

    展开全文
  • 树状数组求逆序对及离散化 逆序对指的是一个序列中有两个数ai和aj,iaj,即它们下标与数值的增减不一致,那么对于这个问题:一个序列中逆序对的个数,该如何解决呢? 我最初接触到的方法是归并排序,是个很不错...
    树状数组求逆序对及离散化
    逆序对指的是一个序列中有两个数ai和aj,i<j&&ai>aj,即它们下标与数值的增减不一致,那么对于这个问题:求一个序列中逆序对的个数,该如何解决呢?
    我最初接触到的方法是归并排序,是个很不错的方法,但是对于向我一样的蒟蒻……还是有理解难度,而今天讲的树状数组解法,至少……理解难度降低了不少。
    树状数组求逆序的思想事实上和树状数组关系不大,以下图为例(自己画的,丑:):
    如上图,第一次将第一个数1对应的a[1]++,这时还看不出来,再将4对应的a[4]++,同理a[2]++……即将n对应的a[n]++,这样做,就可以将一个无序的序列变得有序,同时a数组也表示了对应下标的数是否出现/处理过,而且当只有i个元素变换之时,剩余元素不会对接下来的操作造成影响,现在给出计算到2时的图片:
    那么,对于最新处理的2或任意一个n(设下标为i)来说,前i个数中,比它小及其本身的数的个数,就是前i项的前缀和,因为排在原序列中i之后的数尚未处理,而已处理的a中比他小的数必然在它前面,且对应a[]值为1,那么,已处理的i个数中,比这个数n大的数的个数,也就是这一个数的逆序对数,就是i-getsum(n),而前缀和的求值与a数组的修改、维护,就可以交给树状数组了:
    int lowbit(int a)
    {
        return a&(-a);
    }
    void add(int p,int c)
    {
        while(p<=n)
        { C[p]+=c;p+=lowbit(p);}
    }
    int getsum(int p)
    {
        LL ans=0;
        while(p)
        { ans+=C[p];p-=lowbit(p)   }
    
          return ans;
    }
    函数并没有变化,只是主函数中的调用变成了这样:
    add(a[i], 1);
    ans += i - getsum(a[i]);
    枚举一下i就可以了
    但是,这个问题还有大坑!!我们的插入,是基于修改n对应的a[n]的,但是,如果n达到了2^31级?你开的下这么大的数组吗?
    这个时候,就是离散化出场的时候了,离散化作为一种常见的优化方式,其实原理很简单,用一个结构体将数的值和下标联系在一起,再按数值排一次序,将i赋给loc[a[i].pos]//pos为下标//,这样,就将数据范围压缩在了序列长度以内,极大的压缩了空间:
    struct Node
    {
    	int val,pos;
    }a[100000]
    bool cmp(Node a,Node b)
    {
        if(a.val==b.val)return a.pos<=b.pos;
        else return a.val<b.val;
    }
    
    for(int i=1;i<=n;i++){
            scanf("%d",&a[i].val);
            a[i].pos=i;
        } 
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++)
            tre[a[i].pos]=i;
    比如100 1 5 20 2 离散化为5 1 3 4 2,极大的节省了空间。
    树状数组求逆序对,说到底,就是对求和函数的特殊运用,光会求逆序对,作用不大,关键是要明白怎样根据题目要求,去处理序列,求和到底可以干什么?这些都需要经验积累,推荐几道题:洛谷P1908 P1521 poj2299
    poj 3067 火柴排队 奶牛集会,谢谢。

    展开全文
  • 离散化树状数组求逆序对 今天在学校ojojoj上看见一道求逆序对的题,上一次企图用冒泡排序做,结果wa了几发。学习树状数组时,猛然发现树状数组还可以求逆序对,于是打开了新的大门。 传送门:39.106.31.26/problem....

    离散化树状数组求逆序对

    今天在学校 o j oj oj上看见一道求逆序对的题,上一次企图用冒泡排序做,结果wa了几发。学习树状数组时,猛然发现树状数组还可以求逆序对,于是打开了新的大门。
    传送门:39.106.31.26/problem.php?id=3677(洛谷也有这道题P1908)

    猫猫TOM和小老鼠JERRY最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。最近,TOM老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中 a i &lt; a j a_i&lt;a_j ai<aj i &lt; j i&lt;j i<j的有序对。知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。
    I n p u t Input Input
    第 一 行 , 一 个 数 n , 表 示 序 列 中 有 n 个 数 。 ( n ≤ 40000 ) 第一行,一个数n,表示序列中有n个数。(n≤40000) nnn40000)
    第 二 行 n 个 数 , 表 示 给 定 的 序 列 。 第二行n个数,表示给定的序列。 n
    O u t p u t Output Output
    给 定 序 列 中 逆 序 对 的 数 目 。 给定序列中逆序对的数目。
    S a m p l e Sample Sample I n p u t Input Input
    6
    5 4 2 6 3 1
    S a m p l e Sample Sample O u t p u t Output Output
    11

    解题思路

    我们针对样例来理解如何采用树状数组求逆序对。

    1:

    最初的条件如下:
    在这里插入图片描述

    2:

    我们利用update(5),将第5个位置置为1。计算 [ 1 , 5 ] [1,5] [1,5]上比5小的数字,这里用到了树状数组的 g e t s u m ( x ) getsum(x) getsum(x)操作,现在用输入的下标 i − g e t s u m ( x ) i-getsum(x) igetsum(x) 就可以得到对于逆序数。即: g e t s u m ( 5 ) = 1 , r e s = i − g e t s u m ( 5 ) = 1 − 1 = 0 。 getsum(5)=1,res=i-getsum(5)=1-1=0。 getsum(5)=1,res=igetsum(5)=11=0
    在这里插入图片描述

    update函数:
    void update(ll x){
    	while(x<=n){
    		ans[x]++;
    		x+=lowbit(x);
    	}
    }
    
    getsum函数:
    ll getsum(ll x){
    	ll res=0;
    	while(x){
    		res+=ans[x];
    		x-=lowbit(x);
    	}
    	return res;
    }
    

    3:

    跟上面情况相同,先把第4个位置置为1, g e t s u m ( 4 ) = 1 , r e s = i − g e s u m ( 4 ) = 2 − 1 = 1 getsum(4)=1,res=i-gesum(4)=2-1=1 getsum(4)=1,res=igesum(4)=21=1
    在这里插入图片描述

    4:

    把第2个位置置为1, g e t s u m ( 2 ) = 1 , r e s = i − g e s u m ( 2 ) = 3 − 1 = 2 。 getsum(2)=1,res=i-gesum(2)=3-1=2。 getsum(2)=1,res=igesum(2)=31=2
    在这里插入图片描述

    5:

    把第6个位置置为1, g e t s u m ( 6 ) = 4 , r e s = i − g e s u m ( 6 ) = 4 − 4 = 0 。 getsum(6)=4,res=i-gesum(6)=4-4=0。 getsum(6)=4,res=igesum(6)=44=0
    在这里插入图片描述

    6:

    把第3个位置置为1, g e t s u m ( 3 ) = 2 , r e s = i − g e s u m ( 3 ) = 5 − 2 = 3 。 getsum(3)=2,res=i-gesum(3)=5-2=3。 getsum(3)=2,res=igesum(3)=52=3
    在这里插入图片描述
    6:把第1个位置置为1, g e t s u m ( 1 ) = 1 , r e s = i − g e s u m ( 1 ) = 6 − 1 = 5 。 getsum(1)=1,res=i-gesum(1)=6-1=5。 getsum(1)=1,res=igesum(1)=61=5
    在这里插入图片描述

    7:

    把每一步的res加起来就是最后的答案了, s u m = 0 + 1 + 2 + 0 + 3 + 5 = 11 。 sum=0+1+2+0+3+5=11。 sum=0+1+2+0+3+5=11


    这道题看似仿佛已经讲完了,但是仔细思考思考里面居然有一个大坑。这个坑是我们树状数组造成的。当我们输入的值 a i = 999999999 a_i=999999999 ai=999999999这样庞大的值是,数组 a n s [ x ] ans[x] ans[x]是肯定存不下的。取一个极端情况,有两个值: a 1 = 1 , a 2 = 1 0 10 a_1=1,a_2=10^{10} a1=1,a2=1010,按照上面的要求我们需要使 a n s [ 1 0 10 ] = 1 ans[10^{10}]=1 ans[1010]=1,那么这个数组大部分内存都浪费了,并且也不支持你开这么大,在这样的情况下,我们将数组离散化。

    推荐一篇写离散化的blog:
    https://blog.csdn.net/qq_41754350/article/details/81199993

    简单的说就是我们用数值下标替代了它的值进行操作。
    在这里插入图片描述
    将上述的 A [ i ] A[i] A[i]进行排序,用位置 b [ i ] b[i] b[i]代替自己的原来的值,起到离散化作用。
    在这里插入图片描述


    没想到吧,这里居然还有个坑,离散化的数据一定要去重,不然在求逆序数时会得到错误的解。为了能够偷懒,给大家推荐一个排序:stable_sort()用法和sort()差不多,好处是能去重嘛,要是不懂大家可以百度一下。

    最后上代码:

    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll maxn=5*1e5+10;
    ll b[maxn],n,ans[maxn];
    struct code{
    	ll val,wz;
    }a[maxn];
    bool cmp(code a,code b)
    {
    	return a.val<b.val;
    }
    ll lowbit(ll x){
    	return x&(-x); 
    }
    void update(ll x){
    	while(x<=n){
    		ans[x]++;
    		x+=lowbit(x);
    	}
    }
    ll sum(ll x){
    	ll res=0;
    	while(x){
    		res+=ans[x];
    		x-=lowbit(x);
    	}
    	return res;
    }
    int main(){
    	ll res=0,i;
    	scanf("%lld",&n);
    	for(i=1;i<=n;i++){
    		scanf("%lld",&a[i].val);
    		a[i].wz=i;
    	}
    	stable_sort(a+1,a+1+n,cmp);//稳定排序 
    	for(i=1;i<=n;i++){
    		b[i]=a[i].wz;//离散化
    	}
    	for(i=1;i<=n;i++){
    		update(b[i]);
    		res+=i-sum(b[i]);
    	}
    	printf("%lld\n",res);
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,605
精华内容 5,442
关键字:

树状数组求逆序对