传送门 题面 给定一个序列。查询左端点在[x1,y1][x_1, y_1][x1​,y1​]之间，且右端点在[x2,y2][x_2, y_2][x2​,y2​]之间的最大子段和， 数据保证x1≤x2,y1≤y2x_1\leq x_2,y_1\leq y_2x1​≤x2​,y1​≤y2​ ，但是不保证端点所在的区间不重合 题解 线段树好题，建议先做SP1043 GSS1 - Can you...

传送门 线段树每个节点中存的值： val[]val[]val[] ——区间所有数之和 lmax[]lmax[]lmax[] ——选的a[i]a[i]a[i]在区间内，且包括a[l]a[l]a[l]，连续a[i]a[i]a[i]之和的最大值 rmax[]rmax[]rmax[] ——选的a[i]a[i]a[i]在区间内，且包括a[r]a[r]a[r]，连续a[i]a[i]a[i]之和的最大值 ...

感觉这题自己也讲不清，还是搬运洛谷的一篇题解吧。。。 作者: duyi 在Ta的博客查看 观察这题与GSS1的最主要差别是需要去重。 这样的问题有一个比较套路化的技巧（主要看个人经验）。就是可以离线做。我们将所有询问按r从小到大排序。 我们一次从111到nnn扫过整个序列。假设现在扫到iii。在线段树中， 第jjj个叶子结点我们维护a[j]...a[i]a[j]…a[i]a[j]...a[...

建议先做SP1043 GSS1 - Can you answer these queries I 传送门 没什么好讲的，也就是在GSS1的基础上加一个修改，连pushdown都不要。 #include <bits/stdc++.h> #define MAXN 50005 using namespace std; inline int read(){ int x=...

传送门 注意到开方是向下取整的，而且∑ai≤1018\sum a_i \le 10^{18}∑ai​≤1018 所以我们发现没开几次方，大部分aia_iai​都会变成111，此时再怎么开方，aia_iai​还是111，所以不用修改aia_iai​ 所以想到开一个flagflagflag，记录这个区间是不是都是111 若区间都是111修改时直接跳过 1234567891011121314151...

建议先做SP1043 GSS1 - Can you answer these queries I 传送门 我们可以用FHQTreapFHQ TreapFHQTreap做这道题。 首先，FHQTreapFHQ TreapFHQTreap最重要的是Merge和Split操作，Split按照权值split 但是这道题插入删除修改时，要按照分出序列前kkk个值，是不是没法做？ 没关系，我们采用类似于...

建议先做SP1043 GSS1 - Can you answer these queries I 传送门 树链剖分模板题 尽管如此，这道题还是孙了我甚久。 坑点： 在查询的时候，因为两条树链L,RL,RL,R是左右对称的，所以不能直接将两条树链合并计算， 而是先翻转LLL或RRR，再合并计算。 #include <bits/stdc++.h> #define MAXN 20000...