祝馀宫

题面大秦为你打开题目传送门 题目描述在 $2016$ 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。 这个难题是这样子的：给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部排序，排序分为两种： 0 l r 表示将区间 $[l,r]$ 的数字升序排序 1 l r 表示将区间 $[l,r]$ 的数字降序排序 注意，这里是对下标在区间 $[l,r]$ 内的数排序。最后询问第 $q$ 位置上的数字。 输入格式输入数据的第一行为两个整数 $n$ 和 $m$，$n$ 表示序列的长度，$m$ 表示局部排序的次数。 第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个排列。 接下来输入 $m$ 行，每一行有三个整数 $\text{op},l,r$，$\text{op}$ 为 $0$ 代表升序排序，$\text{op}$ 为 $1$ 代表降序排序, $l,r$ 表示排序的区间。 最后输入一个整数 $q$，表示排序完之后询问的位置 输出格式输出数据仅有一行，一个整数，表示按照 ...

题面大秦为你打开题目传送门 题目描述有一棵点数为 $N$ 的树，以点 $1$ 为根，且树有点权。然后有 $M$ 个操作，分为三种： 操作 $1$：把某个节点 $x$ 的点权增加 $a$。 操作 $2$：把某个节点 $x$ 为根的子树中所有点的点权都增加 $a$。 操作 $3$：询问某个节点 $x$ 到根的路径中所有点的点权和。 输入格式第一行包含两个整数 $N,M$。表示点数和操作数。接下来一行 $N$ 个整数，表示树中节点的初始权值。接下来 $N-1$ 行每行两个正整数 $\mathit{from},\mathit{to}$， 表示该树中存在一条边 $(\mathit{from},\mathit{to})$。再接下来 $M$ 行，每行分别表示一次操作。其中第一个数表示该操作的种类，之后接这个操作的参数。 输出格式对于每个询问操作，输出该询问的答案。答案之间用换行隔开。 样例 #1样例输入 #112345678910115 51 2 3 4 51 21 42 32 53 31 2 13 52 1 23 3 样例输出 #11236913 提示对于 $100\%$ 的数据，$1\le ...

题面题目链接大秦 为你打开 题目传送门 备用题面有一个队列，现在对它进行n次操作，每次操作可以是下面三种中的一种： “in x”：向队列中加入插入一个整数 $x(0 ≤x ≤10^9)$ 。 “out”：从队列中弹出一个数字。 “query”：从队列中查询中位数，例如队列中有 $m$ 个数字，则中位数是，升序排序后第 $floor(\cfrac m 2)+1$ 个数字。 初始队列为空。 思路权值线段树模板题，直接在线段树上面跑二分，线段树的数值表示这段区间（指数字）数字的个数。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596#include<bits/stdc++.h>using namespace std;const int N = 100010;cla ...

题面大秦为你打开题目传送门 题目背景XLk 觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。 题目描述“第一分钟，X 说，要有数列，于是便给定了一个正整数数列。 第二分钟，L 说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。 第三分钟，k 说，要能查询，于是便有了求一段数的和的操作。 第四分钟，彩虹喵说，要是 noip 难度，于是便有了数据范围。 第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。 第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过 $64$ 位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。” ——《上帝造题的七分钟·第二部》 所以这个神圣的任务就交给你了。 输入格式第一行一个整数 $n$，代表数列中数的个数。 第二行 $n$ 个正整数，表示初始状态下数列中的数。 第三行一个整数 $m$，表示有 $m$ 次操作。 接下来 $m$ 行每行三个整数 k l r。 $k=0$ 表示给 $[l,r]$ 中的每个数开平方（下取整）。 $k=1$ 表示询问 $[l,r] ...

题面题目链接大秦 为你打开 题目传送门 备用题面给定一个序列 $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 ...

题面大秦 为你打开 题目传送门 题目翻译给定一个包含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 ...

原神蒸蒸日上！