威风镰鼬

题解

/ 注册

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

题解 | #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

题解 | #wyh的天鹅#

思路学艺不精，交splay结果WA了，还找不到问题。所以我还是用了vector写。保持vector是有序的，插入和删除的时候二分，复杂度很优。记得要清空vector。代码 #include<bits/stdc++.h> //#define int long long using na...

vector 平衡树数据结构

2021-08-03

1 699