shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

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

蒲公英来自专栏

嗯,今天也是我第一次学分块,所以更下题解和分块.辛格大佬说这个题就是莫队的板子分块一般是将一个区间分成sqrt(n)块,然后对于进行处理,比如说今天我们这个题目求区间众数.我们处理出两个数组,一个f[i][j]表示第i块到第j块的众数是多少,另外一个s[i][j]表示前i块中j出现次数.处理完这两个...

分块

2020-07-21

2 652

窗内的星星来自专栏

题目意思很简单,就是你拿一个给定大小的矩形去圈星星,要求你圈到星星最大的亮度是?这题可以直接二维曲尺解决,因为数据不是很强,但是我们还是讲讲线段树如何解决.还是和上题一样用线段树的扫描线解决,我们把数据做成给定坐标和价值做成扫描线,扫描完了就抛弃,把线段树存节点存成线段,然后我们用add做延迟标记,...

线段树离散化

2020-07-20

2 683

亚特兰蒂斯来自专栏

讲这题之前,我先介绍下线段树扫描线,可能昨晚睡眠不足,导致今天连递归都没看懂,服了.扫描线只是利用线段树思路解决问题的一种方式而已.就拿本题来说要你计算图形面积.这是题目的样例,讲下重点和我对这题的理解，虽然不是很透彻..首先我们可以把x轴按x的值切分，我们要用y轴值进行快速更新.首先这个更新可以用...

线段树离散化

2020-07-20

2 714

区间最大公约数来自专栏

思路:求l~r的a数组的gcd,等价于求al与各差分ai的gcd.证明:辗转相除法.详细的讲下吧.假如d是al,al+1...ar的gcd,那么它一定是al,al+1-al,al+2-al+1...的公约数.同理后面可得前面.那么原题就可以用线段树维护差分数组的gcd即可.代码如下: #includ...

线段树

2020-07-19

2 650

你能回答这些问题吗来自专栏

怀着激动的心情,把大家都会的线段树学了一下.听说线段树博大精深,所以决定把进阶指南暂时放一放,学完这个把kuangbin的线段树专题也做了.emm.今天先更个不带lazy的线段树,虽然我觉得带不带lazy其实都差不多.但是,第一次写线段树,好激动哎...首先介绍线段树的几个操作(不带lazy).1....

线段树

2020-07-19

3 670

谜一样的牛来自专栏

记住树状数组的作用,快速维护前缀和.下面说下这题怎么做,首先得明确一点必须逆推.最后一个数是k,那么它就是k+1小的数.且是排列,所以顺序是一定的.下面就是说下怎么用树状数组+二分进行找到第k+1小且删除第k+1小了.其实你用树状数组只要记得它是用来快速求前缀和的就行了.如此,我们就可以将每个位子都...

树状数组

2020-07-16

4 658

一个简单的整数问题2 来自专栏

树状数组的第三种用法,区间修改,区间查询.仔细讲下.假设我们要求a[l-r]里面的和,而我们知道a[l]=d[1-l]. 用代码表示a[l~r]的和就是： int sum=0; for(int i=l;i<=r;i++) { for(int j=1;j<=i;j++) {...

树状数组

2020-07-16

1 684

一个简单的整数问题来自专栏

这个是树状数组的多点修改,单点查询....三个题目连着把树状数组的操作演示完了...我知道的 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; ll d[N],su...

树状数组

2020-07-16

3 591

楼兰图腾来自专栏

这个题貌似就是让你找逆序对?emm...没啥好说的. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; ll sum[N];//建树 ll a[N],n; ll G...

树状数组

2020-07-16

1 591

食物链来自专栏

建图种类并查集即可 #include <bits/stdc++.h> using namespace std; const int N=5e4+5; int fa[N],d[N]; int ask(int x) { if(fa[x]!=x) { int r...

并查集

2020-07-15

1 666