威风镰鼬

分类

题解(153)

/ 注册

全部文章（共10篇）

题解 | #不存在的树#

思路就是树链剖分+线段树的板子，但是因为眼疾看少了”多组数据“导致一直WA（哭了不会的可以看一下我的这篇博客：https://editor.csdn.net/md/?articleId=121182009 代码 #include<bits/stdc++.h> #define inf ...

树链剖分线段树

2021-11-24

1 453

题解 | #树的距离#

首先感谢TheOnlyMan为我们带来主席树的精彩讲解，但说到底不管在不在线，本题只用普通的线段树就够了。时间空间都更优秀。AC结果：287ms 42300KB 思路先跑一个dfs（因为最近写惯了所以树链剖分没改回来），然后把树拍平去建线段树。我们知道以x为根的子树表示的范围就是[dfn[x...

C++ 树链剖分线段树主席树

2021-11-17

1 506

题解 | #[JSOI2008]最大数MAXNUMBER#

思路改一下线段树的模板就行了。每次添加数的时候len+1，查询区间是[len-L+1,len]。代码 #include <bits/stdc++.h> #define int long long using namespace std; typedef long long ll; c...

线段树

2021-09-17

1 419

题解 | #Atlantis#

思路这道题是扫描线线段树的板子题，具体的处理方法：(1)每个矩形的上下边加入扫描线并标记，下边标记为1，上边标记为-1(2)让扫描线从从低到高排序，而矩形的左右边从小到大排序(3)考虑数据范围，我们进行离散化处理(3)建立线段树，那么区间可表示为区域的y1,y2，以及长度。(4)遍历所有相邻左右边...

线段树扫描线数据结构

2021-08-17

2 439

题解 | #Mayor's posters#

思路典型的区间染色问题。离散化区间端点（注意非连续区间中间要加点隔开），就可以建线段树了。倒序每一次询问，查看该区间是否被覆盖，如果没有就ans++,然后顺便把区间覆盖掉。代码 #include<iostream> #include<vector> #include<...

线段树数据结构

2021-08-17

1 487

题解 | #A Simple Problem with Integers#

思路线段树板子。代码 #include<iostream> #define pushup(x) (tree[x]=tree[x<<1]+tree[x<<1|1]) #define MID int mid=(start+end)>>1 using n...

数据结构线段树

2021-08-16

1 535

题解 | #数据结构#

思路要维护区间和以及平方和两个线段树，同时支持加法和乘法操作。前面基本套模板就行了，那么我们重点是pushdown怎么写。（这个板子是参照oi-wiki先打出lazy的pushdown的，已经能支持加法维护区间和了）我们可以用上述式子Pushdown区间平方和。考虑乘法：一开始我们建立cheng...

线段树

2021-06-23

1 678

题解 | #情人节的电灯泡#

思路把n*n的矩阵摊平成一条直线，就可以用线段树的方法解决啦！n<1000，所以展成直线就是1e6的单点修改+区间求和。个人码风问题我全开ll了，第一发因为update写错了爆零（我太菜了）代码 #include<stdio.h> #include<iostream>...

线段树

2021-06-15

2 526

题解 | #Tree Recovery#

思路线段树裸题，区间修改+区间查询，板子如下。需要注意的一个坑点就是读命令的时候不要漏掉换行符。（个人码风习惯把int改成ll，各位还是要注意别爆了）代码 #include<bits/stdc++.h> #define int ll using namespace std; type...

线段树

2021-06-12

2 510

题解 | #Big Water Problem#

思路看数据范围1e5，暴力求和会被查询卡掉，用前缀和会被单点修改卡掉，所以我们要用到线段树。线段树（查询+单点修改），背板代码如下。我的码风把int定义成ll了，希望你们看的习惯。代码 #include<bits/stdc++.h> #define int ll using name...

线段树

2021-06-12

2 654