A 借教室 法一：线段树 区间修改 / 懒标记 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6+10; int n,m; int w[N]; struct node{ int l,r; ll lazy; ll minm; }tr[N*4]; void pushdown(int u){ auto &rt=tr[u],&le=tr[u<<1],&ri=tr[u<<1|1]; ...

F 题 邻接表 + 优先队列 + 贪心 思路 (1) 建树 — 邻接表 初始时，只有根节点 (序号0)，遇到 '(' 即入栈时 则建立新节点，遇到 ')' 即出栈时，则执行"退后操作" 建立新节点时，新节点的序号为入栈序号，新节点的父亲为 now 结点 now 结点，指当前我们指向的结点 因此，建立新节点 即 新建一个 now 结点的子节点，"退后操作" 即 让 now 指向 now 的父节点 建好树后，共有 n+1 个结点，n 条边 n+1 个结点，指最初的 0 结点 与 新建的 n 个新节点(2) "染色" — 贪心 + 优...

H 题 前置知识 假设 A 、B相邻，A 二进制表示中 1 的个数为 x ，B 二进制表示中 1 的个数为 y 那么，y 必为 x+1 或 x-1（x = 0 时，y 只能为 x+1 ） 因此，x 和 y 的奇偶性，必不同思路 我们令，二进制表示中 1 的个数为偶数的顶点的属性为 ‘0’，反之为 ‘1’，便可以实现： 对于任意一个顶点 A ，与其相邻的顶点必与其属性不同 证明如下： 假设 A顶点、B顶点 相邻，且 A、B 的属性相同 不妨令，A 二进制表示中 1 的个数为 x ，B 二进制表示中 1 的个数为 y 那么 x 和 y 的奇偶性，必不同，因此 A、B的属性也必不同，这与假设矛盾...

C Looooops 思路 k 位存储系统，意思是能储存的最大数为 2^k-1，越过了会变为 0 所以 A + x*C B（mod 2^k）利用扩欧求得 x 即可 Code #include <bits/stdc++.h> using namespace std; typedef long long ll; ll exgcd(ll a,ll b,ll &x,ll &y){ if(!b){ x=1,y=0; return a; } ll d=exgcd(b,a%b,y,x); y-=a/b*x...

线性筛 + 前缀和 思路 先用线性筛把漂亮数给筛出来，然后利用前缀和的性质做到 O(1) 查询 Code #include <bits/stdc++.h> using namespace std; const int N = 1e8+10; int cnt; bool st[N]; bool vis[N]; int sum[N]; int primes[N]; void Init(){ for(int i=2;i<=N;i++){ if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j...

打鼹鼠 二维前缀和 ＋ 树状数组（二维） Code #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5000; ll tr[N][N]; int n,m; int lowbit(int x){ return x & -x; } void add(int x,int y,int v){ for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)) tr[i][j...

简单题 思路 转为括号序列，左括号：区间左端点，右括号：区间右端点 t = 1 时，L 处的左括号数目加 1，R 处的右括号数目加 1 t = 2 时，令 [1,x] 区间的左括号数目 减去 [1,x-1] 区间的右括号数目 = k k 就是 位置 x 上的元素（初始为0） 的变化次数，k 为偶数 答案为 0，否则为 1Code #include <bits/stdc++.h> using namespace std; const int N = 1e5+10; int tr[N],trr[N]; int n,m; int lowbit(int x){ retur...

校门外的树 思路 转为括号序列，左括号：区间左端点，右括号：区间右端点 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...