数据结构

将修改操作和查询操作分开来，每次都用左区间的修改操作更新右区间的查询操作，因为左区间的修改操作对左区间的查询操作在递归左区间时就已经处理了，同理查询操作也是一样。 写的太暴力，还能过程能优化很多 #include <bits/stdc++.h> using namespace std; typedef long long LL; templ...

在我们平常使用的分治中，每一个子问题只解决它本身（可以说是封闭的）。 而在cdq分治中，对于划分出来的两个子问题，前一个子问题用来解决后一个子问题而不是它本身。 具体算法流程如下： 1.将整个操作序列分为两个长度相等的部分（分） 2.递归处理前一部分的子问题（治1） 3.计算前一部分的子问题中的修改操作对后一部分子问题的影响（治2） 4.递归处理后一部分子问...

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; template <class T> inline bool scan_d(T &ret) {char c; int sgn;if(c=getchar(),c==EOF...

题意：~ 思路：大数中缀表达式计算。。 import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigInteger; import java.u...

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PI; #define lson l, m, rt<<1 #define rson m+1, r, rt<...

题意：~ 思路：给定一个n个点，n-1条边，问添加少的边使原图变成一个双连通图。因为给定的就是一棵树，所以问题简单了很多。 #include <bits/stdc++.h> using namespace std; const int N = 100050; vector<int> g[N]; vector<int&...

题意：给出n个宾馆的坐标以及价格，现在有m个人要住宾馆，给出了m个的坐标和他们能承受的最高价格，询问在承受价格之内的最近的宾馆的坐标和价格，如果答案不唯一，输出顺序在前的宾馆。 思路：多了价值的限制条件，在同样满足条件的情况下，优先查询编号小的 #include <bits/stdc++.h> using namespace std; typ...

题意：求K维空间中给定一个点最邻近的M个点。 思路：KD树模板题， #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PI; ty...

题目链接：点我~~ 题意：给定一棵树，每次询问一个集合，问所有不在这个集合的点两两 LCA (可以相同)的并集大小。 思路：实际上就是对于每个被删掉的点，check 一下是不是除了一个子树之外的点都被删掉了。那么对于每个被删掉的点的连通块，从最高点开始 dfs 就行。 #include <bits/stdc++.h> using namespa...

题目链接：点我~~ 题意：给定一个序列n，有m次查询，每次查询一个区间[l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。 思路： 主席树维护后缀[i,n]，然后对于每次碰到一个数字，就把它以前的位置−1，新位置+1 主席树维护区间不同数字的个数k 然后寻找区间第k/2大呗 因为是维护的后缀，直接找root[l]里的第k/2大出现的位置就...