爱飞鱼的blog

#时间复杂度为Θ(n^3) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495const int inf =0x3f3f3f3f;const int N=505;long long w[N][N];long long la[N],lb[N];bool va[N],vb[N];long long match[N];long long n,m,upd[N];long long last[N];bool dfs(int x,int fa){ va[x]=1; for(int y = 1; y<=n; y++) { if(!vb[y]) { ...

01trie特训2 题意：给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。 Sol：考虑枚举两段的分界点，对于较短的两段来说可能会有多个分界点但这样我们求的是答案的超集，一定会包括答案的。对于一个分界点，我们先考虑如果要求以左边区间必须包含分界点，那么我们只需要异或前缀和后找一个位置和它异或最大或最小，这是经典的01trie的应用。再考虑右边，我们需要做后缀异或和，做跑一遍trie。注意实际上可以不以分界点为选取的子段的端点，我们需要需要维护异或后结果的前缀最大值，后缀最小值，剩下同理。 ...

给定一棵有 nnn 个点的树，询问树上距离为 kkk 的点对是否存在。 第一行两个数 n,mn,mn,m,n个点。 第 222 到第 nnn 行，每行三个整数 u,v,wu, v, wu,v,w，代表树上存在一条连接 uuu 和 vvv 边权为 www 的路径。 接下来 mmm 行，每行一个整数 kkk，代表一次询问。 对于每次询问输出一行一个字符串代表答案，存在输出 AYE，否则输出 NAY。 对于 100%100\%100% 的数据，保证 1≤n≤1041 \leq n\leq 10^41≤n≤104，1≤m≤1001 \leq m\leq 1001≤m≤100，1≤k≤1071 \leq k \leq 10^71≤k≤107，1≤u,v≤n1 \leq u, v \leq n1≤u,v≤n，1≤w≤1041 \leq w \leq...

stl的妙用 关于mutiset的应用的几个题 G - Minimum Xor Pair Query 题意：你可以进行以下操作 加入一个数 删除一个数 输出任意两个数异或最小值 思路：首先我们要知道一个性质(重要!)：两个数差值越小，异或值也越小。 那么我们要求异或最小值，那么答案一定在排序后相邻两个数中产生。 为了便于写，防止在set里面找不到的情况出现，我们手动插入下界和上界。 考虑我们的操作： 对于加入一个数，我们的答案有什么影响呢？ 假设我们插入的值是x。 假设我们的情况是：l x r 首先如果l和r都存在，那么显然此时l和r的异或值不可能成为答案，我们把它删去 然后在答案里面加入x^l和 x^r(前提是l，r存在) 12345678910111213void add(ll x){ s.insert(x); multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x); it1--, it2++; if(*it1 != -1 && *it2 !=...

给定 n 个整数构成的序列 a，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值。 题目一开始的离散化复杂度为O(nlog⁡n)O(n\log n)O(nlogn)，构建基础主席树复杂度为O(nlog⁡n)O(n\log n)O(nlogn)，统计并插入的复杂度是O(nlog⁡n+nlog⁡n)=O(nlog⁡n)O(n\log n + n\log n)=O(n\log n)O(nlogn+nlogn)=O(nlogn)，询问的复杂度是O(mlog⁡n)O(m\log n)O(mlogn)。复杂度总和就是O((m+n)log⁡n)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;...

离线+并查集 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++)...

E题：题意：给定一个数组，你有两个操作，第一个操作是对任意前缀减去一个数，第二个操作是对任意后缀减去一个数。现在希望你用这两个操作将这两个数都变成0，要求操作次数最少，无解情况需要判断。 Sol:考虑两种操作，一种前缀操作，一种后缀操作都是对一整个区间操作，我们应该想到区间加常用的差分！我们记d为差分数组 操作1等价于d[1]−=k和d[i+1]+=kd[1]-=k和d[i+1]+=kd[1]−=k和d[i+1]+=k 操作2等价于d[n+1]+=k和d[n−i+1]−=kd[n+1]+=k和d[n-i+1]-=kd[n+1]+=k和d[n−i+1]−=k 题目要求我们用最少操作次数完成原数组恰好全部置0，等价于差分数组变0. 问题转化到这逐渐清晰。 考虑d[n+1]是不影响答案的，也就是操作二使用没有代价，对于差分数组中的所有正元素全部可以免费变0 对于为0的不用管 对于负元素，我们需要用操作1将其变0，考虑代价是次数加1以及d[1]减小，如果d[1]不够减，则原问题无解。 123456789101112131415void...

经典数据结构问题 静态区间颜色数 1234567891011121314151617181920212223242526272829303132void solve() { int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; int m; cin >> m; int mx = *max_element(alls(a)); vector<vector<pii>> q(n + 1); for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; q[r].push_back({l, i}); } deb("?"); ...

12345678910111213141516void floyd(){ for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}init(){ for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF;}存边方式： d[a][b] = min(d[a][b], w);# 如果是无向边需要加d[b][a]

笛卡尔树 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...