线段树：
注意 ： 4倍 空间 4倍空间
╮(╯▽╰)╭，一直有点半懂不懂 ， 这些应该可以了
树的建立： 注意 l==r 时要return！！！
void build(int l,int r,int i) { p[i].l=l; p[i].r=r; if(p[i].l==p[i].r) { p[i].hz=p[i].mz=p[i].qz=1; return ; ///////////////// 关键 } int mid=(l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1); up(i); // gen xin }
懒标记： 超级重要，一定要对每一道提具体分析，懒标记的转移一定要正确。
void down(int i) { if(p[i].lazy==0) return; p[i<<1].lazy=p[i<<1|1].lazy=p[i].lazy; // 标记跟新 if(标记满足什么) { 跟新什么 } p[i].lazy=0; // 注意！！！！！！！！！ }
上传：
void up(int i) { p[i].状态=p[i<<1].状态+p[i<<1|1].状态; }
树的修改：
void xiu(int l,int r,int i) { if(l>p[i].r||r<p[i].l) return ; if(l<=p[i].l&&p[i].r<=r) { lazy[i]^=1; /// LAZY 是帮忙记录儿子的信息，不是自己的 p[i].sum=(p[i].r-p[i].l+1)-p[i].sum; // 更新自己的信息 return ; //// 下传递很重要 } down(i); xiu(l,r,i<<1); xiu(l,r,i<<1|1); up(i); // 上传递很重要 }
树的查询（有时候不一样）：
long long cha(int l,int r,int i,int k) { if(l>p[i].r||r<p[i].l) return 相反的; if(l<=p[i].l&&p[i].r<=r) { if(k满足什么状态) return p[i].状态; // ruturn } return 2个状态 cha(l,r,i*2,k),chaa(l,r,i*2+1,k) }
特别：
int cha(int i,int x) { down(i); if(p[i].r-p[i].l+1==x&&p[i].mz==x) return p[i].l; if(p[i<<1].mz>=x) return cha(i<<1,x); if(p[i<<1].hz+p[i<<1|1].qz>=x) return p[i<<1].r-p[i<<1].hz+1; if(p[i<<1|1].mz>=x) return cha(i<<1|1,x); return 0; }
例题：
1824: 【高级数据结构】Hotel 时间限制: 1 Sec 内存限制: 64 MB 提交: 18 解决: 7 [提交] [状态] [讨论版] [命题人:外部导入] 题目描述 奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50,000)间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的 湖面。 贝茜一行，以及其他慕名而来的旅游者，都是一批批地来到旅馆的服务台，希望能订到D_i (1 <= D_i <= N)间连续的房间。服务台的接待工作也很简单：如果存在r满足编号为r..r+D_i-1的房间均空着，他就将这一批顾客安排到这些房间入住；如果没有满足条件的r，他会道歉说没有足够的空房间，请顾客们另找一家宾馆。如果有多个满足条件的r，服务员会选择其中最小的一个。 旅馆中的退房服务也是批量进行的。每一个退房请求由2个数字X_i、D_i描述，表示编号为X_i..X_i+D_i-1 (1 <= X_i <= N-D_i+1)房间中的客人全部离开。退房前，请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。 而你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共需要处理M (1 <= M < 50,000)个按输入次序到来的住店或退房的请求。第一个请求到来前，旅店中所有房间都是空闲的。 输入 * 第1行: 2个用空格隔开的整数：N、M * 第2..M+1行: 第i+1描述了第i个请求，如果它是一个订房请求，则用2个数字: 1、D_i描述，数字间用空格隔开； 如果它是一个退房请求，用3个以空格隔开的数字: 2、X_i、D_i描述 输出 * 第1..??行: 对于每个订房请求，输出1个独占1行的数字：如果请求能被满足，输出满足条件的最小的r；如果请求无法被满足，输出0 样例输入 Copy 10 6 1 3 1 3 1 3 1 3 2 5 5 1 6 样例输出 Copy 1 4 7 0 5
代码：
#include <bits/stdc++.h> using namespace std; const int N = 50005; const int M = 50005; #define ri register int struct settree{ int l,r,qz,hz,mz,lazy; }p[N*4+5]; void up(int i) { p[i].mz=max(max(p[i<<1].mz,p[i<<1|1].mz),p[i<<1].hz+p[i<<1|1].qz); p[i].qz=p[i<<1].qz; if(p[i].qz==p[i<<1].r-p[i<<1].l+1) p[i].qz+=p[i<<1|1].qz; p[i].hz=p[i<<1|1].hz; if(p[i].hz==p[i<<1|1].r-p[i<<1|1].l+1) p[i].hz+=p[i<<1].hz; } void build(int l,int r,int i) { p[i].l=l; p[i].r=r; if(p[i].l==p[i].r) { p[i].hz=p[i].mz=p[i].qz=1; return ; } int mid=(l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1); //p[i].hz=p[i].mz=p[i].qz=(r-l+1); // up(i); } void down(int i) { if(p[i].lazy==0) return; if(p[i].lazy==1) { p[i<<1].lazy=p[i<<1|1].lazy=1; p[i<<1].mz=p[i<<1].qz=p[i<<1].hz=p[i<<1].r-p[i<<1].l+1; p[i<<1|1].mz=p[i<<1|1].qz=p[i<<1|1].hz=p[i<<1|1].r-p[i<<1|1].l+1; } else { p[i<<1].lazy=p[i<<1|1].lazy=2; p[i<<1].mz=p[i<<1].qz=p[i<<1].hz=0; p[i<<1|1].mz=p[i<<1|1].qz=p[i<<1|1].hz=0; } p[i].lazy=0; } int cha(int i,int x) { down(i); if(p[i].r-p[i].l+1==x&&p[i].mz==x) return p[i].l; if(p[i<<1].mz>=x) return cha(i<<1,x); if(p[i<<1].hz+p[i<<1|1].qz>=x) return p[i<<1].r-p[i<<1].hz+1; if(p[i<<1|1].mz>=x) return cha(i<<1|1,x); return 0; } void xiu(int l,int r,int i,int k) { if(r<p[i].l||l>p[i].r) return; if(l<=p[i].l&&p[i].r<=r) { if(k==1) { p[i].mz=p[i].qz=p[i].hz=p[i].r-p[i].l+1; p[i].lazy=1; } else { p[i].mz=p[i].qz=p[i].hz=0; p[i].lazy=2; } return ; } down(i); xiu(l,r,i<<1,k); xiu(l,r,i<<1|1,k); up(i); } int n,m; int main(){ scanf("%d%d",&n,&m); build(1,n,1); for(ri i=1;i<=m;i++) { int opt; scanf("%d",&opt); if(opt==1) { int x; scanf("%d",&x); int ans=cha(1,x); printf("%d\n",ans); if(ans) xiu(ans,ans+x-1,1,2); } else { int L,R; scanf("%d%d",&L,&R);// xiu(L,L+R-1,1,1); } } }
例题：懒标记的重要：
Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面. 刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态. 奶牛们执行M (1 <= M <= 100,000)条指令, 每个指令都是两个整数中的一个(0 <= 指令号 <= 1). 第1种指令(用0表示)包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 它们表示起始开关和终止开关. 奶牛们只需要把从S_i到E_i之间的按钮都按一次, 就可以完成这个指令. 第2种指令(用1表示)同样包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 不过这种指令是询问从S_i到E_i之间的灯有多少是亮着的. 帮助FJ确保他的奶牛们可以得到正确的答案. 输入 第 1 行: 用空格隔开的2个整数N和M 第 2..M+1 行: 每行表示一个操作, 有3个用空格分开的整数: 指令号, S_i 和 E_i 输出 第 1..询问的次数 行: 对于每一次询问, 输出询问的结果. 样例输入 Copy 4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4 样例输出 Copy 1 2
代码（错误代码）：
#include <bits/stdc++.h> using namespace std; const int N = 100400; const int M = 100000; #define ri register int struct settree{ int l,r,sum,lazy,num; }p[N*4+5]; int val[N]; int n; void build(int l,int r,int i) { p[i].l=l; p[i].r=r; if(l==r) { return ; } int mid=(l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1); } void down(int i) { if(p[i].lazy==0) return; p[i<<1].lazy+=p[i].lazy; p[i<<1|1].lazy+=p[i].lazy; /////////// p[i<<1].num+=p[i].lazy; p[i<<1|1].num+=p[i].lazy; if(p[i<<1].num%2==1) p[i<<1].sum=p[i<<1].r-p[i<<1].l+1; else p[i<<1].sum=0; if(p[i<<1|1].num%2==1) p[i<<1|1].sum=p[i<<1|1].r-p[i<<1|1].l+1; else p[i<<1|1].sum=0; p[i].lazy=0; } void build2(int i) { if(p[i].l==p[i].r) { val[p[i].l]=p[i].sum; return ; } down(i); build2(i<<1); build2(i<<1|1); } void xiu(int l,int r,int i) { if(l>p[i].r||r<p[i].l) return; if(l<=p[i].l&&p[i].r<=r) { p[i].lazy++; p[i].num++; if(p[i].num%2==1) p[i].sum=(p[i].r-p[i].l+1); else p[i].sum=0; return ; } down(i); xiu(l,r,i<<1); xiu(l,r,i<<1|1); p[i].sum=p[i<<1].sum+p[i<<1|1].sum; } int ans; int cha(int l,int r,int i) { if(l>p[i].r||r<p[i].l) return 0; if(l<=p[i].l&&p[i].r<=r) { return p[i].sum; } down(i); return cha(l,r,i<<1)+cha(l,r,i<<1|1); } int m; int main(){ scanf("%d",&n); build(1,n,1); scanf("%d",&m); for(ri i=1;i<=m;i++) { int L,R,X; int opt; scanf("%d",&opt); if(opt==0) { scanf("%d%d",&L,&R); xiu(L,R,1); } else { scanf("%d%d",&L,&R); printf("%d\n",cha(L,R,1)); } } }
正确代码：
#include <bits/stdc++.h> using namespace std; const int N = 100400; const int M = 100000; #define ri register int struct settree{ int l,r,sum,lazy,num; }p[N*4+5]; int val[N]; int n; void build(int l,int r,int i) { p[i].l=l; p[i].r=r; if(l==r) { return ; } int mid=(l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1); } void down(int i) { if(p[i].lazy==0) return; p[i<<1].lazy^=1; p[i<<1|1].lazy^=1; /////////// p[i<<1].sum=p[i<<1].r-p[i<<1].l+1-p[i<<1].sum; p[i<<1|1].sum=p[i<<1|1].r-p[i<<1|1].l+1-p[i<<1|1].sum; p[i].lazy=0; } void build2(int i) { if(p[i].l==p[i].r) { printf("%d",p[i].num%2); return ; } down(i); build2(i<<1); build2(i<<1|1); } void xiu(int l,int r,int i) { if(l>p[i].r||r<p[i].l) return; if(l<=p[i].l&&p[i].r<=r) { p[i].lazy^=1; p[i].sum=(p[i].r-p[i].l+1)-p[i].sum; return ; } down(i); xiu(l,r,i<<1); xiu(l,r,i<<1|1); p[i].sum=p[i<<1].sum+p[i<<1|1].sum; } int ans; int cha(int l,int r,int i) { if(l>p[i].r||r<p[i].l) return 0; if(l<=p[i].l&&p[i].r<=r) { return p[i].sum; } down(i); return cha(l,r,i<<1)+cha(l,r,i<<1|1); } int m; int main(){ scanf("%d",&n); build(1,n,1); scanf("%d",&m); for(ri i=1;i<=m;i++) { int L,R,X; int opt; scanf("%d",&opt); if(opt==0) { scanf("%d%d",&L,&R); xiu(L,R,1); } else { scanf("%d%d",&L,&R); printf("%d\n",cha(L,R,1)); } } }
啊