讲这题之前,我先介绍下线段树扫描线,可能昨晚睡眠不足,导致今天连递归都没看懂,服了.扫描线只是利用线段树思路解决问题的一种方式而已.就拿本题来说要你计算图形面积.这是题目的样例,讲下重点和我对这题的理解，虽然不是很透彻..首先我们可以把x轴按x的值切分，我们要用y轴值进行快速更新.首先这个更新可以用线段树，存tr数组的话考虑4个变量l，r表示当前节点的左右区间，然后用cnt和len分别表示这个矩形在这个区域叠加了几次以及这个区域所占长度，显然因为y是浮点数，不适合我们直接建树，我们需要离散化一下.我们拿build把节点建树，然后我们modify进行更新，更新时候有个pushup操作.等会单独讲...

思路:求l~r的a数组的gcd,等价于求al与各差分ai的gcd.证明:辗转相除法.详细的讲下吧.假如d是al,al+1...ar的gcd,那么它一定是al,al+1-al,al+2-al+1...的公约数.同理后面可得前面.那么原题就可以用线段树维护差分数组的gcd即可.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+10; ll w[N],s[N]; struct node{ ll l,r,sum,d; }tr[N*4]; void pushup(...

怀着激动的心情,把大家都会的线段树学了一下.听说线段树博大精深,所以决定把进阶指南暂时放一放,学完这个把kuangbin的线段树专题也做了.emm.今天先更个不带lazy的线段树,虽然我觉得带不带lazy其实都差不多.但是,第一次写线段树,好激动哎...首先介绍线段树的几个操作(不带lazy).1.build 这个操作就是把已知信息转化为二叉搜索树,线段树就是一颗二叉搜索树,分治思想的体现.2.pushup 这个操作就是通过子节点信息更新父节点.3.modify 执行更新操作.4.query 执行查询操作.对于这个题目而言,线段树需要维护些什么信息呢?我们思考两段合并的最大连续子段和,就是能否...

记住树状数组的作用,快速维护前缀和.下面说下这题怎么做,首先得明确一点必须逆推.最后一个数是k,那么它就是k+1小的数.且是排列,所以顺序是一定的.下面就是说下怎么用树状数组+二分进行找到第k+1小且删除第k+1小了.其实你用树状数组只要记得它是用来快速求前缀和的就行了.如此,我们就可以将每个位子都设为1,然后删了就表示0.然后二分出k+1即可.代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],b[N],sum[N],n; int lowbit(int x) { retur...

树状数组的第三种用法,区间修改,区间查询.仔细讲下.假设我们要求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++) { sum+=a[j]; } } ()表示对1到n求和 n*a[1]+(n-1)*a[2]+...+a[n]=n*()*d[i]-()(d[i]*(i-1)).我们要这样想树状数组的功能是对1到n求和.代码如下: #include <bits/stdc++.h> using namespace std; ...

这个是树状数组的多点修改,单点查询....三个题目连着把树状数组的操作演示完了...我知道的 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; ll d[N],sum[N],a[N]; ll n; int lowbit(int x) { return x&(-x); } void insert(ll pos,ll val) { while(pos<=n) { sum[pos]+=val; pos+=lowbit(pos); } } ll quer...

这个题貌似就是让你找逆序对?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 Greater[N];//左边比它大的数. ll Less[N];//左边比它小的数. int lowbit(int x) { return x&(-x); } void insert(int pos,int val) { while(pos<=n) { sum[pos]+=val; p...

数据结构了,作为一个从来没有学过数据结构的萌新.认真的更下树状数组.什么是树状数组?就是利用二进制的存储方式进行的一个数据结构.线段树是二叉树进行存储,而树状数组是用lowbit进行存储.https://www.cnblogs.com/xenny/p/9739600.html 这博客不错,我也不说了~

建图种类并查集即可 #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 root=ask(fa[x]); d[x]+=d[fa[x]]; fa[x]=root; } return fa[x]; } int main() { for(int i=1;i<=N-5;i++) fa[i]=i; int n,T; cin>>n>>T; int res=0; while(T--) {...

各种找矛盾的题..下面用种比较好的算法写吧,不用扩展域,权值并查集.怎么权值查并集呢?首先和上个题目一样,用一个d[x]表示x到根节点的距离.假如距离为偶数就表示同一面.奇数就表示对立面. #include <bits/stdc++.h> using namespace std; const int N=2e4+5; int n,m; unordered_map<int,int>s; int fa[N],d[N]; int find(int x) { if(fa[x]!=x) { int root=find(fa[x]); d[x]+=d[fa[x]]; fa[x]=r...

因为儿子需要,所以又更一篇水题题解.很容易想到爆搜2^40复杂度直接搜,当然也可以合并分别处理2堆,但是我觉得这题剪枝完全不必要.所以一发爆搜+剪枝就过了.剪枝就是必须保证前面的搜到的答案必要一致.emm没了 #include <bits/stdc++.h> using namespace std; const int N=45; int a[N]; int cka[N],ckb[N]; int n,flag; void dfs(int u,int dep1,int dep2) { if(u>n) return; if(flag) return; if(dep1!=1&amp...

又是查并集..没啥好说的...qaq大概是查并集+、差分思想吧?d[x]表示我x点到root的距离,然后sz[x]表示x集合的大小.显然root到root的距离为0.我们考虑两个集合合并,显然,我们第一个集合的d[root]设为sz[2].sz[2]的大小又要+sz[1].然后我们第二次查询时,就是原来的d[x]+d[root]了.qwq #include <bits/stdc++.h> using namespace std; const int N=3e4+5; int sz[N],d[N],fa[N]; int find(int x) { if(fa[x]!=x) { int...

并查集,忘了.自己写也可以写出来,wow.. #include <bits/stdc++.h> using namespace std; const int N=1e6+5; unordered_map<int,int>fa; struct vv{ int l,r,p; }a[N]; int f(int x) { if(fa[x]!=x) return fa[x]=f(fa[x]); else return fa[x]=x; } int main() { int T; scanf("%d",&T); while(T--) { int n; fa.clear();...

这题可以完全转化为台阶博弈.就看你会不会转化了.//下面讲讲怎么转化,不会台阶博弈的,就...我们可以把我们可以两个棋子之间中的空隙看成台阶的石子数,向左移看成石子往下传递石子.然后就是台阶博弈了?下面讲讲台阶博弈怎么做?台阶博弈是这样的: 现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中第ii级台阶上有ai个石子(i≥1)。 两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。 已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。这个怎么做呢..nim博弈就不解释了ε唉~做法就是奇数堆异或为0就胜.代码如下: #include <b...