Description
夫子将人间之气注入桑桑体内后，便再也无法隐瞒踪迹，昊天终于发现了他。 “恭请夫子显圣！” 西陵神国桃山最高处，庄严肃穆的神殿外，石坪上跪着黑压压的人群，往常骄横的红衣神官和神殿执事们。就像最虔诚的信徒，以额触地。 “恭请夫子显圣！” 极西荒原深处，天坑中央的巨峰之巅。悬空寺讲经首座的手中没有握着锡杖，而是诚心诚意地双手合什，无比恭敬地祝祷着。 遥远的南海某处。 青衣道人沉默看着陆地的方向，脸上的神情显得异常凝重。 他没有说那句话，因为他很紧张。 他看到一道大幕正在缓缓落下。 为了这一刻，他已经等待了太长时间，不到最后，他无法放心。
泗水畔。 黑色的罩衣在空中飘舞，夫子乘风而上。 桑桑随之而去，无数光明金花，从她的身体里溢出，洒向人间。 陈皮皮跪在知守观里的湖畔，对着天空不停流泪，双肩塌着，身体不停颤抖，眼睛哭到红肿，就像被雪迷了眼睛的兔子。 中年道人站在他身后，叹息安慰说道：“夫子既然已经显圣登天，那么你父亲便可以回来，至少这算是一件好事……陈皮皮的父亲是知守观观主。 他叫陈某，无数年来身上都是一袭青色道衣，故号青衣道人。 。。。 夫子升天后 ， 陈某回来了。开始了举世伐唐。 现在唐国情况危急，北方的金帐王国 ， 南方的晋国 ， 西方的月轮国兵员调动密集 ， 一时间唐国边境线上烽火重重。 已知唐国边境上共有 n 个关卡 ， 编号为别为 1 ... n。你现在是唐国军机处的一员情报人员 ， 在你面前共有 m 份情报 ，每份情报有两个数 L , R表示有一股兵力将要袭击 L 到 R 区间里的所有关卡 ，对于每个关卡 ，每被袭击一次他的危险度就加一。Input
t（ t<= 5）代表有 t 组数据.每组数据 先输入 n ， m(n<=100000 m<=100000) ， 然后输入 m 行 ， 每行 两个数 L , R(1<= L <= R <= n). Output
输出所有关卡里危险度最高的关卡的危险度。Sample Input
2 2 3 1 2 1 1 2 2 5 5 1 2 1 2 1 2 1 5 1 5 Sample Output
2 5
一看就是线段树吧 【ps 手感还不错，稍微调试点一次就过了，平常要调试半天 TAT 】
代码
#include<bits/stdc++.h> #define ll o<<1 #define rr o<<1|1 #define lson o<<1,le,mid #define rson o<<1|1,mid+1,ri #define LL long long using namespace std; const int MAXN =100000+10; const int MAXM = 200000; struct Tree{// 线段树 int l,r,lazy,maxx; }tree[MAXN<<2]; void up(int o){ tree[o].maxx=max(tree[ll].maxx,tree[rr].maxx); } void down(int o){ if(tree[o].lazy){ tree[ll].lazy+=tree[o].lazy; tree[ll].maxx+=tree[o].lazy; tree[rr].lazy+=tree[o].lazy; tree[rr].maxx+=tree[o].lazy; tree[o].lazy=0; } } void build(int o,int le,int ri){ tree[o]={le,ri,0,0}; if(le==ri) return ; int mid=(le+ri)>>1; build(lson); build(rson); up(o); } void update(int o,int le,int ri,int val){ if(tree[o].l>=le&&tree[o].r<=ri) { tree[o].maxx+=val; tree[o].lazy+=val; return ; } down(o); int mid=(tree[o].l+tree[o].r)>>1; if(le>mid) update(rr,le,ri,val); else if(ri<=mid) update(ll,le,ri,val); else { update(ll,le,mid,val); update (rr,mid+1,ri,val); } up(o); } int query(int o,int le,int ri){ down(o); if(tree[o].l>=le&&tree[o].r<=ri) return tree[o].maxx; int mid=(tree[o].l+tree[o].r)>>1; if(le>mid) query(rr,le,ri); else if(ri<=mid) query(ll,le,ri); else return max(query(ll,le,mid),query(rr,mid+1,ri)) ; } int main(){ int t;cin>>t; while(t--){ int n,m;cin>>n>>m; build(1,1,n); int a,b; while(m--){ scanf("%d%d",&a,&b); update(1,a,b,1); } //puts("-======="); int ans=query(1,1,n); printf("%d\n",ans); } return 0; }