点分治 线段树    发布于 2020-03-04   540人围观   0条评论

题目大意

定义一种叫做前缀数组和的东西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   428人围观   0条评论

 题目大意

给定一个序列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   533人围观   0条评论

题目大意

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

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   446人围观   0条评论

题目大意

有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   331人围观   0条评论

题目大意

平面直角坐标系上有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 == '-')
        
查看更多
线段树 DP BFS    发布于 2019-07-04   292人围观   0条评论

题解

此题原本是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   382人围观   0条评论


题目大意

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


题解

求矩形面积并是扫描线的基础经典问题。这篇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   528人围观   0条评论

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

查看更多
splay 线段树 树套树    发布于 2017-04-06   210人围观   0条评论

引言

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

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
查看更多
整体二分 线段树    发布于 2017-01-15   215人围观   0条评论

Description

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M 接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3

Sample Output

1 2 1

HINT

【样例说明】第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3大的数是 1 。
N,M<=50000,N,M<=50000a<=b<=N1 操作中abs(c)<=N2操作中c<=Maxlongint

题解

二分:当遇到的操作是询问操作时,查询线段树里的当前区间,并将当前区间所包含的数的个数as与查询的第k大相比较,如果小于k,那么把当前询问分到左边去,并统计影响k-=as,反之,将它分到右边;当遇到的操作是加入操作时,把要加入的数和mid比较,如果大于mid,那么就把当前操作统计进去,而且当前操作会对右边产生影响,所以要分到右边去,虽然对左边也有影响,但在处理询问时已经处理,就不用考虑了。
数的统计:线段树维护,记录每个区间当前有多少个大于mid的数,“加入”操作里的“统计进去”即是更新当前区间的数的个数(注:不要把线段树的区间和上面把操作分到左右区间混淆,这是不相干的概念,上面分到左右只是为了维护整体二分的序列的有序性)
每次操作完,都要以区间序号为关键字重新排序。
细节:线段树维护时,要考虑线段树每一次二分时,之前的标记等都是不能再使用的,所以要重置,但因为数组过大,如果每一次memset,必然TLE。所以设一个标记数组,每次pushdown前,都要判断当前点的标记是否是1,若是1,把当前点置0,并把当前点的左右儿子重置。这样,每次二分重置时,只用重置根节点即可。
数据范围过大,可能超int。

代码

#include <iostream>
#includ
查看更多