【拾题杂谈】LuoguP4145 花神游历各国
题面大秦为你打开题目传送门
题目背景XLk 觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。
题目描述“第一分钟，X 说，要有数列，于是便给定了一个正整数数列。
第二分钟，L 说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟，k 说，要能查询，于是便有了求一段数的和的操作。
第四分钟，彩虹喵说，要是 noip 难度，于是便有了数据范围。
第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。
第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过 $64$ 位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。
输入格式第一行一个整数 $n$，代表数列中数的个数。
第二行 $n$ 个正整数，表示初始状态下数列中的数。
第三行一个整数 $m$，表示有 $m$ 次操作。
接下来 $m$ 行每行三个整数 k l r。
$k=0$ 表示给 $[l,r]$ 中的每个数开平方（下取整）。
$k=1$ 表示询问 $[l,r] ...
【拾题杂谈】517八段第三课E
题面题目链接大秦 为你打开 题目传送门
备用题面给定一个序列 $A[1],A[2],A[3],…,A[N]$ 。
定义 $Query(x,y)=Max\{a[i]+a[i+1]+…+a[j]\};\{x≤ i≤ j ≤ y\}$
给出 $M$ 个查询 $(x,y)$ ，对于每一个查询，输出它们的值。
思路首先这道题目的原题大家都知道，就是最大子段和。但是这个如何用线段树来维护呢（毕竟是要区间查询）
我们不妨看看一个字段有几种组成部分（对于线段树的树节点）：
全在左儿子
全在右儿子
两边都有。
全在左儿子和全在右儿子的好办，我们只需要记录 $\tt lsum , rsum$ 分别表示就可以了，但是在中间的怎么办？我们不妨大胆一点，直接设 $\tt lsum,rsum$ 是到中间为止的，那么在中间的段就可以用左边的右边最大和右边的左边最大拼起来，这样就解决了。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960 ...
【拾题杂谈】POJ3321 Apple Tree
题面大秦 为你打开 题目传送门
题目翻译给定一个包含N个结点的苹果树，结点从1到N编号，树根为1。
苹果会长在某些结点上，但是两个苹果不会同时长在一个结点上。
随着时间的推移，苹果会被摘走，或者某些结点又长出新苹果。
现在我们想知道在某个时刻某个子树中有多少苹果。
思路首先不难想到用线段树（当然也可以树状数组），在树上的线段树问题一般都得用 Dfs 序或者树链剖分把他们化作区间上的问题解决。而这道题特别简单，没有大的需求用树链剖分，这里使用Dfs序，所谓Dfs序，就是记录他第一次被访问，和最后一次被访问的位置，这样就转化成了区间，而且这样这个区间可以包含他的整个子树。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106 ...
【算法模板】线段树区间修改区间查询求和
解释出门右转 线段树博文 谢谢
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657struct Node { int L, R; ll num, lazy; Node() {} Node(int L, int R, ll num) : L(L), R(R), num(num) {} Node operator + (Node &you) const { return Node(min(L, you.L), max(R, you.R), num + you.num); }};class SegTree { private : Node node[N << 2]; public : void Add(int p, ll v) ...
【算法模板】线段树区间修改区间查询最小值
解释出门右转 线段树博文 谢谢
附：Add函数里面加 v 是因为我们最小值统计的只是一个元素。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657struct Node { int L, R; ll num, lazy; Node() {} Node(int L, int R, ll num) : L(L), R(R), num(num) {} Node operator + (Node &you) const { return Node(min(L, you.L), max(R, you.R), min(num, you.num)); }};class SegTree { private : Node node[N << 2]; public ...
【算法模板】线段树单点修改区间查询最小值
解释出门右转 线段树博文 谢谢
这个真的没什么好说，，，，太简单了
123456789101112131415161718192021222324252627282930313233343536373839404142434445struct Node { int L, R; long long num; Node() {} Node(int L, int R, long long num) : L(L), R(R), num(num) {} Node operator + (Node &you) const { return Node(min(L, you.L), max(R, you.R), min(num, you.num)); }};class SegTree { private : Node node[N << 2]; public : void Build(int p, in ...
即刻测试
原神蒸蒸日上！
【算法介绍】欧几里得算法
算法简介：时间 与 智慧欧几里得算法，简称 $\gcd$ ，常用的是辗转相减或辗转相除，是一个远古时期就被前人证明出来的算法。还有就是拓展欧几里得算法简称 $\tt exgcd$ ，是一个基于欧几里得算法用于求解 $Ax+By=C$ 方程的算法。非常的玄学，接下来会讲讲关于这些算法的流程代码以及复杂度分析。
算法演示：影照浮世风流欧几里得算法：旧语新知 · 记忆中的沙丘欧几里得算法，就是中国的辗转相减或辗转相除，本质上是让两个数不断地大数减小数（或者是用小数模大数），最后求出最大公约数，那么为什么会是这样呢？看如下证明
设一个 $a, b, c$ 分别表示 $\gcd(a,b) = \gcd(b,c)$ 这样一个式子的一部分，令他们三满足关系 $a=b\times q_0+c$（ $a$ 除以 $b$ 的余数是 $c$ ）如果 $b,c$ 有一个公因子 $q_1$ ，则这两个数可以有如下表示方法：
b=k_0\times q_1,c=k_1\times q_1将其带入式子 $a = b\times q_0 + c$ ，可得：
\begin{align}
a&=b ...
【算法介绍】素数筛法
算法简介：骑士团长的一日假期素数筛法是作为数论基础而出现的。数论本质上是对数字的一些性质的研究，而质数是这里很重要的一部分。不同的质数筛有着不同的特性，用来解决不同的题目，接下来我们会大概了解几种。
算法演示：若困你于无风之地$O(\sqrt n)$ 判断单个质数这个很简单，由于考虑到因子是一对一对的，所以一对因数中较小的那一个最多最多是 $\sqrt n$ ，也就是说我们只需要枚举 $2$ ~ $\sqrt n$ 复杂度 $O(\sqrt n)$ ，不枚举 $1$ 是因为所有数字都是 1 的倍数，素数也只是被 $1$ 和它本身整除。
1234567bool isPrime(int x) { if(x <= 1) return false; for(int i = 2; i * i <= n; i++) { if(x % i == 0) return false; // 找到一个不是 1 也不是它本身的因子 } return true;}
$O(n\log\log n)$ 多个快筛这个就属于新开一 ...
