“做专题也要按照基本法”——蛤
离开了诡异的村庄，卿学姐来到了威廉·圣·乱七八糟王国，这里的国王咸鱼王是个智障。
国家涣散，盗贼四起，民不聊生。
见到这样的景象，卿学姐不禁潸然泪下，“悠悠苍天，奈何苦了苍生”。
自幼学习基本法的卿学姐决定向整个国家普及基本法，改善国家法度。
在这个国家总共有 N N个人，每个人都有一个编号，编号从1开始。
由于整个国家的人实在是太多了，卿学姐每次只能对一个连续区间的编号的人普及基本法。
同时卿学姐还想知道在某个时刻某个区间还有多少人没有被普及基本法。
第一行两个整数 N,Q N,Q，表示总共有 N N个人，并且有 Q Q次事件。
接下来 Q Q行，每行三个整数 t,L,R t,L,R。如果 t t是 1 1，代表在这时，卿学姐向闭区间 L,R L,R的人普及基本法。如果 t t是 2 2，代表在这时，卿学姐想知道闭区间 L,R L,R里面有多少人还没有被普及基本法。
1≤N≤100000000 1≤N≤100000000
1≤Q≤100000 1≤Q≤100000
1≤t≤2 1≤t≤2
1≤L≤R≤N 1≤L≤R≤N
输出每个卿学姐想知道的答案
题解：看题目想到线段树，但是因为数据范围太大，显然不能直接使用线段树，所以这里应该加上离散化操作
代码如下：
#include <iostream> #include <bits/stdc++.h> using namespace std; const int maxn=100005; int c[2*maxn],kind[maxn],tree[8*maxn],lazy[8*maxn]; int cl[maxn],cr[maxn]; map<int, int> ys; void push_up(int rt) { tree[rt]=tree[rt<<1]+tree[rt<<1|1]; //cout<<rt<<' '<<tree[rt]; } void push_down(int rt) { tree[rt<<1]=tree[rt<<1|1]=0; lazy[rt<<1]=lazy[rt<<1|1]=1; lazy[rt]=0; } void build(int l,int r,int rt) { if(l==r) { tree[rt]=c[l]-c[l-1]; //cout<<l<<' '<<tree[rt]<<endl; lazy[rt]=0; return; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); push_up(rt); } void update(int l,int r,int L,int R,int rt) { if(l>=L&&r<=R){ tree[rt]=0; lazy[rt]=1; //cout<<l<<' '<<r<<' '<<tree[rt]<<endl; return; } if(lazy[rt]) push_down(rt); int mid=(l+r)>>1; if(L<=mid) update(l,mid,L,R,rt<<1); if(R>=mid+1) update(mid+1,r,L,R,rt<<1|1); push_up(rt); } int query(int l,int r,int L,int R,int rt) { //cout<<l<<r<<endl; //cout<<tree[rt]<<endl; if(l>=L&&r<=R) return tree[rt]; if(lazy[rt]) push_down(rt); int mid=(l+r)>>1; int ans=0; if(L<=mid) ans+=query(l,mid,L,R,rt<<1); if(R>=mid+1) ans+=query(mid+1,r,L,R,rt<<1|1); push_up(rt); return ans; } int main() { int n,q; cin>>n>>q; int cnt=0; int cc=0; int qq=1; for(int i=0;i<q;i++) { int kind1,l,r; scanf("%d %d %d",&kind1,&l,&r); c[++cnt]=l; c[++cnt]=r; cl[cc]=l; cr[cc]=r; kind[cc]=kind1; cc++; } sort(c+1,c+cnt); cnt=unique(c+1,c+cnt)-c-1; for(int i=cnt;i>0;i--) { if(c[i-1]+1!=c[i]) c[++cnt]=c[i-1]+1; //cout<<i<<' '<<c[i]<<endl; } sort(c+1,c+cnt+1); if(c[cnt]!=n) c[++cnt]=n; for(int i=1;i<=cnt;i++){ ys[c[i]]=i; } build(1,cnt,1); for(int i=0;i<q;i++) { //cout<<kind[i]<<' '<<ys[cl[i]]<<' '<<ys[cr[i]]<<endl; if(kind[i]==1) update(1,cnt,ys[cl[i]],ys[cr[i]],1); else if(kind[i]==2) { int ans=query(1,cnt,ys[cl[i]],ys[cr[i]],1); printf("%d\n",ans); } } //cout << "Hello world!" << endl; return 0; }