求一手聚聚的官方题解

这题写了我两个小时，在cf延时的15分钟内调出来了，直呼内行D 线段树 区间加，区间乘，区间查询，区间覆盖给个节点用k*x+val 表示lazy更新 初始叶子节点k=1 val=a[l] 其他 k=1 val=0 一个mul数组，记录每个节点的前面的系数k，val数组记录后面val的值 sum数组记录区间和，因为询问的是区间和 每次区间乘了一个k： 某个节点记录： mul[id]*=k val[id]*=k sum[id]*=k mul[id]=k*mul[id]%mod; val[id]=k*val[id]%mod; sum[id]=k*sum[id]%mod;区间加了一个k: val[id...

赛后补C题，这题型怎么越看越像虚树呢，然后试着用虚树+两次dfs找直径 AC了 将相同势力的点拿出来建虚树，然后树上找直径即可。但是这树没说根，我们假设1为根，找直径的时候特判一下1节点就可以了。  #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll inf=0x3f3f3f3; const int N=2e5+10; int dfn[N],numdfn; int n,max_deep; int a[N]; /* lca部分 */ struct LCA { int head[N],d...

如标题

这题看起来难，题面有点长，读懂就是水题一个了。 题意：有两个人：JOJO 和 Dio 玩游戏 两个人各自有n长度的字符串，以及相同的血量h 现从1开始遍历字符串，当 JOJO 有连续的后缀字符是ora 那么就会施法使得Dio 血量减一 当Dio有连续的后缀字符是muda 那么就会施法使得JOJO 血量减一 当Dio有连续的后缀字符是zawaluduo 会使得JOJO瞬间没血 当JOJO有连续的后缀字符是zawaluduo 会使得Dio瞬间没血 如果同时发现zawaluduo 优先执行JOJO的。 判断最后谁赢了 做法:模拟一下就可以了。 #include<bits/stdc++.h&gt...

I-Interesting Matrix Problem 题意：给你N *M的矩阵 （1<=N , M <=1e8）矩阵内的值是 i乘j 现有q次询问，每次询问输入k 代表 查询这个矩阵内第k小的数是多少。 做法：第一思路二分答案，然后mid去check O(N) 枚举行 i 计算mid/i的个数，发现会超时 写下公式：  这个公式好眼熟啊，不就是数论的整除分块，果断套了一个分块 时间复杂度：q*sqrt(N) 注意还要判断mid/i 不能大于m #include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=(...

糖糖别胡说，我真的不是签到题目题目链接：https://ac.nowcoder.com/acm/problem/14583题意很简单做法：看到别人的做法都是差分求出最后的数值，然后倒着求答案。 今天我就来一个特殊的做法，直接正着模拟。开两棵线段树，维护0和1  ① 遇到一个0 需要把种类为1的小于当前bi全部消掉，这里用权值线段树维护区间和+懒人标记 去更新 ② 接着将当前这个0插入到0种类的线段树内。最后的答案就是sum[0][1]+sum[1][1] ③ 至于如何维护 施法 前面的数字全部加1呢？用一个基数base代表施法次数。每次遇到新的ai bi 将bi-base就能做到和前面的bi是...

作为一个竞赛选手没问我一个算法题表示很伤，你让我写个lca，ac自动机都行啊  ，另一方面的确自己计算机基础知识还是太薄弱了   笔试搞出3个题外加一个45%   已经凉了   大概流程：   1.自我介绍   2.问了大学学了哪些相关专业课程   3.计网什么什么在哪个层  （问的计网问题一个没听懂 不会）   4.操作系统分段管理与分页管理的区别（不会）   5.数据库存储类型有哪些（不会）   ...省略很多相关数据库、操作系统、计网的题   6.++i  和i++的区别（答出）   7.const *  和*const的区别（答出）   8.B+树和B树的区别（只答出部分）   9.统...

【题意】  给由01组成的矩阵，问包含1的子矩阵第二大的面积是多少   【题解】   悬线法求极大子矩阵的裸题   悬线法推荐学习博客：https://blog.csdn.net/dbc_121/article/details/77503611   【代码】   不知道怎么贴代码   #include <iostream> #include <algorithm> using namespace std; const int Max = 3005; int ves[Max][Max], up[Max][Max], Left[Max][Max], Right[Max][M...

D题第一个样例给解释可以不~