祝馀宫

题面题目链接大秦 为你打开 题目传送门 备用题面有一个队列，现在对它进行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 ...

原神蒸蒸日上！