【6】树状数组学习笔记

前言

树状数组是我学的第一个高级数据结构,属于 log ⁡ \log log 级数据结构。

其实现在一般不会单独考察数据结构,主要是其在其他算法(如贪心,DP)中起到优化作用。

长文警告:本文一共 995 995 995 行,请合理安排阅读时间。

lowbit函数

lowbit函数用于求解一个数二进制位最右边的 1 1 1 表示的权值,可以使用下面函数计算。

int lowbit(int x)
{return (x&(-x));
}

举个例子:

x = 1010100100 \;\;x=1010100100 x=1010100100

− x = 0101011100 -x=0101011100 x=0101011100

x & ( − x ) = 0000000100 = 4 x\&(-x)=0000000100=4 x&(x)=0000000100=4

树状数组本质上是一个数组,属于线性数据结构。树状数组中,把数按照其 l o w b i t lowbit lowbit 值进行分层,分层虽然没有明显的操作与现象,但导致画出来的层次像树一样,所以叫做树状数组

图片挂掉了

单点修改+区间查询

树状数组支持单点修改区间查询(一般是求和)。

对于 c c c 数组的定义(初始化):

c k = ∑ i = k − l o w b i t ( k ) + 1 k a i c_k=\sum_{i=k-lowbit(k)+1}^{k}a_i ck=i=klowbit(k)+1kai

原理类似于倍增,把原数组下标 k k k 按照二进制每位进行拆分,通过每个二进制位求出一段区间的和,最后加和得到区间前缀和。

注意:下标从 1 1 1 开始存储。

查询前缀和

使用 l o w b i t lowbit lowbit 求出下标最右边二进制位为 1 1 1 的数位表示的值,然后 c c c 数组对应元素累加到结果,再减去这个 l o w b i t lowbit lowbit 值,使之后可以求出下标第二右边二进制位为 1 1 1 的数位表示的值。重复这个过程,直到下标为 0 0 0

举个例子:

a a a [ 1 , 6 ] [1,6] [1,6] 的前缀和。

首先,因为 6 = 110 , l o w b i t ( 6 ) = 2 6=110,lowbit(6)=2 6=110,lowbit(6)=2 ,所以 c 6 = a 5 + a 6 c_6=a_5+a_6 c6=a5+a6

然后,将最后一位的 1 1 1 减掉,得到 4 = 100 , l o w b i t ( 4 ) = 4 4=100,lowbit(4)=4 4=100,lowbit(4)=4 ,所以 c 4 = a 1 + a 2 + a 3 + a 4 c_4=a_1+a_2+a_3+a_4 c4=a1+a2+a3+a4

最后, c 4 + c 6 = a 1 + a 2 + a 3 + a 4 + a 5 + a 6 c_4+c_6=a_1+a_2+a_3+a_4+a_5+a_6 c4+c6=a1+a2+a3+a4+a5+a6 ,也就是 a a a [ 1 , 6 ] [1,6] [1,6] 的前缀和。

正确性证明:

设原下标为 k k k ,由 l o w b i t lowbit lowbit c c c 数组的定义得求出 [ k − l o w b i t ( k ) + 1 , k ] [k-lowbit(k)+1,k] [klowbit(k)+1,k] 的和。设减去 l o w b i t ( k ) lowbit(k) lowbit(k) l l l ,求出 [ l − l o w b i t ( l ) + 1 , k − l o w b i t ( k ) ] [l-lowbit(l)+1,k-lowbit(k)] [llowbit(l)+1,klowbit(k)] 。观察得这两个区间是相接且不交叉的,可以合并为 [ l − l o w b i t ( l ) + 1 , k ] [l-lowbit(l)+1,k] [llowbit(l)+1,k] ,这样递推下去。由于最后下标为 0 0 0 ,故一定可以合并成 [ 1 , k ] [1,k] [1,k] 。证毕。

int getsum(int x)
{int t=0;while(x>0)t+=c[x],x-=lowbit(x);return t;
}

时间复杂度: O ( log ⁡ n ) O(\log n) O(logn)

单点修改

单点修改一个下标后,受影响的必然是减去 l o w b i t lowbit lowbit 后是这个下标,所以可以把 l o w b i t lowbit lowbit 加回来,同时把 c c c 数组增加。当然,如果超过了数组元素个数 n n n 就没必要再加了。

void add(int x,int d)
{while(x<=n)c[x]+=d,x+=lowbit(x);
}

时间复杂度: O ( log ⁡ n ) O(\log n) O(logn)

初始化

不需要按照 c c c 数组的定义来,可以把每一个数都进行一次单点修改操作。

void init()
{for(int i=1;i<=n;i++)add(i,a[i]);
}

时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn)

区间求和

使用查询前缀和查询出前缀和,然后相减就是区间的和。

int ask(int x,int y)
{return getsum(y)-getsum(x-1);
}

时间复杂度: O ( log ⁡ n ) O(\log n) O(logn)

单点修改+区间查询例题

例题 1 1 1

P3374 【模板】树状数组 1

单点修改+区间查询模板题,不多赘述。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[600000],c[600000];
int lowbit(int x)
{return (x&(-x));
}void add(int x,int d)
{while(x<=n)c[x]+=d,x+=lowbit(x);
}void init()
{for(int i=1;i<=n;i++)add(i,a[i]);
}int getsum(int x)
{int t=0;while(x>0)t+=c[x],x-=lowbit(x);return t;
}int ask(int x,int y)
{return getsum(y)-getsum(x-1);
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);init(); for(int i=0;i<m;i++){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op==1)add(x,y);else if(op==2)printf("%d\n",ask(x,y));}return 0;
}

例题 2 2 2

P2068 统计和

类似例题 1 1 1 ,但是不用初始化,注意字符的输入。

#include <bits/stdc++.h>
using namespace std;
long long n,m,a[600000],c[600000];
long long lowbit(long long x)
{return (x&(-x));
}void add(long long x,long long d)
{while(x<=n)c[x]+=d,x+=lowbit(x);
}long long getsum(long long x)
{long long t=0;while(x>0)t+=c[x],x-=lowbit(x);return t;
}long long ask(long long x,long long y)
{return getsum(y)-getsum(x-1);
}int main()
{cin>>n>>m;for(int i=0;i<m;i++){char op;int x,y;cin>>op>>x>>y;if(op=='x')add(x,y);else if(op=='y')printf("%lld\n",ask(x,y));}return 0;
}

例题 3 3 3

P2982 [USACO10FEB]Slowing down G

树上树状数组。

由于每次每头牛走完之后会单点修改一个值,而放慢速度的次数又取决于从根到目标节点的区间和,自然联想到树状数组。

首先预处理出每个节点的层次,一方面方便遍历树,另一方面方便树上树状数组。

对于单点修改的操作,考虑预处理出修改每个节点之后会影响的点,可以通过先搜索层次深的节点,搜索更浅的节点时记忆化,做到将近 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的复杂度。

对于区间查询的操作,考虑预处理出查询每个节点之前会计算的点,可以通过先搜索层次浅的节点,搜索更深的节点时记忆化,同样做到将近 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的复杂度。

然后,由于已经预处理了每个点的影响与计算,所以树状数组操作时只需要遍历这些预处理的记录就行了。

注意一定要记忆化,否则很容易退化回 O ( n 2 ) O(n^2) O(n2)

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
struct edge
{int to,next;
}e[300000];
struct order
{int p,c;
}xu[100001];
struct node
{int b;vector<int>low;vector<int>high;
}retree[100001];
int n,h[100001],tol=0,c[100001],book[100001]; 
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*10+ch-48;ch=getchar();}return x*f;
}bool cmp(struct order a,struct order b)
{return a.c>b.c;
}void add_edge(int u,int v)
{e[++tol].next=h[u];e[tol].to=v;h[u]=tol;
}void dfs1(int root,int ce)
{retree[root].b=ce;for(register int i=h[root];i;i=e[i].next){if(book[e[i].to])continue;book[e[i].to]=1;dfs1(e[i].to,ce+1);}
}void dfs2(int root,int from,int want)
{if(retree[root].b==want){int l=retree[root].low.size();for(int i=0;i<l;i++)retree[from].low.push_back(retree[root].low[i]);return;}if(want>n)return;for(register int i=h[root];i;i=e[i].next){if(retree[e[i].to].b<=retree[root].b)continue;dfs2(e[i].to,from,want);}
}void dfs3(int root,int from,int want)
{if(retree[root].b==want){int l=retree[root].high.size();for(int i=0;i<l;i++)retree[from].high.push_back(retree[root].high[i]);want-=lowbit(want);return;}if(want<=0)return;for(register int i=h[root];i;i=e[i].next){if(retree[e[i].to].b>=retree[root].b)continue;dfs3(e[i].to,from,want);}
}void add(int x)
{int l=retree[x].low.size();for(register int i=0;i<l;i++)c[retree[x].low[i]]++;
}int query(int x)
{int t=0,l=retree[x].high.size();for(register int i=0;i<l;i++)t+=c[retree[x].high[i]];return t;
}int main()
{n=read();for(register int i=0;i<n-1;i++){int u,v;u=read();v=read();add_edge(u,v);add_edge(v,u);}for(register int i=1;i<=n;i++){retree[i].low.push_back(i);retree[i].high.push_back(i);}book[1]=1;dfs1(1,1);for(register int i=1;i<=n;i++)xu[i].p=i,xu[i].c=retree[i].b;sort(xu+1,xu+n+1,cmp);for(register int i=1;i<=n;i++)dfs2(xu[i].p,xu[i].p,retree[xu[i].p].b+lowbit(retree[xu[i].p].b));for(register int i=n;i>=1;i--)dfs3(xu[i].p,xu[i].p,retree[xu[i].p].b-lowbit(retree[xu[i].p].b));for(register int i=1;i<=n;i++){int p;p=read();printf("%d\n",query(p));add(p);}return 0;
}

当然,每次修改时计算也是可以的,而且可以大大减少码量,这里不多赘述。

例题 4 4 4

P4054 [JSOI2009] 计数问题

由于权值值域很小( c ≤ 100 c\le100 c100 ),可以对每一种权值建立一个二维树状数组,每次更新时单独更新。一个某种权值的格子会对这种权值的答案造成 1 1 1 的贡献,所以可以把每个这种权值的格子视为 1 1 1 ,其他的格子视为 0 0 0 。统计个数时加起来就行了。

操作 1 1 1 的处理:

首先,如果把 a a a 修改成 b b b ,那么会影响 a a a b b b 两种权值的二维树状数组。可以把 a a a 的树状数组影响到的值都加 1 1 1 ,而 b b b 的树状数组影响到的值都减 1 1 1 ,从而达到修改的目的。

注意:警示后人(0pts,仅过Subtask #1)

对于影响到的值,可以参考一维树状数组的解决方式。将横坐标与纵坐标分别加上其 l o w b i t lowbit lowbit ,把原区间划分为四个小区间。

void add(int x,int y,int k,int s)
{int i=x,j=y;while(x<=n){y=j;while(y<=m)c[x][y][s]+=k,y+=lowbit(y);x+=lowbit(x);}
}void insert()
{int x=0,y=0,c=0;scanf("%d%d%d",&x,&y,&c);add(x,y,1,c);add(x,y,-1,a[x][y]);a[x][y]=c;
}

操作 2 2 2 的处理:

s [ i ] [ j ] s[i][j] s[i][j] 表示二维右下点为 ( i , j ) (i,j) (i,j) 的矩形的前缀和,利用容斥原理得到矩形 ( x 1 , y 1 , x 2 , y 2 ) (x_1,y_1,x_2,y_2) (x1,y1,x2,y2) 的加和值为:

s [ x 2 ] [ y 2 ] − s [ x 1 − 1 ] [ y 2 ] − s [ x 2 ] [ y 1 − 1 ] + s [ x 1 − 1 ] [ y 1 − 1 ] s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][y_1-1] s[x2][y2]s[x11][y2]s[x2][y11]+s[x11][y11]

对于前缀和的处理,可以参考一维树状数组的解决方式。将横坐标与纵坐标分别减去其 l o w b i t lowbit lowbit ,把原区间划分为四个小区间。

int getsum(int x,int y,int k)
{int t=0,i=x,j=y;while(x>0){y=j;while(y>0)t+=c[x][y][k],y-=lowbit(y);x-=lowbit(x);}return t;
}int query()
{int x1,y1,x2,y2,c;scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);return (getsum(x2,y2,c)-getsum(x1-1,y2,c)-getsum(x2,y1-1,c)+getsum(x1-1,y1-1,c));
}

最后,把这些操作拼起来,再加上输入输出与初始化即可。

#include <bits/stdc++.h>
using namespace std;
int n,m,q,a[301][301],c[301][301][101],op;
int lowbit(int x)
{return (x&(-x));
}void add(int x,int y,int k,int s)
{int i=x,j=y;while(x<=n){y=j;while(y<=m)c[x][y][s]+=k,y+=lowbit(y);x+=lowbit(x);}
}void insert()
{int x=0,y=0,c=0;scanf("%d%d%d",&x,&y,&c);add(x,y,1,c);add(x,y,-1,a[x][y]);a[x][y]=c;
}int getsum(int x,int y,int k)
{int t=0,i=x,j=y;while(x>0){y=j;while(y>0)t+=c[x][y][k],y-=lowbit(y);x-=lowbit(x);}return t;
}int query()
{int x1,y1,x2,y2,c;scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);return (getsum(x2,y2,c)-getsum(x1-1,y2,c)-getsum(x2,y1-1,c)+getsum(x1-1,y1-1,c));
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)add(i,j,1,a[i][j]); scanf("%d",&q);for(int i=0;i<q;i++){scanf("%d",&op);if(op==1)insert(); else if(op==2)printf("%d\n",query());}return 0;
}

区间修改+单点查询

树状数组支持单点查询区间修改(一般是求和)。

单点修改,区间查询使用的是前缀和思想,把它反过来,变成差分思想,就能够实现单点查询,区间修改。

首先建立一个差分数组,其中每个值定义为:

b i = a i ( i = 1 ) b_i=a_i(i=1) bi=ai(i=1)

b i = a i − a i − 1 ( i ≠ 1 ) b_i=a_i-a_{i-1}(i\neq1) bi=aiai1(i=1)

之后,在差分数组上建立树状数组。

单点查询

同单点修改,区间查询的查询前缀和。

因为由差分数组的定义,可以知道差分数组前 i i i 项的和为:

b i + b i − 1 ⋯ + b 2 + b 1 = a i − a i − 1 + a i − 1 − a i − 2 ⋯ + a 2 − a 1 + a 1 = a i \begin{aligned} b_i+b_{i-1}\dots+b_2+b_1 = a_i&-a_{i-1}+a_{i-1}-a_{i-2}\dots+a_{2}-a_{1}+a_{1}\\=a_i\end{aligned} bi+bi1+b2+b1=ai=aiai1+ai1ai2+a2a1+a1

所以,可以直接在差分数组上查询前 i i i 项的前缀和,就是 a i a_i ai 的值。

int getsum(int x)
{int t=0;while(x>0)t+=c[x],x-=lowbit(x);return t;
}

时间复杂度: O ( log ⁡ n ) O(\log n) O(logn)

区间修改

对于 [ l , r ] [l,r] [l,r] 区间增加 k k k 的修改,可以把位置分为一下几类:

1 1 1 l < i ≤ r l\lt i\le r l<ir

b i = b i + k − ( b i − 1 + k ) = b i − b i − 1 b_i=b_i+k-(b_{i-1}+k)=b_i-b_{i-1} bi=bi+k(bi1+k)=bibi1

没有变化,无需修改。

2 2 2 i = l i=l i=l

b i = b i + k − b i − 1 = b i − b i − 1 + k b_i=b_i+k-b_{i-1}=b_i-b_{i-1}+k bi=bi+kbi1=bibi1+k

按照之前的修改操作将第 l l l + k +k +k 即可。

3 3 3 i = r + 1 i=r+1 i=r+1

b i = b i − ( b i − 1 + k ) = b i − b i − 1 − k b_i=b_i-(b_{i-1}+k)=b_i-b_{i-1}-k bi=bi(bi1+k)=bibi1k

按照之前的修改操作将第 r + 1 r+1 r+1 − k -k k 即可。

void add(int x,int d)
{while(x<=n)c[x]+=d,x+=lowbit(x);
}void pluss()
{int x,y,k;scanf("%d%d%d",&x,&y,&k);add(x,k);add(y+1,-k);
}

时间复杂度: O ( log ⁡ n ) O(\log n) O(logn)

初始化

在差分数组上建立树状数组。

void init()
{for(int i=1;i<=n;i++)add(i,b[i]);
}

时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn)

区间修改+单点查询例题

例题 5 5 5

P3368 【模板】树状数组 2

区间修改+单点查询模板题,不多赘述。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[600000],b[600000],c[600000];
int lowbit(int x)
{return (x&(-x));
}void add(int x,int k)
{while(x<=n)c[x]+=k,x+=lowbit(x);
}void init()
{for(int i=1;i<=n;i++)add(i,b[i]);
}int getsum(int x)
{int ans=0;while(x>0)ans+=c[x],x-=lowbit(x);return ans;
}void pluss()
{int x,y,k;scanf("%d%d%d",&x,&y,&k);add(x,k);add(y+1,-k);
}int ask()
{int x;scanf("%d",&x);return getsum(x);
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];init();for(int i=1;i<=m;i++){int op;scanf("%d",&op);if(op==1)pluss();else if(op==2)printf("%d\n",ask());}return 0;
}

例题 6 6 6

P5057 [CQOI2006]简单题

同例题 5 5 5 ,不用初始化。

对于数字反转,可以修改时直接将数字加 1 1 1 ,查询时利用对 2 2 2 取模的周期性来解决。

#include <bits/stdc++.h>
using namespace std;
int n,m,b[600000],c[600000];
int lowbit(int x)
{return (x&(-x));
}void add(int x,int k)
{while(x<=n)c[x]+=k,x+=lowbit(x);
}int getsum(int x)
{int ans=0;while(x>0)ans+=c[x],x-=lowbit(x);return ans;
}void pluss()
{int x,y,k=1;scanf("%d%d",&x,&y);add(x,k);add(y+1,-k);
}int ask()
{int x;scanf("%d",&x);return (getsum(x)+2)%2;
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int op;scanf("%d",&op);if(op==1)pluss();else if(op==2)printf("%d\n",ask());}return 0;
}

树状数组求逆序对

一般来说,可以使用归并排序来求一个序列中的逆序对数。但是,树状数组也可以完成。

其中步骤如下:

1 1 1 :将数组离散化,映射到 1 ∼ n 1\sim n 1n

教练推荐的离散化博客:浅谈数据的离散化

2 2 2 :建立一个树状数组, c i c_i ci 表示离散化后数字 i i i 出现的次数。

3 3 3 :从左到右依次遍历数组,设这个 a i a_i ai k k k 每次修改对应 c k c_k ck ,进行一次 + 1 +1 +1 。然后根据数组有序时的要求是升序还是降序,查询 [ k + 1 , n ] [k+1,n] [k+1,n] [ 1 , k − 1 ] [1,k-1] [1,k1] 的区间和,累加进 a n s ans ans

4 4 4 :结束,输出 a n s ans ans

树状数组求逆序对用到的是单点修改+区间查询的树状数组。

树状数组求逆序对例题

例题 7 7 7

P1908 逆序对

求逆序对数板子题,可以归并排序,亦可树状数组,这里使用树状数组,不多赘述。

#include <bits/stdc++.h>
using namespace std;
struct node
{long long x,y;
}a[600000];
long long n,m,ans=0,b[600000],c[600000];
bool cmp(struct node a,struct node b)
{return a.y<b.y;
}long long lowbit(long long x)
{return (x&(-x));
}void add(long long x,long long d)
{while(x<=n)c[x]+=d,x+=lowbit(x);
}void init()
{sort(a+1,a+n+1,cmp);b[a[1].x]=++m;for(long long i=2;i<=n;i++)if(a[i].y!=a[i-1].y)b[a[i].x]=++m;else b[a[i].x]=m;
}long long getsum(long long x)
{long long t=0;while(x>0)t+=c[x],x-=lowbit(x);return t;
}int main()
{scanf("%lld",&n);for(long long i=1;i<=n;i++){scanf("%lld",&a[i].y);a[i].x=i;}init();for(long long i=1;i<=n;i++){add(b[i],1);ans+=(i-getsum(b[i]));}printf("%lld",ans);return 0;
}

例题 8 8 8

P1774 最接近神的人

实质就是求一个数组的逆序对数,推导过程可以看 零碎知识点整理 杂项部分 3.2 3.2 3.2 的证明部分。

#include <bits/stdc++.h>
using namespace std;
struct node
{long long x,y;
}a[600000];
long long n,m,ans=0,b[600000],c[600000];
bool cmp(struct node a,struct node b)
{return a.y<b.y;
}long long lowbit(long long x)
{return (x&(-x));
}void add(long long x,long long d)
{while(x<=n)c[x]+=d,x+=lowbit(x);
}void init()
{sort(a+1,a+n+1,cmp);b[a[1].x]=++m;for(long long i=2;i<=n;i++)if(a[i].y!=a[i-1].y)b[a[i].x]=++m;else b[a[i].x]=m;
}long long getsum(long long x)
{long long t=0;while(x>0)t+=c[x],x-=lowbit(x);return t;
}int main()
{scanf("%lld",&n);for(long long i=1;i<=n;i++){scanf("%lld",&a[i].y);a[i].x=i;}init();for(long long i=1;i<=n;i++){add(b[i],1);ans+=(i-getsum(b[i]));}printf("%lld",ans);return 0;
}

例题 9 9 9

P1637 三元上升子序列

首先,为了计算方便,可以以中间那个数,也就是 a j a_j aj 为基准。设在在这个数之前有 n n n 个数比它小,在这个数之后有 m m m 个数比它大,那么由于前后各自任选一个就能构成一组 thair ,根据乘法原理得到 a n s ans ans 应该累加 n × m n\times m n×m

我们可以进行两次树状数组求逆序对:第一次求某个数之前比它小的数的个数,第二次反转序列,求某个数之后比它大的数的个数。

由于 a i a_i ai 的范围很小,所以不用离散化,但是 警示后人(73pts,WA on #4 #9 #10) 。

#include <bits/stdc++.h>
using namespace std;
long long n,ans=0,maxn=0,a[300000],c[300000],ls[300000],rb[300000];
long long lowbit(long long x)
{return (x&(-x));
}void add(long long x,long long d)
{while(x<=maxn)c[x]+=d,x+=lowbit(x);
}long long getsum(long long x)
{long long t=0;while(x>0)t+=c[x],x-=lowbit(x);return t;
}int main()
{scanf("%lld",&n);for(long long i=1;i<=n;i++){scanf("%lld",&a[i]);maxn=max(maxn,a[i]);}for(long long i=1;i<=n;i++){add(a[i],1);ls[i]=getsum(a[i]-1);}memset(c,0,sizeof(c));for(long long i=n;i>=1;i--){add(a[i],1);rb[i]=getsum(maxn)-getsum(a[i]);}for(long long i=1;i<=n;i++)ans+=ls[i]*rb[i];printf("%lld\n",ans);return 0;
}

例题 10 10 10

P1966 [NOIP2013 提高组] 火柴排队

排序题目的巅峰。

首先,由于距离是两数之差的平方,有一个显然的贪心:把两个数组从小到大排序,同一位置的数互相对应,此时距离最小。交换两数后,由于平方的影响,绝对值之差会较大,导致距离也较大,证明了贪心的正确性。

然后,将 a a a 数组的每个数与 b b b 数组建立映射关系,同时进行离散化。可以记录下数组 a a a 中每个数字排序前的位置,再以排序后其对应的 b b b 数组的元素的位置作为关键字进行离散化。这样相当于数组中记录的是在不改变 b b b 数组的情况下,每个数组元素在距离最小情况下的排名。

由于数组记录的是排名,那么最小情况必然是一个单升不降的序列。此时的序列是一个乱序序列,要求最小化将这个序列排好序的相邻两数交换次数。这点就很像例题 8 8 8 ,实质就是求一个数组的逆序对数,树状数组求解即可,推导过程可以看 零碎知识点整理 杂项部分 3.2 3.2 3.2 的证明部分。

由于每次交换,逆序对数量要么 + 1 +1 +1 ,要么 − 1 -1 1 ,两个序列地位相同,可以只变换一个序列,最终最优解不受影响,再次保证了算法的正确性。

#include <bits/stdc++.h>
const int MOD=100000000-3;
using namespace std;
struct node
{int x,v;
}a[200000],b[200000];
long long n,m=1,ans,c[200000],d[200000]; 
bool cmp(struct node a,struct node b)
{return a.v<b.v;
}long long lowbit(long long x)
{return (x&(-x));
}void add(long long x,long long k)
{while(x<=m)c[x]+=k,x+=lowbit(x);
}long long getsum(long long x)
{long long ans=0;while(x>0)ans+=c[x],x-=lowbit(x);return ans;
}int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i].v);a[i].x=i;}for(int i=1;i<=n;i++){scanf("%lld",&b[i].v);b[i].x=i;}sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);for(int i=1;i<=n;i++){if(i!=1&&a[i].v!=a[i-1].v)m++;d[a[i].x]=b[i].x;}for(int i=1;i<=n;i++){add(d[i],1);ans+=((getsum(m)%MOD-getsum(d[i])%MOD)+MOD)%MOD;ans%=MOD;}printf("%lld\n",ans%MOD);return 0;
}

后记

树状数组讲了两个星期,可见其内容之多,共 995 995 995 行。

数据结构果然毒瘤啊qaq

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/33563.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

研发团队协作软件推荐:18款工具对比

本文将深入对比18款主流研发团队协作软件&#xff1a;PingCode、 Worktile、钉钉、飞书、企业微信、Teambition、蓝湖、石墨文档、明道等。 在当今信息化时代&#xff0c;研发团队协作软件已经成为企业提高工作效率、改善团队沟通与管理的重要工具。借助这些软件&#xff0c;企…

Java8的新特性

1.Lambda表达式和函数式接口 Lambda的基础&#xff1a;函数式接口 Java 8与之前版本的区别&#xff1a; Java 7及之前&#xff1a;接口中只能包含抽象方法&#xff0c;无法通过函数式接口简洁地表示Lambda表达式。Java 8&#xff1a;通过FunctionalInterface注解&#xff0c;明…

数据库管理-第302期 国产类RAC架构数据库网络连接方式(20250314)

数据库管理302期 2025-03-14 数据库管理-第302期 国产类RAC架构数据库网络连接方式&#xff08;20250314&#xff09;1 Oracle RAC2 DMDSC3 YAC4 KES RAC总结 数据库管理-第302期 国产类RAC架构数据库网络连接方式&#xff08;20250314&#xff09; 作者&#xff1a;胖头鱼的鱼…

Spring框架详解(IOC容器-上)

IOC&#xff08; Inversion of Control&#xff0c;控制反转&#xff09;和DI&#xff08;dependency injection&#xff09;是Spring框架的核心特性&#xff0c;也是Spring框架的基础。 Spring框架作为一个IOC容器&#xff0c;负责加载、创建和管理Spring Bean。 接下来介绍…

架构学习第八周--Kubernetes博客搭建

目录 一、整体架构 二、部署MySQL主从 三、部署Redis哨兵 四、部署WordPress 五、注意事项 一、整体架构 本项目为在一主三从的Kubernetes集群上部署WordPress博客。因为WordPress部分容器版本自行集成Apache和PHP服务&#xff0c;因此在Kubernetes上部署WordPress只需提供…

【品铂科技】在高精度定位行业内的口碑怎么样?

1. ‌技术实力与行业认可‌ 公司自主研发的ABELL无线实时定位系统在复杂环境中&#xff08;如工业、司法监狱等&#xff09;展现出厘米级&#xff08;5-10厘米&#xff09;高精度定位能力&#xff0c;客户反馈系统稳定性强、抗干扰能力突出&#xff0c;成为行业技术标杆‌。参…

长度最小的子数组-滑动窗口解法

本来觉得自己双指针学的还可以了&#xff0c;于是今天直接刷了一道滑动窗口题&#xff0c;没想到还是被坑绊倒了两次。这次我想记录在博客里&#xff0c;不仅可以防止我以后重蹈覆辙&#xff0c;兴许也还可以帮助到其他人。 题目来自力扣&#xff1a;209. 长度最小的子数组 - …

深入理解Linux网络随笔(七):容器网络虚拟化--Veth设备对

深入理解Linux网络随笔&#xff08;七&#xff09;&#xff1a;容器网络虚拟化 微服务架构中服务被拆分成多个独立的容器&#xff0c;docker网络虚拟化的核心技术为&#xff1a;Veth设备对、Network Namespace、Bridg。 Veth设备对 veth设备是一种 成对 出现的虚拟网络接口&…

深入理解 Maven BOM 及其继承特性

深入理解 Maven BOM 及其继承特性 一、什么是 Maven BOM&#xff1f; Maven BOM&#xff08;Bill Of Materials&#xff0c;物料清单&#xff09;是一种特殊的 Maven 项目&#xff0c;用于集中管理依赖项的版本信息。BOM 项目本身并不包含实际的代码或资源&#xff0c;而仅仅…

C语言(25)

一.数据在内存中的存储 1.整数在内存中的存储 整数在内存中以二进制的形式储存&#xff0c;分别为原码&#xff0c;补码&#xff0c;反码 有符号的整数&#xff0c;在上述三种形式都有符号位和数值位两个部分&#xff0c;符号位为0是正数&#xff0c;1是负数&#xff0c;最高…

一篇博客搞定时间复杂度

时间复杂度 1、什么是时间复杂度&#xff1f;2、推导大O的规则3、时间复杂度的计算3.1 基础题 13.2 基础题 23.3基础题 33.4进阶题 13.5进阶题 23.6 偏难题 13.7偏难题 2&#xff08;递归&#xff09; 前言&#xff1a; 算法在编写成可执行程序后&#xff0c;运行时要耗费时间和…

探索 Trossen AI:从 Aloha到智能机器人平台的进化之路

在人工智能与机器人技术快速发展的当下&#xff0c;科研硬件的性能与成本成为影响行业创新的重要因素。Trossen Robotic为在机器人领域二十余年的知名企业&#xff0c;近日推出的 Trossen AI 系列产品&#xff0c;为科研机构与开发者提供了高性能、高性价比的解决方案。 Trosse…

【Power Platform系列】如何在画布应用中调用工作流上传附件

在Power Apps画布应用中上传附件&#xff0c;比如到SharePoint文档库最典型的方式非常简单&#xff0c;插入一个编辑窗体&#xff0c;将窗体和背后的文档库绑定起来即可以快速实现。不过窗体内部的显示格式很难控制&#xff0c;如果要实现更为灵活的控制&#xff0c;就需要采用…

工作记录 2017-01-12

序号 工作 相关人员 1 协助BPO进行Billing的工作。 处理Amazing Charts的数据查询。 修改BillingJobPoster&#xff0c;处理CCDA 的自动导入&#xff0c;预计还需一天才能完成。 修改录入Code的界面&#xff08;code 移动到指定位置&#xff09;&#xff0c;预计明天更新。…

在centOS Linux系统搭建自动化构建工具Jenkins

前言 在工作中发现公司使用Jenkins实现自动化部署项目方案&#xff0c;于是闲着自己也捣鼓一下&#xff0c;网上查阅相关部署资料&#xff0c;顺便记录操作步骤&#xff0c;所以有了下面这篇的文章。 部署完之后&#xff0c;安装前端项目所需环境&#xff0c;比如node环境&am…

开箱即用的whisper-service服务

安装须知 Whisper官方网址 https://github.com/openai/whisper Whisper 镜像站 https://docker.aityp.com/r/docker.io/onerahmet 本次提供的环境镜像为&#xff1a;docker.io/onerahmet/openai-whisper-asr-webservice:v1.6.0-gpu 运行环境要求 服务器架构 服务器架构要…

SpringCloud带你走进微服务的世界

认识微服务 随着互联网行业的发展&#xff0c;对服务的要求也越来越高&#xff0c;服务架构也从单体架构逐渐演变为现在流行的微服务架构。这些架构之间有怎样的差别呢&#xff1f; 单体架构 单体架构&#xff1a;将业务的所有功能集中在一个项目中开发&#xff0c;打成一个…

【xv6操作系统】页表与写时拷贝解析及相关实验设计

【xv6操作系统】页表与写时拷贝解析及相关实验设计 页表页表概念xv6页表xv6 TLB实验1&#xff1a;加速系统调用实验2&#xff1a;打印三级页表实验3&#xff1a;检测已访问的页表 写时拷贝写时拷贝实验实现 页表 页表概念 deepseek说&#xff1a; 页表&#xff08;Page Table…

如何处理PHP中的编码问题

如何处理PHP中的编码问题 在PHP开发过程中&#xff0c;编码问题是一个常见且棘手的问题。无论是处理用户输入、数据库交互&#xff0c;还是与外部API通信&#xff0c;编码问题都可能导致数据乱码、解析错误甚至安全漏洞。本文将深入探讨PHP中的编码问题&#xff0c;并提供一些…

人工智能之数学基础:线性变换的象空间和零空间

本文重点 前面的课程中,我们学习了线性变换,由此而引申出线性变换的象空间和零空间,这两个空间在机器学习领域会被经常用到,本文对此进行学习。 直观理解 总的来说象空间就是经过线性变换得到的空间,零空间就是经过线性变换是零的元素构成的空间。 从几何角度来看,象空…