合浦县城乡规划建设局网站,做外汇网站卖判刑多少年,自己做网站模版,单仁牛商文章目录 一、动态求连续区间和 1、1 题目描述 1、2 题解关键思路与解答 二、数星星 2、1 题目描述 2、2 题解关键思路与解答 三、数列区间最大值 3、1 题目描述 3、2 题解关键思路与解答 标题#xff1a;树状数组与线段树问题 作者#xff1a;Ggggggtm 寄语#xff1a;与其… 文章目录 一、动态求连续区间和 1、1 题目描述 1、2 题解关键思路与解答 二、数星星 2、1 题目描述 2、2 题解关键思路与解答 三、数列区间最大值 3、1 题目描述 3、2 题解关键思路与解答 标题树状数组与线段树问题 作者Ggggggtm 寄语与其忙着诉苦不如低头赶路奋路前行终将遇到一番好风景 一、动态求连续区间和
1、1 题目描述 题目来源《信息学奥赛一本通》,Acwing模板题 题目难度简单 题目描述给定 n 个数组成的一个数列规定有两种操作一是修改某个元素二是求子数列 [a,b] 的连续和。 输入格式 第一行包含两个整数 n 和 m分别表示数的个数和操作次数。 第二行包含 n 个整数表示完整数列。 接下来 m 行每行包含三个整数 k,a,b k0表示求子数列[a,b]的和k1表示第 a 个数加 b。 数列从 1 开始计数。 输出格式 输出若干行数字表示 k0时对应的子数列 [a,b] 的连续和。 数据范围 1≤n≤100000, 1≤m≤100000 1≤a≤b≤n, 数据保证在任何时候数列中所有元素之和均在 int 范围内。 输入样例 10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8输出样例 11
30
351、2 题解关键思路与解答 我们知道求一段区间的和用前缀和数组会很方便时间复杂度也很快。但是当修改数组的数据时我们又要重新求前缀和数组这样下来时间复杂的就较高了为On*n的级别的。这个时候我们就可以用到树状数组来求解。树状数组是一个一维数组每个位置存储的数据是一段区间的和。以下为书抓鬼呢数组的模板我们只需要记住树状数组有三个比较重要的函数lowbit找下一个要操作的数、add改变大小、query求区间和。我们看代码 #include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010;int n, m;
int a[N], tr[N];int lowbit(int x)
{return x -x;
}void add(int x, int v)
{for (int i x; i n; i lowbit(i)) tr[i] v;
}int query(int x)
{int res 0;for (int i x; i; i - lowbit(i)) res tr[i];return res;
}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 ) add(i, a[i]);while (m -- ){int k, x, y;scanf(%d%d%d, k, x, y);if (k 0) printf(%d\n, query(y) - query(x - 1));else add(x, y);}return 0;
}
二、数星星
2、1 题目描述 题目来源《信息学奥赛一本通》 , Ural 1028 题目难度中等 题目描述 天空中有一些星星这些星星都在不同的位置每个星星有个坐标。 如果一个星星的左下方包含正左和正下有 k 颗星星就说这颗星星是 k 级的。 例如上图中星星 5 是 3 级的1,2,4 在它左下星星 2,4 是 1 级的。 例图中有 1 个 0 级2 个 1 级 1 个 2 级1 个 3 级的星星。 给定星星的位置输出各级星星的数目。 换句话说给定 N 个点定义每个点的等级是在该点左下方含正左、正下的点的数目试统计每个等级有多少个点。 输入格式 第一行一个整数 N表示星星的数目 接下来 N 行给出每颗星星的坐标坐标用两个整数 x,y 表示 不会有星星重叠。星星按 y 坐标增序给出y 坐标相同的按 x 坐标增序给出。 输出格式 N 行每行一个整数分别是 0 级1 级2 级……N−1 级的星星的数目。 数据范围 1≤N≤15000 0≤x,y≤32000。 输入样例 5
1 1
5 1
7 1
3 3
5 5输出样例 1
2
1
1
02、2 题解关键思路与解答 我们仔细分析上述题目题目中说道不会有星星重叠。星星按 y 坐标增序给出y 坐标相同的按 x 坐标增序给出。也就是输入的星星的做标顺序是按照从下往上从左往右依次给出的。我们只需要判断该星星的左下方位置有多少个星星来确定等级就行。由于是按照坐标顺序给出的所以这就给我们的统计带来了很大的方便。我们只需要看该坐标的横坐标有多少个比该做的横坐标小的数就是星星的个数。在统计时还不断插入新坐标相当于就是动态求数组的前缀和我们在这里就可以利用树状数组即可解决问题。我们看代码 #includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;const int N32010;int n;int c[N],level[N];int lowbit(int x)
{return x-x;
}int sum(int x)
{int res0;for(int ix;i;i-lowbit(i))resc[i];return res;
}void add(int x)
{for(int ix;iN;ilowbit(i))c[i];
}
int main()
{cinn;for(int i0;in;i){int x,y;scanf(%d%d,x,y);x;level[sum(x)];add(x);}for(int i0;in;i)printf(%d\n,level[i]);
}
三、数列区间最大值
3、1 题目描述 题目来源《信息学奥赛一本通》 题目难度中等 题目描述输入一串数字给你 M 个询问每次询问就给你两个数字 X,Y要求你说出 X 到 Y 这段区间内的最大数。 输入格式 第一行两个整数 N,M 表示数字的个数和要询问的次数 接下来一行为 N 个数 接下来 M 行每行都有两个整数 X,Y。 输出格式 输出共 M 行每行输出一个数。 数据范围 1≤N≤1e5, 1≤M≤1e6, 1≤X≤Y≤N, 数列中的数字均不超过2^31−1 输入样例 10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8输出样例 5
83、2 题解关键思路与解答 我们正常可以想到的就是暴力循环时间复杂度为On*n的级别。题目中歌的数据范围较大所以暴力是通过不了的。我们这个时候就可以使用线段树。线段树可以动态求一段区间的和、一段区间的最大值、最小值等问题。这个题中我们就是要求一段区间的最大值。什么是线段树呢线段树是一棵平衡二叉树。母结点代表整个区间的和越往下区间越小。注意线段树的每个节点都对应一条线段区间但并不保证所有的线段区间都是线段树的节点这两者应当区分开。 我们在使用线段树时通常会先建立一个结构体该结构体包含左右区间以及要求的值。每个节点 u 的左右子节点的编号分别为 2u 和 2u1 假如节点 u 储存区间 [l,r] 的和设 mid⌊(lr/)2⌋ 那么两个子节点分别储存 [l, mid] 和 [mid1,r] 的和。可以发现左节点对应的区间长度与右节点相同或者比之恰好多1。 线段树有四个重要的函数pushup通过子节点向上求父节点的和、build通过递归建立线段树、query求一段区间的最大值或最小值或 和、modify修该某个值。 我们来结合本题的代码一起理解一下 #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includeclimitsusing namespace std;const int N1e510;int w[N];struct Node
{int l,r;int maxv;
}tr[4*N];void build(int u,int l,int r)
{if(lr)tr[u]{l,r,w[r]};else{tr[u]{l,r};int midlr1;build(u1,l,mid),build(u1 | 1,mid1,r);tr[u].maxvmax(tr[u1].maxv,tr[u1 | 1].maxv);}
}int query(int u,int l,int r)
{if(tr[u].ll tr[u].rr)return tr[u].maxv;int midtr[u].ltr[u].r1;int maxvINT_MIN;if(lmid)maxvquery(u1,l,r);if(rmid)maxvmax(maxv,query(u1|1,l,r));return maxv;
}
int main()
{int n,m;scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,w[i]);build(1,1,n);int l,r;while(m--){scanf(%d%d,l,r);printf(%d\n,query(1,l,r));}return 0;
}
