[树状数组]求逆序对-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

[树状数组]求逆序对

阅读量：5365 次

发布时间：2019-06-15

本文共 2980 字，大约阅读时间需要 9 分钟。

树状数组基本讲解：

树状数组的用途就是求前缀和，他的本质跟线段树相似，就是一个空间换时间。

主要采用lowbit，通过二进制从而划分区间。

增加的时候，从下往上依次加lowbit

查询的时候，从上往下减去lowbit。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #define For(a,b) for(int a=0;a
               
                > t ;36 for(int j=1;j<=t;j++){37 scanf("%d",&n);38 _mem(c,n); //初始化数组中前n+1个数为039 for(int i=1;i<=n;i++){40 scanf("%d",&z);41 update(i,z,n);42 }43 cout <<"Case "<
                
                 <<":"<
                 
                  > s;46 if(s[0] == 'E')47 break;48 scanf("%d%d",&x,&y);49 if(s[0] == 'Q')50 cout << getsum(y)-getsum(x-1)<

View Code

求逆序对！

ci 的意思是在前lowbit 中元素的个数。

然后往前i个中的sum就是小于等于这个i的个数

这个数的位置-小于等于这个i的个数就是前面大于这个数的个数

小于等于这个数的个数肯定比这个数的位置要小。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
               10 using namespace std;11 typedef long long ll;12 const int N=1000+10;13 int c[N],n,aa;14 int lowbit(int x)15 {16 return x&-x;17 }18 void insert(int i,int x)19 {20 while(i<=n)21 {22 c[i]+=x;23 i+=lowbit(i);24 }25 }26 int getsum(int i)27 {28 int sum=0;29 while(i>0)30 {31 sum+=c[i];32 i-=lowbit(i);33 }34 return sum;35 }36 int main()37 {38 while(scanf("%d",&n)!=EOF)39 {40 int ans=0;41 memset(c,0,sizeof(c));42 for(int i=1;i<=n;i++)43 {44 scanf("%d",&aa);45 insert(aa,1);46 ans+=i-getsum(aa);47 }48 printf("%d\n",ans);49 }50 return 0;51 }

View Code

挖个坑下回把归并和快排的求逆序对放下来。

F - Cube

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
             8 #include 
             
               9 #include 
              
               10 #include 
               
                11 using namespace std;12 typedef long long ll;13 const int inf=0x7fffffff;14 const int N=110;15 const int M=500000+10;16 int a[N][N][N],c[N][N][N];17 int n,m;18 int lowbit(int x)19 {20 return x&-x;21 }22 void insert(int x,int y,int z,int iii)23 {24 for(int i=x;i<=n;i+=lowbit(i))25 for(int j=y;j<=n;j+=lowbit(j))26 for(int k=z;k<=n;k+=lowbit(k))27 c[i][j][k]+=iii;28 }29 int getsum(int x,int y,int z)30 {31 int sum=0;32 for(int i=x;i>0;i-=lowbit(i))33 for(int j=y;j>0;j-=lowbit(j))34 for(int k=z;k>0;k-=lowbit(k))35 sum+=c[i][j][k];36 return sum;37 }38 int main()39 {40 while(scanf("%d %d",&n,&m)!=EOF)41 {42 memset(c,0,sizeof(c));43 int ss,xx,yy,zz;44 while(m--)45 {46 scanf("%d %d %d %d",&ss,&xx,&yy,&zz);47 if(ss==1)48 {49 int xxx,yyy,zzz;50 scanf("%d %d %d",&xxx,&yyy,&zzz);51 xxx++; yyy++; zzz++;52 insert(xx,yy,zz,1);53 insert(xx,yy,zzz,1);54 insert(xx,yyy,zz,1);55 insert(xx,yyy,zzz,1);56 insert(xxx,yy,zz,1);57 insert(xxx,yy,zzz,1);58 insert(xxx,yyy,zz,1);59 insert(xxx,yyy,zzz,1);60 }61 else62 {63 printf("%d\n",getsum(xx,yy,zz)&1);64 }65 }66 }67 68 return 0;69 }

View Code

转载于:https://www.cnblogs.com/Kaike/p/10318724.html

你可能感兴趣的文章

sql server中bit字段实现取反操作

Part3_lesson2---ARM指令分类学习

jQuery拖拽原理实例

JavaScript 技巧与高级特性

Uva 11729 Commando War

增强学习（一） ----- 基本概念

ubuntu下USB连接Android手机

C# 语句分支语句 switch----case----.

反射获取 obj类的属性与对应值

表单中的readonly与disable的区别（zhuan）

win10下安装配置mysql-8.0.13--实战可用

周记2018.8.27~9.2

MySQL中 1305-FUNCTION liangshanhero2.getdate does not exit 问题解决

Ctrl+Alt+Down/Up 按键冲突

python序列化和json

网格与无网格

SSH-struts2的异常处理

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-11-30 07:33:21 当前IP: 18.188.68.115 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我