Ⅰ, 抛出问题
Description
有一列元素, 每一个元素有三个属性: 标号, 标识符, 数值. 这些元素按照标号从 1~n 排列, 标识符也是 1~n 的一个排列, 初始时数值为 0. 当然我们可以把每个元素看成一个多维数字, 那么这列元素就是一个数列.
现在请你维护这个数列, 使其能支持以下两种操作: 1. 将标号为 l~r 的所有元素的数值先乘上 x, 再加上 y;2. 将标识符为 l~r 的所有元素的数值先乘上 x, 再加上 y. 当然你还得回答某些询问: 1. 标号为 l~r 的所有元素的数值的和; 2. 标识符为 l~r 的所有元素的数值的和.
Input
第一行有两个正整数 n,m, 分别表示数列长度和操作与询问个数的总和. 第二行有 n 个正整数, 表示每个元素的标识符, 保证这 n 个数是 1~n 的一个排列. 接下来 m 行, 每行的第一个数字为 op. 若 op 为 0, 则表示要进行第一个操作, 接下去四个数字表示 l,r,x,y; 若 op 为 1, 则表示要进行第二个操作, 接下去四个数字表示 l,r,x,y; 若 op 为 2, 则表示要回答第一个询问, 接下去两个数字表示 l,r; 若 op 为 3, 则表示要回答第二个询问, 接下去两个数字表示 l,r.
Output
包含若干行, 每行表示一个询问的答案. 由于答案可能很大, 只要请你输出答案对 536870912 取模后的值即可.
- Sample Input
- 4 4
- 2 1 4 3
- 0 2 3 4 5
- 1 1 3 4 7
- 2 1 1
- 3 1 1
- Sample Output
- 7
- 27
- HINT
第一次操作后, 数列变为 0 5 5 0
第二次操作后, 数列变为 7 27 5 7
- N,M<=50000, 1<=L<=R<=N 0<=X,Y<=2^31-1
- Source
bzoj4303 数列
Ⅱ, 分析问题
kdtree, 全称 k-dimensional-tree, 意思即为 k 维树, 主要用于解决高维空间的修改查询操作, 支持打标记, 求最近最远点对等, 类似于线段树等数据结构, 接下来就来详细讲讲 kdtree 的写法
1, 维护的数据
写数据结构, 一定要弄清维护了哪些数据
看代码得了..
注: 代码中给的是二维 kdtree 的模板, 所以只有两位
- struct hahaha{
- int tp,ls,rs,v[2],Max[2],Min[2],val;//tp 为当前节点维护的是哪一位, ls,rs 分别为左右儿子编号, v 存节点坐标 Max 和 Min 维护当前节点管辖区间的大小, val 存当前点的权值
- int cnt,mlt,sum,len;//cnt 加标记, mlt 乘标记, sum 区间和, len 区间长度
- bool operator<(const hahaha &y)const{
- return v[T]<y.v[T];// 方便寻找中位数
- }
- }tree[50010];
2, 建树
如图, 可以看出, kdtree 是以一位一位顺次分割的方式建树的,
每次寻找区间中的中位数点, 沿当前维度进行分割, 如本图为先竖着再横着分割
第一次先找到横向的中位数, 竖着分割一次 (已用红色标出), 在递归左右子树, 找竖着的中位数, 横向分割, 再往下依次递归
以下建树部分代码:
- inline void updata(int p){// 很显然的更新
- tree[p].Min[0]=min(tree[p].v[0],min(tree[ls(p)].Min[0],tree[rs(p)].Min[0]));//x 坐标的最小值
- tree[p].Min[1]=min(tree[p].v[1],min(tree[ls(p)].Min[1],tree[rs(p)].Min[1]));//y 坐标的最小值
- tree[p].Max[0]=max(tree[p].v[0],max(tree[ls(p)].Max[0],tree[rs(p)].Max[0]));//x 坐标的最大值
- tree[p].Max[1]=max(tree[p].v[1],max(tree[ls(p)].Max[1],tree[rs(p)].Max[1]));//y 坐标的最大值
- }
- inline int build_tree(int l,int r,int tp){//l,r 为区间, tp 为区间维度
- T=tp;//T 也是区间维度, 用于查找中位数
- int mid=((l+r)>>1),p=mid;
- nth_element(tree+l,tree+mid,tree+r+1);// 这是个查找中位数的神奇函数
- tree[p].tp=tp;
- tree[p].mlt=1;
- tree[p].len=r-l+1;// 更新节点信息
- if(l<mid)
- ls(p)=build_tree(l,mid-1,tp^1);// 其实这个地方严谨来说应该是 (tp+1)%2, 因为维度是顺次遍历, 假如说有 5 维, 那就是按照 0,1,2,3,4,0,1,2... 这样的顺序遍历.
- // 注意, 这里不是像线段树一样 l,mid, 而是 l,mid-1, 因为左区间不包括这个点本身
- // 之所以这样写是为了卡常
- if(r>mid)
- rs(p)=build_tree(mid+1,r,tp^1);
- updata(p);// 再次更新节点信息
- return p;
- }
3, 插入操作
来源: http://www.bubuko.com/infodetail-2942261.html