Tag-线段树

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2021-01-15 20:44:17 |  0 Comments  |  线段树

Codeforces Educational Round 102 D.Program 线段树合并

题目大意

给出一个字符串序列,字符串仅由-和+组成,一开始有个初始的值x为0,-表示x = x-1,+表示x = x+1。

每次询问给出一个l和r,表示忽视[l,r]区间内的字符串,剩下的操作进行执行,求问x在操作过程中不同的值的个数。

题解

一开始看成区间内不同数的个数了,十分钟打完板子才发现不对。

虽然不是区间内不同数的个数,但是也是一道线段树的题目,且看下面的分析。

首先我们注意到,数x每次无论变大还是变小,每次变化的绝对值一定为1。这样我们就能够用x到达的最大值mx减去x的最小值mi,之后加上1,即为最终的答案。

于是我们只需要维护某一段区间操作使x能够变到的最大值和最小值分别是多少。

但是这样会出现一个问题,区间合并的时候应该怎么做。因为左侧区间得出的最终值一定会影响右侧区间的结果,所以这给我们的合并造成了一定的麻烦的影响。

但是影响是能解决的,因为产生影响的只有区间操作产生的对于这个区间的x最终结果的影响,所以我们只需要记录一下区间操作对x的最终结果的影响就好了。

这样我们就需要记录以下三个参数:

struct tree{
    int l,r,rval,mx,mi;
    tree operator + (const tree &x)const{
        tree res;
        res.mx = max(mx,rval + x.mx);
        res.mi = min(mi,rval + x.mi);
        res.rval = rval + x.rval;
        return res;
    }
    void init(){
        mx = 0;
        mi = INF;
        rval = 0;
    }
}tr[maxn<<2];

重载的operator +,就是区间的合并操作。

然后我们用线段树求解即可,具体求解方法就是,分别求出忽视的区间的左边和右边的操作区间的影响(struct结构),然后进行合并即可。

注意最小值小于0或者最大值大于0的情况,需要给答案+1,因为一开始x就是0。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int t
 2020-03-04 13:04:20 |  0 Comments  |  点分治 线段树

CodeForces 1303G. Sum of Prefix Sums 点分治+李超线段树

题目大意

定义一种叫做前缀数组和的东西sum_i为某个数组的前缀和数组的前i项之和。

现在给定一个树,树上每个节点有权值,树上一条有向路径的权值定义为从起点u到终点v上的所有数字组成的前缀数组和。

求问这种路径权值的最大值是多少。

题解

此题解为搬运CodeForces官方题解,为其中文翻译版本。(严正声明,可能中间会加一些个人的理解,代码的话个人的代码感觉还不如官方的好看所以就放官方的题解代码了)

首先确认这是一个树上路径问题,针对树上路径问题,一般可用的方法就是树分治和树链剖分。

考虑到这道题的路径权值的定义,我们并不能用树链剖分的传统的LCA和线段树的方法来进行计算,我们大概需要用搜索算法才能确定一个路径的权值和长度。

但是问题是,路径总数实在太多了,我们是不可能把所有路径都找出来算一遍的。所以我们考虑采用点分治,看看如何去减少对路径的统计。

考虑使用树分治,这里使用点分治更为方便(当然我也不会边分治),因为下面的思路是依靠点分治经过树的重心的路径这一思路展开的。

我们考虑一个树,经过重心的一个路径u->rt->v,我们分成u->rt和rt前往v的路径的下面一个点x->v两条路径来看。

假设路径u->rt的路径权值为为presum、路径上所有点的值的和为precnt,路径x->v的路径的路径权值为precalc、长度为prelen。

那么u->v的路径的路径权值为:

sum = precnt*prelen + presum + precalc

这是一个一次函数的形式,可以看作是一个直线在某点处的取值问题。

具体而言可以看作一条斜率为prelen,参数为precalc的直线在x = precnt处的取值(最后再加上一个presum)

那么对于前半部分路径对后半部分路径进行组合结果计算的问题就转化成了求后半部分的路径代表的多个直线在某点处的取值的最大值问题(最高点)。

但是用什么来计算呢?暴力肯定行不通的。

这里介绍李超线段树。李超线段树的用途是,维护区间内最高的线段。其思想是线段树的每个节点保存在当前区间中心点mid处最高的线段。每当加入一条线段时,先检测当前区间中心点mid处这条线段的高度与原来的线段相比,然后更低的线段向其左/右孩子更新。李超线段树可以查询在某点处最高的高度为多少。具体实现可以看代码。

于是我们通过点分治和李超线段树可以成功地把此题的复杂度降低到O(nlog2n),并且成功计算出

 2020-02-24 15:52:01 |  0 Comments  |  线段树

CodeForces 1313.C2 Skyscrapers(hard version) nlogn线段树做法

 题目大意

给定一个序列a,要求你每个元素都选出不超过ai的值,使得选出的元素序列满足不严格上凸(上凸、非严格单调皆可),且总和最大,求问每个位置上选出的元素是多少。

题解

此题有一个暴力的easy version版本,只需要枚举每个位置为最大值点位置pos(也就是该点处选择的元素大小为apos)暴力计算即可。

但是当数据量变大到5*105数量级时,我们没有办法枚举位置暴力计算。

但是可以注意到,枚举每个位置为最大值点位置pos这一步仍然是不可避免地,这是解题的核心,于是很容易想到,我们需要在较短时间内算出当每个位置为最大值点位置时,所选出的最优序列的元素大小总和。我们不能用暴力的版本每一次枚举都用O(n)的时间复杂度来算。

我们考虑用一种类似于前缀和和后缀和的形式来计算上述提到的我们需要计算的。前缀和和后缀和相加减去此位置本身所得的值,即在当前位置为最大值点位置时,所选出的最优序列的元素总和的大小。最优前缀和与最优后缀和的计算模式大致相同,直接来看最优前缀和pre的计算方法吧。

假设当前枚举到的位置为pos(pos>1),考虑两种情况:

1.apos>=apos-1,这时选取当前位置为最大值点时,不会对pos-1为最大值点时的最优前缀和的值产生影响,直接转移:pre[pos] = pre[pos-1];

2.apos<apos-1,这时选取当前位置为最大值点时,就不能用pos-1为最大值点时的最优前缀和的值来进行转移,因为这时pos-1位置不能选取其最大值了。这时候需要考虑我们不会对哪个位置之前的选值有影响,很明显是pos位置前第一个小于等于apos的元素所在的位置。

最优后缀和也类似考虑。

在第一种情况下,我们无需考虑什么东西,可以直接转移。重点在第二种情况,如何寻找pos之前第一个小于等于apos的元素所在的位置,这个操作的复杂度会影响到我们整体的算法复杂度。

据说有可以把这个操作整体复杂度做到O(1)的做法,但是这里并没有想到,于是选择nlogn的线段树做法。

首先对数组离散化,对离散化后的权值建一棵线段树,线段树节点上的值为其子树中元素的最大值,元素表示的是当前节点代表的区间的各个离散化后的值中出现的最晚的位置(最大)是哪个位置。

从开始向后逐个计算。

如果在第一种情况,直接转移,并将当前的位置pos更新到到线段树对应着当前位置元素的离散化后的值的权值叶节点。

如果在第二种情况,假设当前

 2019-08-29 22:08:21 |  0 Comments  |  线段树

2018 ICPC 徐州赛站网络赛 H Ryuji doesn't want to study 线段树

题目大意

给定一个序列,有两个操作:

1.询问l---r之间所有数按题目中格式公式的计算求和。

2.更改序列某个位置的值。

题解

其实这题还是蛮简单的……我零基础的队友30s就像出来了(比我快了一些)

这题直接维护区间和是不行的,我们看到询问的操作中的公式跟数的位置和询问区间长度都有关系。

那么我们现在要想的就是如何让区间和与数的位置变成无关的式子。

注意到对于位置 i,有n - i + 1 - n - r,即为我们要求的区间中 位置 i的数字对应的位置系数。

所以我们可以用线段树维护两个值,一个表示 a[i]*(n-i+1)的和,另一个表示a[i]的和。

询问的时候用前一个值对应的区间询问减去后一个值对应的区间询问的(n-r)倍就是我们需要询问的东西了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
struct tree{
	ll sum1,sum2;
	int l,r;
}tr[maxn<<2];
ll a[maxn];
int n,q;
void push_up(int now){
	tr[now].sum1 = tr[now<<1].sum1 + tr[now<<1|1].sum1;
	tr[now].sum2 = tr[now<<1].sum2 + tr[now<<1|1].sum2;
	return;
}
void build(int now,int l,int r){
	tr[now].l = l;
	tr[now].r = r;
	tr[now].sum1 = tr[now].sum2 = 0;
	if(l == r){
		tr[now].sum1 = a[l];
		tr[now].sum2 = a[l] * (n - l + 1);
		return;
	}
	int mid = (l + r) >> 1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	push_up(now);
	return;
}
void update(int now,int pos){
	if(tr[now].l == tr[now].r){
		tr[now].sum1 = a[pos];
		t
 2019-08-27 15:38:01 |  0 Comments  |  线段树

2018-2019 ACM-ICPC, Asia Shenyang Regional Contest E.The Kouga Ninja Scrolls 曼哈顿距离转换契比雪夫距离 + 线段树单点修改

题目大意

有n个人,他们分别位于(x,y),属于家族c。

现在有三种操作:

1.编号为k的人位置变换到(x+xk,y+yk)。

2.编号为k的人转投到家族c。

3.查询编号区间l----r之间的所有人中两个最远的不同家族的人之间的曼哈顿距离是多少。

题解

如果会曼哈顿距离转化为契比雪夫距离的话,这题思路并不难,可能就是写起来麻烦,极度锻炼思维和代码能力的一道线段树题目。

首先我们看一下曼哈顿距离去掉绝对值之后,一共只有四种情况:

1.x - x' + y - y'

2.x - x' + y' - y

3.x' - x + y - y'

4.x' - x + y' - y;

根据这四种情况,我们变换坐标(x,y)---->(x+y,x-y),从而把横纵坐标分离开计算距离,两个维度上的坐标是分别独立的,取最大值就是上面所说的契比雪夫距离。

然后我们维护的就是一个区间的x+y,x-y的最大、次大、最小、次小。注意:维护的时候最大、次大不能来自同一个家族,最小和次小同理。

查询的时候,我们把区间l---r之间的八个值全部取出,对于同类的(分为x+y和x-y两类值),列出所有的大值减去小值的情况,取所有结果的最大值即可。(注意如果大值和小值来自同一家族,那么这样是不能取的)

前两个修改操作,其实也就是个单点修改,没什么好说的,主要就是push_up函数细节多一(hen)些(duo),需要考虑的东西多一(hen)些(duo)

还是不多说废话了,直接上代码吧(354行啊……)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	ll val;
	int id;
	bool operator > (const node &b) const{
		return this->val > b.val;
	}
	bool operator < (const node &b) const{
		return this->val < b.val;
	}
	bool operator == (const node &b) const{
		return this->val == b.val && this->id == b.id;
	}
};
const ll INF = 1e17;
const int maxn = 2
 2019-08-08 13:50:48 |  0 Comments  |  线段树

2019 Multi-University Training Contest 6 1005 Snowy Smile 线段树维护最大子段和

题目大意

平面直角坐标系上有n个点,每个点有wi的价值,你可以选出一个矩形,获得矩形内部和边界上所有点的价值总和,求问最大的价值总和是多少。

题解

一开始一看,这题简单啊,直接离散化上二维前缀和好了。

然后写着写着发现不对劲,二维前缀和枚举是O(n^4)的。。。

然后后面想到了其实也就是离散化后维护最大子矩阵和,大概是要用二维线段树维护的……不过这个代码难度和复杂度就……

最后是队友给了思路:把问题通过一系列手法降维处理,把最大子段和转化为最大子区间和,这样就可以用一维的普通线段树去维护了。

首先还是要离散化,然后对于所有点按离散化后的x坐标从小到大排序。

然后我们枚举一个左侧的边界作为起始,枚举右侧边界作为终止,建立一棵投影到y轴上的线段树,把我们枚举的两个边界及其中间的所有点全部投影到y轴,并加入线段树进行单点修改,维护线段树区间最大子段和,这样我们枚举的两个边界中所维护的线段树的最大子段和就是以这两条边为边界的最大子矩阵和。

由于点数比较少,所以每枚举一次左侧边界后面的操作都是复杂度O(nlogn)的。所以对于每一个case,我们这个解决方案的总复杂度就是O(n2logn)的

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans = 0;
int T;
int n;
const int maxn = 2e5+5;
struct point{
    int x,y;
    ll w;
}p[maxn];
int xx[maxn],yy[maxn];
int tot1,tot2;
struct tree{
    int l,r;
    ll sum,mxl,mxr,mxs;
}tr[maxn<<2];
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        
 2019-07-04 14:41:30 |  0 Comments  |  线段树 DP BFS

BZOJ 1999 树网的核[数据加强版] 树的直径+线段树

题解

此题原本是NOIP提高组一道压轴,这一改数据感觉可以放省选赛或者CCPC难题里面什么的了

鬼知道为什么我当初做这道题会YY出线段树做法,现在想想我自己都佩服我自己。

嘛写这篇算是权当复习一下思路了。

题目告诉我们最小偏心距是什么了……我们要求的就是选定一个长度不超过s的核(在直径上,也可以是点也可以是边)使得离这个核最远的点离这个核 的距离最小。

首先求直径是很好求的,两遍BFS就搞定了。

但是直径可能会有很多条,那我们就对每一条都要计算。

对于每一条直径,我们的答案一定是由两类值的最大值来组成:

1.非此直径上的点到当前选定的核的距离的最大值。

2.直径的两个端点到当前选定的核的距离的最大值。

我们考虑用两个指针(two-pointers)的思想,不断的在直径上移动我们选定的核的两端(保证长度不超过s),这样可以保证线性查询,而不是暴力枚举带来的平方复杂度的查询。

距离直径的两个端点的值很好求,只需要在移动指针的时候不断地修改就可以了。

至于非此直径上的点,我们可以预处理他们到每一个此直径上的点的距离的最大值,然后再不断移动核的两端的时候,我们发现,这其实就是求当前核所涵盖的区间上的点的最远距离的最大值,这个区间问题我们可以用线段树(或者树状数组)进行查询,这样就可以logn的复杂度内查询了。

对于每一条直径我们都这么操作来算出一个答案,最终取所有答案的最小值就是最小偏心距了。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
int get_num() {
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if (c == '-')
        flag = true;
    else num = c - '0';
    while (isd
 2019-03-12 17:13:37 |  0 Comments  |  线段树 扫描线

hdu 1542 Atlantis 扫描线:矩形面积并


题目大意

给出矩形的左下端点和右上端点的坐标,求所有的矩形的面积的并。


题解

求矩形面积并是扫描线的基础经典问题。这篇blog是借助这个来介绍初步入门扫描线。

扫描线,顾名思义,就是一条上下扫描或者左右扫描的虚拟的自主创造的线。

在扫描线扫描到一条线段的时候,就进行操作。而这种操作常常是利用线段树这种数据结构来进行存储的。

在矩形面积的并这一个问题中,我们可以这样去把要计算的总的面积分为这样几个部分来看:

(图来自于别人的博客,实在是不想自己画图了QAQ)

我们可以看到,这个图就是按照扫描线来分区计算面积的。

我们每一次找到一条扫描线,就要维护当前在这条扫描线上(当然这里扫描线是向上扫的)所有的线段的覆盖总长(覆盖部分不再重复计算)。

然后我们用两条扫描线的高度差去乘前一条扫面先上的所有线段的覆盖总长,就是这两条扫描线与矩形围成的面积并。

对于扫描线的顺序,只需要把矩形的上下边去离散化排序以下就可以了。

于是我们剩下的任务就是维护当前扫描线上的线段覆盖总长。

由于x坐标可能会很大,我们一样要对x进行离散化,并且记录离散化后的元素对应的离散化前的元素。

然后我们可以类比前缀和的方式:

对于每一个矩形的下边,我们设这里的标记为+1,对于每一个矩形的上边,我们设这里的标记为-1

这里的标记就可以使用线段树来维护了(但是这里的标记并不需要下放,也不需要向上更新,这里的标记是用于记录这段区间线段是否被覆盖的)。

于是我们在线段树中维护两个变量,一个表示这段区间表示的线段是否被完全覆盖,另一个表示这段区间被覆盖的线段的总长。

在求被覆盖线段总长时,要分两种情况进行讨论:

1.当前区间表示的线段被完全覆盖:区间被覆盖的线段总长即为这段区间表示的线段总长。

2.当前区间表示的线段未被完全覆盖:当前区间被覆盖的线段的总长=其左区间被覆盖的线段的总长+其右区间被覆盖的线段的总长。

我们是一边更新一边统计答案,统计答案只需要每次答案加上总区间被覆盖的线段总长×两条扫描线之间的高度差。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct node
{
    double x1, x2, y1, y2; int id;
    node(double X1 = 0, double Y1 = 0, double X2 = 0, do
 2018-12-26 11:18:55 |  0 Comments  |  线段树

Codeforces Round#528 div2 F. Rock-Paper-Scissors Champion

Codeforces Round#528 div2

F. Rock-Paper-Scissors Champion

time limit:per test 2 seconds
memory limit:per test 256 megabytes
input:standard input
output:standard output

n players are going to play a rock-paper-scissors tournament. As you probably know, in a one-on-one match of rock-paper-scissors, two players choose their shapes independently. The outcome is then determined depending on the chosen shapes: "paper" beats "rock", "rock" beats "scissors", "scissors" beat "paper", and two equal shapes result in a draw.

At the start of the tournament all players will stand in a row, with their numbers increasing from 1 for the leftmost player, to n for the rightmost player. Each player has a pre-chosen shape that they will use in every game throughout the tournament. Here's how the tournament is conducted:

1.If there is only one player left, he is declared the champion.
2.Otherwise, two adjacent players in the row are chosen arbitrarily, and they play the next match. The losing player is eliminated fr

 2017-04-06 00:00:14 |  0 Comments  |  splay 线段树 树套树

BZOJ 3196 二逼平衡树

引言

好久没写题解了,正好不怎么想写代码,还是来发波题解吧。

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围:n,m<=50000
2.序列中每个数的数据范围:[0,1e8]
3.虽然原题没有,但事实上5操作的k可能为负数

题解

这是一道线段树套平衡树(就是每个线段树节点里面都存着一颗平衡树)的裸题。。。
用线段树维护下标区间,然后把平衡树节点套到线段树节点里面,注意此处的平衡树节点维护的是权值的大小。 修改操作可以转化成为找到当前这个数对应的区间,在splay里面删掉这个数,然后插入修改成的那个数就OK。
然后就是注意排名的话是比当前小的数的个数+1。
要求区间内排名为k的数的时候,我们就得注意了。因为我们是线段树套平衡树,所以说查询区间的时候,查询区间会分布在很多个线段树节点上。所以这样的话,这个操作就只能是二分答案,然后去看答案的排名是不是在这个查询区间中排k。(注意因为有重复的数,所以要求最大排名和最小排名,看k是不是在这个范围内)。
最后要注意的就是……为了保证空间,一律用内存池写。(可能我的代码里面的指针对某些读者不太友善。。。)

代码

#includ
Title - Artist
0:00