19-大数据一班-杨文冠

分类

学习(23) 未归档(1) 练习(1) 题解(137)

/ 注册

TA的专栏 96篇文章 0人订阅

[kuangbin带我飞]专题十五数位DP

11篇文章 891人学习

[kuangbin带我飞]专题十四数论基础

2篇文章 648人学习

8篇文章 749人学习

动态规划入门

7篇文章 923人学习

1篇文章 669人学习

二分图匹配

2篇文章 653人学习

[kuangbin带我飞]专题七线段树

8篇文章 797人学习

3篇文章 744人学习

线段树进阶

3篇文章 660人学习

codeforces补题

32篇文章 875人学习

莫比乌斯反演

6篇文章 577人学习

网络流初步

4篇文章 762人学习

6篇文章 722人学习

2021杭电多校

3篇文章 783人学习

全部文章（共21篇）

Assign the task 来自专栏

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

线段树

2020-12-07

1 576

Tunnel Warfare 来自专栏

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

线段树

2020-12-07

2 628

Can you answer these queries? 来自专栏

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

线段树

2020-12-07

1 614

Balanced Lineup 来自专栏

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

线段树

2020-12-07

2 654

Count the Colors 来自专栏

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

线段树

2020-12-07

2 588

Just a Hook 来自专栏

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

线段树

2020-12-07

1 579

Mayor's posters 来自专栏

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

线段树离散化

2020-12-07

1 617

树链剖分

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 628

线段树中等题

hdu 1540 题意：1-n个地道，m个次操作，D代表摧毁第i个地道，Q代表查询包含第i个地道的最大连续地道数目，并输出。R代表修复最近摧毁的那个地道。思路：（线段树&区间合并&最大连续区间）充分利用了线段树相邻结点之间的区间都是连续的性质，x[rt]表示这个区间从左边起的连续区...

线段树

2020-04-26

1 574

线段树简单题

hdu 1166 思路：点修改+区间求和，数组实现线段树。提交hdu时注意把模板的update改成add（改别的或不改都行，一提交就网页丢失就改这里）。可用树状数组实现。 Code： #include<bits/stdc++.h> #define js ios::sync_with...

线段树二维线段树

2020-04-24

4 615