bitset应用
bitset bitset前身：普通状态压缩的优化 以cf937G为例,对于邻接矩阵的由二维压缩到一维 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <bits/stdc++.h>using i64 = long long;void solve() { int n; std::cin >> n; std::vector<std::string> g(n), w(n); for (int i = 0; i < n; i++) { std::cin >> g[i] >> w[i]; } std::vector<int> e(n); for (int i = 0; i < n; i++) { for (int...
bitset专题
bitset bitset前身：普通状态压缩的优化 以cf937G为例,对于邻接矩阵的由二维压缩到一维 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <bits/stdc++.h>using i64 = long long;void solve() { int n; std::cin >> n; std::vector<std::string> g(n), w(n); for (int i = 0; i < n; i++) { std::cin >> g[i] >> w[i]; } std::vector<int> e(n); for (int i = 0; i < n; i++) { for (int...
log_trick
一类子区间gcd，按位与，按位或的问题 有 TTT 组询问，每次给出 nnn 个数 aia_iai。[P7009 CERC2013] Magical GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 你需要找到这个数组的一个子序列（要求编号连续），使得该序列中所有数的最大公约数和序列长度的乘积最大，并输出这个最大值。 Sol:重要性质如果右端点不同，那么gcd意义下本质不同的左端点只有log个https://www.luogu.com.cn/problem/P5502 1234567891011121314151617181920212223242526272829303132333435363738include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int N=1e5+10;#define LL long longqueue<int>q,r;int n;LL...
01trie特训2
01trie特训2 题意：给定一个含有 n 个元素的数组...
01trie专题
01trie特训2 题意：给定一个含有 n 个元素的数组...
笛卡尔树
笛卡尔树 1234567891011121314151617181920212223242526272829struct DKR { int n; vector<int> l, r; int root; stack<int> st; DKR(int nn) : n(nn), l(nn + 1), r(nn + 1), root(0) {} // 默认为小根堆，维护最小值所在区间 // dkr.built(a,less<int>());大根堆 int built(const vector<int>& a, function<bool(int, int)> cmp = greater<int>()) { while (!st.empty()) st.pop(); // 清空栈 for (int i = 1; i <= n; i++) { int...
可撤销并查集
可撤销并查集 给定n个结点，q次询问，每次询问分为三类： 1 x y：可以选择将x,y两个点连通，如果已经连通则不操作。 2 ：撤销上一次的操作（若全部撤销完了则不操作）。 3 x y：询问x*,*y是否连通，如果是则输出"YES"，反之输出"NO"，请注意都是大写字母，不包含引号。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768struct DSU { std::vector<int> siz; std::vector<int> f; std::vector<std::array<int, 2>> his; DSU(int n) : siz(n + 1, 1), f(n + 1) { std::iota(f.begin(),...
可持久化线段树（主席树）
给定 n 个整数构成的序列 a，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值。 题目一开始的离散化复杂度为O(nlogn)O(n\log n)O(nlogn)，构建基础主席树复杂度为O(nlogn)O(n\log n)O(nlogn)，统计并插入的复杂度是O(nlogn+nlogn)=O(nlogn)O(n\log n + n\log n)=O(n\log n)O(nlogn+nlogn)=O(nlogn)，询问的复杂度是O(mlogn)O(m\log n)O(mlogn)。复杂度总和就是O((m+n)logn)O((m+n)\log n)O((m+n)logn)。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#define N 200005#define lc(x) tr[x].l#define rc(x) tr[x].rstruct node{ int l,r,s;...
可持久化字典树（Trie）
最大异或和 给定一个非负整数序列 {a}\{a\}{a}，初始长度为 NNN。 有 MMM 个操作，有以下两种操作类型： A x：添加操作，表示在序列末尾添加一个数 xxx，序列的长度 NNN 加 111。 Q l r x：询问操作，你需要找到一个位置 ppp，满足 l≤p≤rl \le p \le rl≤p≤r，使得：a[p]⊕a[p+1]⊕...⊕a[N]⊕xa[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus xa[p]⊕a[p+1]⊕...⊕a[N]⊕x 最大，输出最大值。 对于所有测试点，1≤N,M≤3×1051\le N,M \le 3\times 10 ^ 51≤N,M≤3×105，0≤ai≤1070\leq a_i\leq 10 ^ 70≤ai≤107。 分析：设 Si 表示前缀 i 个异或和，令 K=x⊕Sn，然后要在 [0,n−1] 中找到一个 p 使得 Sp⊕K...
离线+并查集
离线+并查集 LCA&DSU&MST - jzcrq - 博客园 (cnblogs.com) 多次询问两点间的瓶颈路，也就是u到v所有路径中边权的最小值最大。 Sol：考虑先将所有询问离线。考虑建立最大生成树的过程，设联通块s1和s2要被边权为w的边连通。对于存在点u在s1,v在s2的询问的答案就是w。为了保证时间复杂度我们考虑启发式合并，注意判断大小的时候只需要交换u和v本身。把询问的对应点和编号挂在点上，每次把size小的部分的点拿出来更新答案和询问。无法回答的插入新的根中。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152void solve() { int n, m; cin >> n >> m; vector<array<int, 3>> edg(m + 1); for (int i = 1; i <= m; i++)...
最新文章