校门外的树 思路 转为括号序列，左括号：区间左端点，右括号：区间右端点 k = 1 时，l 处的左括号数目加 1，r 处的右括号数目加 1 k = 2 时，[1,r] 区间的左括号数目 减去 [1,l-1] 区间的右括号数目 就是答案 Code #include <bits/stdc++.h> using namespace std; const int N = 1e5+10; int tr[N],trr[N]; int n,m; int lowbit(int x){ return x & -x; } void add(int t[],int x,int...

不需要懒标记，区间修改转为单点修改 思路 已知：0 或 1 开根号后 仍是 0 或 1，又因为 1e9 最多开 5 次根号就会变成 1（每个数最多修改 5 次） 所以本题的区间修改 可以变为单点修改 + 剪枝为什么不会超时？ 对于查询操作，单次查询时间复杂度为 O(logn)，最多执行 m 次，所以最坏是 O(m*logn) 对于修改操作，单点修改时间复杂度 O(logn) 又因为有剪枝，每个点最多修改 5 次，且 m 次操作，最多修改 n 个点，所以最坏是 O(5*n*logn) 所以总时间复杂度约为 max(O(m*logn),O(5*n*logn)) flag 取值的含义 fla...

思路 枚举右端点 i 当 fee[i] <= p 时，对其有贡献的左端点是：i 左侧所有与 i 同色的点 当 fee[i] > p 时，对其有贡献的左端点分为两种： (1) i 左侧，所有与 i 同色的，fee[j] <= p 的 j 点 显然： 位置 j < 位置 i (2) i 左侧，所有与 i 同色的，在某个 j 点左侧的点 ps：j 就是 (1) 中的 j 为了方便 fee[i] > p 的情况，我们在 fee[i] <= p 时 才对 num[color] 进行更新 注： color[i] ：第 i 个客栈的配色 num[color...

思路 枚举右端点 i 当 fee[i] <= p 时，对其有贡献的左端点是：i 左侧所有与 i 同色的点 当 fee[i] > p 时，对其有贡献的左端点分为两种： (1) i 左侧，所有与 i 同色的，fee[j] <= p 的 j 点 显然： 位置 j < 位置 i (2) i 左侧，所有与 i 同色的，在某个 j 点左侧的点 ps：j 就是 (1) 中的 j 为了方便 fee[i] > p 的情况，我们在 fee[i] <= p 时 才对 num[color] 进行更新 注： color[i] ：第 i 个客栈的配色 num[color...

离散化 + dp + ST 表 参考楼上大佬的题解，总结出下面的思路 r[i]：以 i 作为左端点时，其右端点的位置. 则以 i 为起点时，目标序列的最大长度为 r[i] - i + 1 r[i] 具有非减性质，这为二分提供了前提条件 对于区间[L,R]，求其内部最长"好序列"的长度时，区间内每个点都有可能是“最长好序列”的左端点 所以有两种情况：(1)存在 r[i] > R 的左端点 (2)不存在 r[i] > R 的左端点 对于(1)： r[i] 大于 R 的左端点中，我们只需要考虑它们中最左边的那个(考虑r[i]的非减性,可用二分)，得到 ans1 ...

ST 表 + 优先队列 + 前缀和 题意 给一个长度 为 n 的序列，让你从中选 k 个长度在 [L,R] 范围内的区间 (同一个区间不可选多次) 要求：这 k 个区间的区间和 相加 得到的值 应该最大 思路 (1):求出前缀和 (2):枚举 i 令其作为区间左边界，则右边界ri可取值 [i+L-1,i+R-1] 使用RMQ在区间[i+L-1,i+R-1]里找到pos => 目标区间里最大值的下标，即：对于左端点 i 有最大区间和 sum[pos] - sum[i-1] 同时，我们把 {i:此时的左边界,i+L-1:右边界最小值,i+R-1:右边界最大值,最大区间和} 作为一个结构体放...

线段树 或 ST 表 法1：线段树 #include <bits/stdc++.h> using namespace std; const int N = 2e5+10; int m,d; struct node{ int l,r; int maxm; }tr[N*4]; void pushup(int u){ tr[u].maxm=max(tr[u<<1].maxm,tr[u<<1|1].maxm); } void build(int u,int l,int r){ tr[u]={l,r}; if(l==r...

并查集 + 离散化 思路 离散化之后，先执行 op = 1 的，再执行 op = 0 的 执行 op = 1 的时：直接合并 执行 op = 0 的时：进行判断Code #include <bits/stdc++.h> using namespace std; const int N = 1e7+10; struct node{ int x,y; int op; bool operator < (const node & a) const{ return op > a.op ; } }p[N...

并查集 + 邻接表 + 逆向思维 逆向思维: 原题意：共要删除 k 个点，问：每次删除过后，连通块个数是多少？ 逆向思维：删点 ==> 加点、连边 对！没错，变成了加点与连边 所以最开始，我们只对 n-k 个点进行合并操作就行，然后枚举每个要删除的点（注意是从后向前枚举） 对于每个枚举到的 "要删点"，我们执行 加点 与 连边操作(合并操作) 加点：加上该点 连边：对 该点 和 与其直接相连的点们 进行并查集的合并操作 ps：被删点 和 被删点 可能直接相连，比如 题目让我们先删 6，再删 3，但 3、6 直接相连 当我们枚举时，因为是逆着枚举，所以我们会先枚...

法1：三倍空间，种类并查集 类似于：https://ac.nowcoder.com/acm/problem/16591 Code #include <bits/stdc++.h> using namespace std; const int N = 3e5; int fa[N]; int n,k; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } bool check(int op,int x,int y){ if(x>n||y>n) return t...

并查集 思路：对于每次询问，我们找出所有边权 >=k 的边，对于每个找出的边，对其两端的点进行合并操作，最后 v点所在联通块 所含的点的数目减一(减去自身) 就是本次询问的答案 但因为数据过大，每次询问我们都将 所有 边权>=k 的边找出来 对其两端点进行合并操作的话，会超时而且还会有许多重复操作：比如 第一次询问要求我们找出 所有边权>=4 的边，第二次询问要求我们找出 所有边权>=2 的边你会发现 >=4 的边 其实也是 >=2 的，所以对于第二次询问，其实我们没有必要找出所有 >=2 的边只需要找出一部分便是(在上一次询问中已经被找到的边没必要...

思路 M 对互相仇恨的罪犯，我们按仇恨值从大到小排序，对于每一对互相仇恨的罪犯，我们要设法将他们分配在不同的监狱里，反正不能在同一监狱里 如果不可避免的在同一监狱了 也就是与我们的策略发生冲突了，那么此时的仇恨值就是答案 如果到最后都不曾发生冲突，那么答案是 0，因为此时：任意一对会冲突的罪犯 都不会位于同一个监狱(二分图) 不管是 从大到小排序 还是 分配在不同的监狱里，这一切都是为了保证：矛盾的最大值最小(题意要求) 法1：种类并查集：开二倍空间 令 x 表示 x 自身，x + n 表示 x 的敌人 Code #include <bits/stdc++.h> using...

Code #include <bits/stdc++.h> using namespace std; const int N = 1e6+10; string stk[N]; int hh; int main(){ int q; while(cin>>q){ hh=0; for(int i=1;i<=q;i++){ int op; cin>>op; if(op==1){ string s; ...

并查集 + map Code #include <bits/stdc++.h> using namespace std; const int N = 20010; unordered_map<string,string>fa; int n,m; string find(string x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { ...