米游社 · 崩坏:因缘精灵

4.3.1 线段树(1)

来自版块: 酒馆
2
12
2
文章发表:05-03 最后编辑:08-07
来自合集: 算法提高课

265.最大数

题目:

给定一个正整数数列a1, a2, ……,an,每一个数都在0~p-1之间。可以对这列数进行两种操作:

1.添加操作:向序列后添加一个数,序列长度变成n+1;

2.询问操作:询问这个序列中最后L个数中最大的数是多少。

程序运行的最开始,整数序列为空。

写一个程序,读入操作的序列,并输出询问操作的答案。

输入格式

第一行有两个正整数m, p,意义如题目描述;接下来m行,每一行表示一个操作。

如果该行的内容是Q L,则表示这个操作是询问序列中最后L个数的最大数是多少;

如果是 A t,则表示向序列后面加一个数,加入的数是(t+a) mod p。其中,t是输入的参数,a是在这个添加操作之前最后一个询问操作的答案(如果之前没有询问操作,则a=0)。

第一个操作一定是添加操作。对于询问操作,L>0且不超过当前序列的长度。

输出格式

对于每一个询问操作,输出一行。该行只有一个数,即序列中最后L个数的最大数。

数据范围

1≤m≤2×10⁵

1≤p≤2×10⁹

0≤t<p

思路:

1.线段树有Push up和Push down两个操作。Push up就是由子结点求父结点的信息。比如sum=l.sum+r.sum。Push down就是把父结点的修改信息递归到子结点。被称为懒标记或延迟标记。我们本节只讲Push up。

2.最简单的线段树有5种操作,①pushup()。②pushdown()。③build(),将一段区间初始化成线段树。④modify(),修改单点或者修改一个区间,一般修改一个区间需要用到懒标记,本节不讲。⑤query(),查询某一段的信息。

3.线段树是一个二叉树。如下图所示比如我们要维护1-10,那么根就表示1-10,那么根结点的子结点就是[1,5]和[6,10],mid为(l+r)/2下取整。[1,5]又会分为[1,3]和[4,5]。[1,3]分为[1,2]和[3]。[1,2]会分为[1]和[2]……以此类推。那么整个树除了最后一层就是一个满二叉树。因此我们就可以用一维数组去存储整棵树。假设一个点是x,那么它的父结点就是x/2下取整,即x>>1,左儿子为2x,即x<<1,右儿子是2x+1,即x<<1|1。


4.一般来说,线段树开空间为4n。去掉最后一层,假设剩余的倒数第一层点数为n,那么它这一层的上面就是n-1个点,而去掉的那一层最多2n个点,所以最坏是4n-1个点。

5.对于build函数

build(int u,int L,int R)

{

tr[n].L=L,tr[n].R=R;

if(L==R) return; //叶子结点直接返回

int mid = L+R>>1;

build(u<<1,L,mid),build(u<<1|1,mid+1,R);

pushup(u);

}

6.对于查询函数,比如我们要找某个区间里的最大值,我们让线段树的每个结点存当前区间的最大值。查询一般会有下面几种情况。我们用[L,R]表示当前查询的区间,[TL,TR]表示数中结点查询范围。

①如果[L,R]⊃[TL,TR]。那么我们可以直接返回,不用递归了。

②如果[L,R]∩[TL,TR]≠∅,如果和左边有交集就递归到左边,右边有交集就递归到右边,可以同时两边一起递归。

不存在[L,R]∩[TL,TR]=∅的情况。最开始的时候根节点是整个区间,此时一定有交集,而后我们每次递归都是会选择有交集的部分继续去做,所以一定是会有交集的。如下图

假设我们要搜索[5,9]这个范围,那么我们搜索的范围就是棕色圈所标记的圈。由图,我们可知在搜索的时候最多只会搜索两条链,其他分裂出来的点并不影响时间复杂度。每条链都是O(logn),所以整体是O(logn)。因为每个链最多可能有递归左边和递归右边,有两个链,所以最多有4logn个点。

7.序列最开始是空的,所以我们可以先把m个坑开好,每一次用一个变量n表示当前有几个位置被占据了。每次添加可以看成是在第n+1的位置加入我们的数字。本题第一个操作可以看成每次动态在一个位置修改一个数。第二个操作是动态问某一个区间内的最大值。

8.线段树定义

Node{

int l,r;

int v; //本题存的是区间最大值

}

此外,本题修改的时候是需要上一次询问的a,所以这是一个动态问题,不能用静态方法求解。

代码(c++):

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;

int m, p;

struct Node

{

int l, r;

int v; //区间[l, r]中的最大值

}tr[N * 4];

void pushup(int u) //由子节点的信息,来计算父节点的信息

{

tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);

}

void build(int u, int l, int r)

{

tr[u] = {l, r}; //左右端点

if (l == r) return; //如果是叶结点

int mid = l + r >> 1;

build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

}

int query(int u, int l, int r)

{

if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; // 树中节点,已经被完全包含在[l, r]中了

int mid = tr[u].l + tr[u].r >> 1;

int v = 0;

if (l <= mid) v = query(u << 1, l, r); //和左边有交集

if (r > mid) v = max(v, query(u << 1 | 1, l, r)); //这边是>,不是≥,因为我们的区间划分是[L,mid]和[mid+1,R]

return v;

}

void modify(int u, int x, int v) //u是当前递归到的线段树结点,x是目标结点

{

if (tr[u].l == x && tr[u].r == x) tr[u].v = v; //叶结点的情况

else

{

int mid = tr[u].l + tr[u].r >> 1;

if (x <= mid) modify(u << 1, x, v);

else modify(u << 1 | 1, x, v);

pushup(u); //递归完之后,一定要记得更新一下最大值信息,pushup一下

}

}

int main()

{

int n = 0, last = 0; //last代表a

scanf("%d%d", &m, &p);

build(1, 1, m); //第一个1代表根节点,区间为1-m

int x;

char op[2]; //读字符一般习惯用字符串读,可以过滤空白字符

while (m -- )

{

scanf("%s%d", op, &x);

if (*op == 'Q')

{

last = query(1, n - x + 1, n); //后x个数

printf("%d\n", last);

}

else

{

modify(1, n + 1, ((LL)last + x) % p);

n ++ ;

}

}

return 0;

}


266.你能回答这些问题吗

题目:

给定长度为N的数列A,以及M条指令,每条指令可能是以下两种之一:

1、"1 x y",查询区间[x,y]中的最大连续子段和,即


2、"2 x y",把A[x]改成y。

对于每个查询指令,输出一个整数表示答案。

输入格式

第一行两个整数N,M。第二行N个整数A[i]。

接下来M行每行3个整数k,x,y,k=1表示查询(此时如果x>y,请交换x,y),k=2表示修改。

输出格式

对于每个查询指令输出一个整数表示答案。每个答案占一行。

数据范围

N≤500000

M≤100000

思路:

1.单点修改不用pushdown,pushup即可。对于查询操作,查询区间内最大子段和。首先想想结点内部都要存什么。

struct Node

{

int L,R; //区间左右端点

int tmax; //最大连续子段和。我们来看一个条件足够与否只需要看是否能用左右儿子的该性质推出父亲结点。这里我们发现左右儿子的tmax推不出父结点的tmax,因为可能是横跨两个区间的。那我们还需要另外两个信息,第一个信息是以左边区间的右端点为结点的最大后缀和,第二个信息是右边区间的左端点为起点的最大前缀和。二者相加就是第三种情况。此外我们还缺少区间总和,因为我们在求父结点的最大前缀和最大后缀的时候会用到

int lmax; //最大前缀和

int rmax; //最大后缀和

int sum; //区间和

}

tmax=max{left_son.tmax,right_son.tmax,left_son.rmax+right_son.lmax}

代码(c++):

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 500010;

int n, m;

int w[N];

struct Node

{

int l, r;

int sum, lmax, rmax, tmax;

}tr[N * 4];

void pushup(Node &u, Node &l, Node &r)

{

u.sum = l.sum + r.sum;

u.lmax = max(l.lmax, l.sum + r.lmax);

u.rmax = max(r.rmax, r.sum + l.rmax);

u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);

}

void pushup(int u)

{

pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);

}

void build(int u, int l, int r)

{

if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]}; //当前区间只有一个数,所以全是w[r]

else

{

tr[u] = {l, r};

int mid = l + r >> 1;

build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

pushup(u);

}

}

void modify(int u, int x, int v)

{

if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};

else

{

int mid = tr[u].l + tr[u].r >> 1;

if (x <= mid) modify(u << 1, x, v);

else modify(u << 1 | 1, x, v);

pushup(u);

}

}

Node query(int u, int l, int r)

{

if (tr[u].l >= l && tr[u].r <= r) return tr[u];

else

{

int mid = tr[u].l + tr[u].r >> 1;

if (r <= mid) return query(u << 1, l, r);

else if (l > mid) return query(u << 1 | 1, l, r);

else

{

auto left = query(u << 1, l, r);

auto right = query(u << 1 | 1, l, r);

Node res;

pushup(res, left, right); //计算出新区间的信息

return res;

}

}

}

int main()

{

scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

build(1, 1, n);

int k, x, y;

while (m -- )

{

scanf("%d%d%d", &k, &x, &y);

if (k == 1)

{

if (x > y) swap(x, y);

printf("%d\n", query(1, x, y).tmax);

}

else modify(1, x, y);

}

return 0;

}


267.区间最大公约数

题目:

给定一个长度为N的数列A,以及M条指令,每条指令可能是以下两种之一:

1、“C I r d”,表示把A[l],A[l+1],...,A[r]都加上d。

2、“Q l r”,表示询问A[l],A[l+1],...,A[r]的最大公约数(GCD)。对于每个询问,输出一个整数表示答案。

输入格式

第一行两个整数N, M。第二行N个整数A[i]。

接下来M行表示M条指令,每条指令的格式如题目描述所示。

输出格式

对于每个询问,输出一个整数表示答案。每个答案占一行。

数据范围

N≤500000

M≤100000

思路:

1.操作一:区间[L,R]增加一个数。操作二:求区间内最大公约数。

这里求最大公约数我们只要维护一个最大公约数就够了,因为左边区间的最大公约数和右边区间的最大公约数再取一个最大公约数。这里对数进行修改后是无法得出修改后的最大公约数的,也就是a,b,c的最大公约数和a+x,b+x,c+x的最大公约数是没什么关系的。但是只修改一个数的话就很容易做了。那有没有什么方法能让对区间的修改变成单点的修改呢?可以用差分。这里我们先分析另外一点,(x,y,z)=(x,y-x,z-y)。其中(x,y,z)代表x,y,z三者的最大公约数。更普遍的(a₁,a₂,...,aₙ)=(a₁,a₂-a₁,...,aₙ-aₙ₋₁)。下面我们来证明其正确性。首先证明左边≤右边。假设左边等于d,是左边最大的公约数,那么因为a₁是d的倍数,a₂是d的倍数,所以可知a₂-a₁仍为d的倍数。同理,所以可推出d为右边的公约数,所以可知左边≤右边。下面来证明左边≥右边,这里同样假设右边是d,且为最大公约数。那么因为a₁是d的倍数并且a₂-a₁是d的倍数,那么a₂-a₁+a₁=a₂即是d的倍数。同理,我们可以推出d是左边的公约数。所以得到左边≥右边,所以推出左边=右边。所以(a₁,a₂,...,aₙ)=(a₁,a₂-a₁,...,aₙ-aₙ₋₁)成立。

2.那么对于求差分,我们让线段树里维护的是所有差分的值。那么对于求一个区间内的最大公约数,就是gcd(a[l],gcd(b[l+1]~b[R]))。其中b为a的差分数组。bi=ai - ai-1,和前面的结论等价。单点查询的话就是求差分数组的前缀和。这里我们求最大公约数和单点查询都是用差分数组来做的,所以可以同时维护这两个属性。

代码(c++):

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;

LL w[N];

struct Node

{

int l, r;

LL sum, d;

}tr[N * 4];

LL gcd(LL a, LL b)

{

return b ? gcd(b, a % b) : a;

}

void pushup(Node &u, Node &l, Node &r)

{

u.sum = l.sum + r.sum;

u.d = gcd(l.d, r.d);

}

void pushup(int u)

{

pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);

}

void build(int u, int l, int r)

{

if (l == r)

{

LL b = w[r] - w[r - 1];

tr[u] = {l, r, b, b};

}

else

{

tr[u].l = l, tr[u].r = r;

int mid = l + r >> 1;

build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

pushup(u);

}

}

void modify(int u, int x, LL v)

{

if (tr[u].l == x && tr[u].r == x)

{

LL b = tr[u].sum + v;

tr[u] = {x, x, b, b};

}

else

{

int mid = tr[u].l + tr[u].r >> 1;

if (x <= mid) modify(u << 1, x, v);

else modify(u << 1 | 1, x, v);

pushup(u);

}

}

Node query(int u, int l, int r)

{

if (tr[u].l >= l && tr[u].r <= r) return tr[u];

else

{

int mid = tr[u].l + tr[u].r >> 1;

if (r <= mid) return query(u << 1, l, r);

else if (l > mid) return query(u << 1 | 1, l, r);

else

{

auto left = query(u << 1, l, r);

auto right = query(u << 1 | 1, l, r);

Node res;

pushup(res, left, right);

return res;

}

}

}

int main()

{

scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);

build(1, 1, n);

int l, r;

LL d;

char op[2];

while (m -- )

{

scanf("%s%d%d", op, &l, &r);

if (*op == 'Q') //gcd(a[l],gcd(b[l+1]~b[R]))的具体实现

{

auto left = query(1, 1, l); //得到A[l]的和

Node right({0, 0, 0, 0});

if (l + 1 <= r) right = query(1, l + 1, r); //右半部分长度至少为1的情况下,看右半部分

printf("%lld\n", abs(gcd(left.sum, right.d))); //差分数组中的负号只是表示大小关系,不影响最大公约数的正负,答案需要加abs。此处为左边的数本身和右边的所有差分数组的元素的最大公约数再次取最大公约数

}

else

{

scanf("%lld", &d);

modify(1, l, d);

if (r + 1 <= n) modify(1, r + 1, -d); //不越界的情况下修改

}

}

return 0;

}

12
2
看帖是喜欢,评论才是真爱:
0 / 1000
  • 全部评论
  • 只看楼主
排序:最早
2
2
12
扫码下载
米游社App