Q779’s Blog

CF877E Danil and a Part-time Job 题解 题目链接：CF877E Danil and a Part-time Job 题意： 一棵树有n个点，根结点编号为1，每个点的权值都是1或0 m次操作： 操作1(get)：询问一个点x的子树里有多少个1 操作2(pow)：将一个点x的子树中所有节点的权值取反 对于每一个操作1，输出答案 输入格式： 第一行一个整数n 第二行共n−1个整数，第i个数xi表示xi是i+1的父亲， 第三行给出n个点的初始权值 第四行一个整数m 接下来m行输入操作的类型和对应的节点遍号 对于每个操作1，输出1的个数 n,m<=2e5 询问&修改子树，显然需要用dfs序，然后用线段树维护 取反操作其实就是把区间和变成区间长度减区间和 而两次取反操作等于啥也没干 因此下传懒标记的时候，直接加个 \(1\) 就好了 时间复杂度 \(O(m \log n)\) 代码： #include <iostream> #include <string> #include <vector> #includ...

时间戳优化树状数组的频繁清空 来自@zx2017老师的ppt Orz 适用场景： 给定 \(T\) 组数据，每组数据有 \(Q\) 个询问，询问给定 \(n\) 个数的区间和 数据范围：\(T\le 2\times 10^5,~\sum Q \le 2\times 10^5,~n\le 5\times 10^5\) 注意，这里只限制了 \(\sum Q\) ，并没有限制 \(\sum n\) 对于每组数据不能直接去清空数组，因为 \(T \times n\) 肯定爆炸 考虑维护一个时间戳now，也就是现在是第几组数据 对于是这组数据的，也就是t[i]==now的情况，直接用 如果不是这组数据的，我们要先清零，再加。 注意到 tree[i]=0,tree[i]+=v 其实等价于 tree[i]=v 由于我们只有查询到一个树上结点，才会去判断它的时间戳 因此这类题目的时间复杂度可以控制在 \(O(\sum Q \log \sum Q)\) 修改部分的代码： int tree[N],t[N],now=0; void add(int x,int v) { for(int...

洛谷P5142 区间方差 题解 题目链接：P5142 区间方差 题意： 对于一个长度为 \(n\) 的序列 \(a_1,a_2,a_3\cdots a_n\)，我们定义它的平均数 \(a\) 为: \[ a=\frac{1}{n}\sum_{i=1}^{n}a_i \] 并定义它的方差 \(d\) 为: \[ d=\frac{1}{n}\sum_{i=1}^{n}(a_i-a)^2 \] 现在给定一个长度为 \(n\) 的序列 \(a_1,a_2\cdots a_n\)。你需要支持两种操作。每种操作的格式为 c x y。 若 \(c=1\)，为修改操作，代表将 \(a_x\) 赋值为 \(y\)。 若 \(c=2\)，为查询操作，代表查询 \(a_x\) 到 \(a_y\) 的方差。 为了避免浮点数误差，请以分数取模形式输出结果（对 1000000007（\(10^9+7\)）取模）。 对于 \(100\%\) 的数据，\(1\leq n,m\leq 1\times 10^5\)，\(1\leq a_i\leq 1\times 10^9\)，\(1\leq x\leq n\)。...

OI模板-图论 最短路算法 dijkstra P4779 【模板】单源最短路径（标准版） 优先队列优化 \(O((n+m)\log m)\) #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> #include <queue> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e5+15) #define M (int)(2e5+15) int n,m,pos=1,d[N],vis[N],head[N]; struct Edge{int u,v,w,next...

OI模板-字符串 字符串哈希 单哈希 给定 \(N\) 个字符串（第 \(i\) 个字符串长度为 \(M_i\)，字符串内包含数字、大小写字母，大小写敏感），请求出 \(N\) 个字符串中共有多少个不同的字符串。 P3370 【模板】字符串哈希 #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e4+15) #define M (int)(1515) const int hash_base=31; const int has...

OI模板-数据结构 笛卡尔树 笛卡尔树满足 每个节点的编号满足二叉搜索树的性质。 节点 \(i\) 的权值为 \(p_i\)，每个节点的权值满足小根堆的性质。 构建的复杂度为 \(\mathcal{O}(n)\) // 2024年06月13日 22:24:45 #include <bits/stdc++.h> using namespace std; // #define int long long // #define INF 0x3f3f3f3f3f3f3f3f typedef long long ll; void up(int &x, int y) { x < y ? x = y : 0; } void down(int &x, int y) { x > y ? x = y : 0; } #define N ((int)(1e7 + 15)) int n, top, a[N], ls[N], rs[N], stk[N]; void build() { for(int i = 1; i...

OI模板-算法 三分法 板子题：P3382 【模板】三分法 时间复杂度 \(O(-\log \epsilon)\) #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cstdarg> #include <cmath> #include <iomanip> #include <random> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define double long double #define N ((int)(15)) const double eps = 1e-6; int n; double l,r,a[N]; double f(double x) { ...

OI模板-数学 注意，本文不同于 OI数学总结-数论 或其他总结类文章 本文倾向于代码实现，只是因为数论的内容与代码联系紧密，并且数论内容较多，因此显得较为相似。 最大公约数 gcd 最大公约数指能够整除多个不全为零的整数的最大正整数 常用性质： \(a\times b = \gcd(a,b) \times \mathrm{lcm}(a,b)\) int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } // 注意这份代码对于(+,-)的情况会求出负数 扩展欧几里德算法(Exgcd) 板子题： P5656 【模板】二元一次不定方程 (exgcd) 若 \(b \ne 0\) ，扩展欧几里得算法求出的可行解必有 \(|x| \le b ,|y| \le a\) 。 int exgcd(int a,int b,int &x,int &y) { int d=a; if(!b)x=1,y=0; else d=exgcd(b,a%b,y,x),y-=a/b*x; ...

OI模板-计算几何 二维凸包 Andrew 时间复杂度 \(O(n \log n)\) #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e5+15) int n; struct vct { double x,y; vct operator-(const vct &o)const { return (vct){x-o.x,y-o.y}; } }p[N],ans[N]; int stk[N],top,used[N]; int cmp(vct a,vct b) { return a.x==b.x?a.y<b.y:a.x<b.x; } double cross(vct a,vct b) { return a.x*b.y-a.y*b...

OI模板-其他 快读快写 测试 T256742 快读测试 稳定版： namespace FastIO { #define gc() readchar() #define pc(a) putchar(a) #define SIZ (int)(1e6+15) char buf1[SIZ],*p1,*p2; char readchar() { if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin); return p1==p2?EOF:*p1++; } template<typename T>void read(T &k) { char ch=gc();T x=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();} while(isdigit(ch)){x=(x...

洛谷P2391 白雪皑皑 题解 题目链接：P2391 白雪皑皑 题意： 现在有 \(n\) 片雪花排成一列。 pty 要对雪花进行 \(m\) 次染色操作，第 \(i\) 次染色操作中，把第 \(((i\times p+q)\bmod n)+1\) 片雪花和第 \(((i\times q+p)\bmod n)+1\) 片雪花之间的雪花（包括端点）染成颜色 \(i\)。其中 \(p,q\) 是给定的两个正整数。他想知道最后 \(n\) 片雪花被染成了什么颜色。没有被染色输出 \(0\)。 \(1\leq n\leq 10^6,~1\leq m\leq 10^7\)。 保证 \(1\leq m\times p+q,m\times q+p\leq 2\times 10^9\)。 一句话题意：线性区间推平（区间赋同一个值），全局询问。 我们模拟赛t3，也是我想了几个月结果有原题的东西，不写题解亏大了 考虑倒序处理修改，因为一个位置的值一定由它最后一次被修改的数决定 暴力推平？对于被推平的点，不可以再推了，所以我们要跳过它 这就需要维护每个点右侧的那个未被推平的结点 可以考虑链表或者并...

洛谷P2024 [NOI2001] 食物链 题解 题目链接：P2024 [NOI2001] 食物链 题意：动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。 现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这 N 个动物所构成的食物链关系进行描述： 第一种说法是1 X Y，表示 X 和 Y 是同类。 第二种说法是2 X Y，表示 X 吃 Y 。 此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 当前的话与前面的某些真的话冲突，就是假话 当前的话中 X 或 Y 比 N 大，就是假话 当前的话表示 X 吃 X，就是假话 你的任务是根据给定的 N 和 K 句话，输出假话的总数。 \(1 \le N \le 5\times10^4,~1 \le K \le 10^5\) 考虑种类并查集。 我们维护三个并查集，分别存同类、食物和天敌 这里...