19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

全部文章 / 题解（共18篇）

Assign the task 来自专栏

题意：一颗n个节点n-1条边的树，T X Y表示给节点x及其子树涂色，C X表示询问节点X的颜色（初始都是-1）思路：（不要漏写运算符了）vis标记入度大于等于1的点，未标记的点就是根结点。dfs序可以把子树映射到连续的区间上，维护每个节点的dfs序以及子树最后一个节点的dfs序。区间修改单点查询...

线段树

2020-12-07

1 577

Tunnel Warfare 来自专栏

题意：1-n个地道，m个次操作，D代表摧毁第i个地道，Q代表查询包含第i个地道的最大连续地道数目，并输出。R代表修复最近摧毁的那个地道。第二次写了，看到题目有大致的思路，但还是不知道具体怎么实现。思路：可以维护一个区间的左连续区间长度li[]，以及右连续区间长度ri[]。如果左孩子区间整个区间是...

线段树

2020-12-07

2 632

Can you answer these queries? 来自专栏

题意：给一个序列，有俩种操作，一种是求区间和，一种是将区间每个数开根号后向下取整（QQ浏览器翻译成了四舍五入，坑了我很久）。思路：因为是对区间内的每个数开根号，没有办法用延迟更新，但是取根号在6，7次就会到1，所以如果父节点的权值等于r-l+1就不用往下跟新了，因为这个区间里每个数都是1，这样修改...

线段树

2020-12-07

1 621

Balanced Lineup 来自专栏

题意：给一个数组，每次询问一个区间，输出区间内最大值和最小值的差。思路：维护一个区间最小值，一个区间最大值 Code： #include<algorithm> #include<cstring> #include<cstdio> #include<iost...

线段树

2020-12-07

2 659

Count the Colors 来自专栏

题意：n次操作，每次给出x1,x2,c，表示在区间[x1,x2]上涂上颜色c，如果能看到颜色i，就输出i并输出颜色i有几个不相交的区间。思路：对于线段而言，如果长度大于等于1，它的两端被别的颜色占了，那么这个颜色还是能看到的。但如果涂区间内的点，如果长度等于1，它的两端被别的颜色占了，那么这个颜色...

线段树

2020-12-07

2 591

Just a Hook 来自专栏

题意：屠夫的钩子有三种连起来，他可以改变某一段的钩子种类来改变钩子的长度m次。问m次后改变链子的长度。思路：这个算是区间赋值吧，在最后在输出整个区间的和，lazy标记和处理完孩子后更新当前节点一个不能少。因为是赋值，所以lazy标记不要去累加。 Code： #include<algorith...

线段树

2020-12-07

1 584

Mayor's posters 来自专栏

题意：输入t组数据，输入n代表有n块广告牌，按照顺序贴上去，输入区间，问贴完以后还有多少块广告牌可以看到（因为有的被完全覆盖了）。输入：2 4表示这块广告牌占了第2、3、4个格子。思路：这是占格子类型的题，Count the Colors是涂颜色的问题两者有点区别。可以理解为这题是涂[l,r]上的点...

线段树离散化

2020-12-07

1 622

树链剖分

poj3384 #include<bits/stdc++.h> using namespace std; const int maxn=1e5+7,maxm=2e5+7; typedef long long ll; inline ll read(){ ll s = 0, w =...

线段树树链剖分数据结构

2020-09-25

1 630