题目链接：zoj 3911 Prime Query 代码 #include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int maxn = 1e6 + 5;const int maxm = 1e7;#define lson(x) ((x)<<1)#

线段树题目的类型大致可以分为四种：单点更新、成段增减或更新、区间合并和扫描线 成段更新和区间合并都需要用到Lazy思想。 扫描线就是求矩形面积和周长的题目，需要用到离散化。 本篇讲解区间合并，区间合并肯定是从子节点向上才能用着合并，这类题目都是求最长连续区间的，主要在PushUp的时候需要对左右儿子的区间进行合并。 这里就直接拿题目说事，所有的解释全部在代码的注释里。 4

区间翻转的裸题，wrong了两发，没找bug，直接又打了一遍，这么大量的代码找bug是疯了。 重新开始做线段树的一些题了，感觉对于pushdown与lazy数组有点印象了。 首先，lazy数组是记录的当前数组的改变，不管是这个题的异或，还是加减，lazy数组就是线段树的主要优化原因，当你用的时候你再下放，大大减少了复杂度。但是记录的时候lazy[i]=1时候，tree[i]是要先处理的，然后每

线段树   // 1093MS 10568K G++#include<iostream>#include<cstdio>using namespace std;#define maxn 100005#define ls (rt<<1)#define rs (rt<<1|1)#define mid ((t[rt].l+t[rt].r)>>1)int n,m;struct tr