暑假杭二day3测试总结"/>
2019暑假杭二day3测试总结
2019暑假杭二day3测试总结
- 前言
- T1
- 题目大意
- sol
- T2
- 题目大意
- sol
- T3
- 题目大意
- sol
前言
Day3居然考了三到线段树+离散化,是数据结构专场吗?我虽然都想出了正解,却还是犯了一些傻逼错误。
T1
题目大意
给定一条白色的直线,有 n n n个操作,每次将 l , r l,r l,r这一段染成黑色,染完后回答还有多少条黑色的线段 ( 0 < = n < = 2 ∗ 1 0 5 , − 1 0 9 < = l < = r < = 1 0 9 ) (0<=n<=2*10^5,-10^9<=l<=r<=10^9) (0<=n<=2∗105,−109<=l<=r<=109)。
sol
把区间离散化后用线段树维护,维护每段区间有多少条线段,以及左右能否超出区间,大区间的线段数先等于左右区间线段数之和,如果左区间向右和右区间向左都超出了,说明左右有一条线段连起来了,线段数再减一。
T2
题目大意
在一条数轴上有 n n n个点,第 i i i个点坐标为 x i xi xi。有 m m m个操作,每个操作都是下面两种之一:
- p , y p,y p,y表示将初始标号为 p p p的点坐标改为 y y y。
- l , r l,r l,r表示求出 ∑ l < = x i < = x j < = l ( x j − x i ) \sum_{l<=x_i<=x_j<=l}(x_j-x_i) ∑l<=xi<=xj<=l(xj−xi)。
sol
同样用线段树维护每段区间的答案, x x x之和,点的个数, a n s p = a n s p < < 1 + a n s p < < 1 ∣ 1 + s u m p < < 1 ∣ 1 ∗ c n t p < < 1 − s u m p < < 1 ∗ c n t p < < 1 ∣ 1 ans_p=ans_{p<<1}+ans_{p<<1|1}+sum_{p<<1|1}*cnt_{p<<1}-sum_{p<<1}*cnt_{p<<1|1} ansp=ansp<<1+ansp<<1∣1+sump<<1∣1∗cntp<<1−sump<<1∗cntp<<1∣1, x x x之和和点的个数比较好维护。
我在这一题犯了一些错误,我写了一个只能读正数的快读,结果样例都没过,还调了好久。然后我因为懒,没离散化,直接动态开点,数组却依然开的是 n l o g ( n ) nlog(n) nlog(n),不是 n l o g ( w ) nlog(w) nlog(w),RE了40分。数组的大小还是要好好算一下的。
T3
T3考了以前队测的原题,还是挺简单的。
题目大意
直接粘贴过来:
Bsny所在的精灵社区有n个居民,每个居民有一定的地位和年龄,ri表示第i个人的地位,ai表示第i个人的年龄。
最近社区里要举行活动,要求几个人分成一个小组,小组中必须要有一个队长,要成为队长有这样的条件:
- 队长在小组中的地位应该是最高的(可以并列第一);
- 小组中其他成员的年龄和队长的年龄差距不能超过K。
有些人想和自己亲密的人组在同一个小组,同时希望所在的小组人越多越好。比如x和y想在同一个小组,同时希望它们所在的小组人越多越好,当然,它们也必须选一个符合上述要求的队长,那么问你,要同时包含x和y的小组,最多可以组多少人?
sol
先将地位排序,再将年龄离散化,就可以用树状数组将每个人当队长队内最多可以有多少人处理出来。
code:
sort(c+1,c+1+n);sort(p+1,p+1+n,cmp);cnt=unique(c+1,c+1+n)-c-1;for(int i=1;i<=n;i++){if(p[i].r!=p[i-1].r)//a为年龄,r为地位for(;s<i;s++)f[s]=ask(ub(p[s].a+k)-1)-ask(lb(p[s].a-k)-1);add(lb(p[i].a));
//ask和add为树状数组,f为每个人当队长队内最多可以有多少人}for(;s<=n;s++)f[s]=ask(ub(p[s].a+k)-1)-ask(lb(p[s].a-k)-1);
之后将询问离线,按两人地位的 m a x max max为关键字降序排列,在处理每个答案之前,将地位大于等于他们地位 m a x max max的人的 f f f按那个人的年龄加到线段树里,处理答案直接在线段树里查询合法年龄区间的答案即可。
code:
int j=n;for(int i=1;i<=Q;i++){int x=q[i].r,y=q[i].a;//询问已经排过序while(j&&p[j].r>=p[x].r)change(1,1,cnt,lb(p[j].a),f[j]),j--;ans[q[i].id]=query(1,1,cnt,lb(max(p[x].a,p[y].a)-k),ub(min(p[x].a,p[y].a)+k)-1);}
更多推荐
2019暑假杭二day3测试总结
发布评论