洛谷 BZOJ 线段树维护，每个节点上面记录666个值l0,l1,r0,r1,m0,m1l0,l1,r0,r1,m0,m1l0,l1,r0,r1,m0,m1（套路），代表从左开始最长000的序列长度，最长111的序列的长度，从右开始的…，中间的…（懒） 翻转就是把他们两两交换，pushup\rm pushuppushup也都是套路。 注意覆盖标记比翻转标记优先级高，于是区间覆盖的时候会把翻转...

传送门 安装操作其实就是把这个节点及其祖先节点变成111，卸载操作其实就是把这个节点及其子树之内的所有节点变成000 树链剖分实现即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686...

传送门 线段树实现区间查询最大值，查询最小值，查询和，区间∗−1*-1∗−1，前面333种都没有什么好讲的，最后一种就是把区间和∗−1*-1∗−1，最小值，最大值交换以后∗−1*-1∗−1 注意：下标从000开始。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849...

传送门 翻译有误，应该是查询uuu到vvv上最大值。 线段树查询最大值和区间+1+1+1， 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980...

传送门 需要一棵支持区间加，区间和查询的线段树 其他没什么好说的，注意开long\rm longlong long\rm longlong 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768...

传送门 树链剖分模板题，用支持区间加，区间覆盖，查询区间最大的线段树实现。 注意覆盖标记cotagcotagcotag优先级比加标记tagtagtag要高，所以覆盖时直接设tag=0tag=0tag=0 需要把ChangeChangeChange操作转化为顶点U[k]U[k]U[k]和V[k]V[k]V[k]的覆盖操作 其他没什么好说的，注意细节即可 12345678910111213141...

传送门 考虑尺取法求出所有满足条件的i,ji,ji,j，使∑k=ijFk>=M\sum ^j _{k=i}F_k>=M∑k=ij​Fk​>=M，O(n)O(n)O(n)即可求出。 再考虑如何求max⁡(Si,Si+1,...Sj−1,Sj)\max(S_i,S_{i+1},...S_{j-1},S_j)max(Si​,Si+1​,...Sj−1​,Sj​) 用线段树预处理即...

传送门 线段树模板题。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include <bits/stdc++.h>#define MAXN 1...

传送门 考虑每个宗教建立一棵线段树，但是空间会炸，考虑动态开点。 时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)，空间复杂度O(nlog⁡n)O(n \log n)O(nlogn) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525...

传送门 题意 给你一个数列{ai}\{a_i\}{ai​}和两数L,RL,RL,R，询问有多少组l,rl,rl,r，满足∑i=lra[i]∈[L,R]\sum ^r _{i=l}a[i] \in [L,R]∑i=lr​a[i]∈[L,R] 题解 考虑把∑i=lra[i]\sum ^r _{i=l} a[i]∑i=lr​a[i]转化为前缀和sum[r]−sum[l−1]sum[r]-sum...