题目背景
面对蚂蚁们的疯狂进攻，小 FF 的 Tower defence 宣告失败……人类被蚂蚁们逼到了 Greed Island 上的一个海湾。现在，小 FF 的后方是一望无际的大海，前方是变异了的超级蚂蚁。小 FF 还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造 SCV 布置地雷以阻挡蚂蚁们的进攻。
题目描述
小 FF 最后一道防线是一条长度为 𝑛n 的战壕，小 FF 拥有无数多种地雷，而 SCV 每次可以在 [𝐿,𝑅] 区间埋放同一种不同于之前已经埋放的地雷。由于情况已经十万火急，小 FF 在某些时候可能会询问你在 [𝐿′,𝑅′] 区间内有多少种不同的地雷，他希望你能尽快的给予答复。
输入格式
第一行为两个整数 𝑛 和 𝑚，𝑛 表示防线长度，𝑚 表示 SCV 布雷次数及小 FF 询问的次数总和。
接下来有 𝑚m 行，每行三个整数 𝑞,𝑙,𝑟q,l,r：
- 若 𝑞=1，则表示 SCV 在 [𝑙,𝑟] 这段区间布上一种地雷；
- 若 𝑞=2，则表示小 FF 询问当前 [𝑙,𝑟] 区间总共有多少种地雷。
输出格式
对于小 FF 的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。
输入输出样例
输入 #1
5 4
1 1 3
2 2 5
1 2 4
2 3 5输出 #1
1
2说明/提示
数据规模与约定
- 对于 30% 的数据，0≤𝑛，𝑚≤1000。
- 对于 100%的数据，0≤𝑛，𝑚≤
。
- 【利用差分数组统计地雷数，那么所求答案 ( 右端点之前的所有区间开头数（包括右端点）—— 左端点之前的所有区间结尾数（不包括左端点） ) 】
参考代码：
#include<bits/stdc++.h> #define int long long const int N=4e5+5; using namespace std; struct node{ int zhi,l,r; }w[N][2]; int n,m,k,a,b,a1[N],lazy1[N][2],lazy2[N],p,c; void build(int k,int l,int r,int t) { w[k][t].l=l;w[k][t].r=r; if(l==r) { w[k][t].zhi=a1[l]; return; } int mid=l+r>>1; build(k*2,l,mid,t); build(k*2+1,mid+1,r,t); w[k][t].zhi=w[k*2][t].zhi+w[k*2+1][t].zhi; } void biao(int k,int v,int t) { lazy1[k][t]+=v; w[k][t].zhi+=v*(w[k][t].r-w[k][t].l+1); return; } void xiaochuan(int k,int t) { if(lazy1[k][t]==0)return; biao(k*2,lazy1[k][t],t); biao(k*2+1,lazy1[k][t],t); lazy1[k][t]=0; } void jia(int k,int l,int r,int v,int t) { if(l<=w[k][t].l&&r>=w[k][t].r) { biao(k,v,t);return; } int mid=w[k][t].l+w[k][t].r>>1; xiaochuan(k,t); if(l<=mid) jia(k*2,l,r,v,t); if(r>=mid+1) jia(k*2+1,l,r,v,t); w[k][t].zhi=w[k*2][t].zhi+w[k*2+1][t].zhi; } int qiu(int k,int yl,int yr,int t) { if(yl<=w[k][t].l&&yr>=w[k][t].r)return w[k][t].zhi; int mid=w[k][t].l+w[k][t].r>>1; int ans=0; xiaochuan(k,t); if(mid>=yl) ans+=qiu(k*2,yl,yr,t); if(mid+1<=yr) ans+=qiu(k*2+1,yl,yr,t); return ans; } signed main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; build(1,1,n,1);build(1,1,n,0); for(int i=1;i<=m;i++) { cin>>k>>a>>b; if(k&1) { jia(1,a,a,1,0); jia(1,b,b,1,1); } else cout<<qiu(1,1,b,0)-qiu(1,1,a-1,1)<<'\n'; } // for(int i=1;i<=15;i++) // cout<<i<<" "<<lazy1[i]<<" "<<lazy2[i]<<'\n'; return 0; }