线段树+区间处理) 57行代码搞定~"/>
SDUT 2880 第五届山东省ACM省赛 Devour Magic (线段树+区间处理) 57行代码搞定~
传送门:SDUT 2880
题目大意:
数轴上有从 1~n 的 n ( 1<= n <= 1e5)个点,每个点每单位时间会增加 1 单位法力,给出某个人按时间顺序的 m 次操作,每次操作都会在时间 t 时把区间 [ l , r ] 内的法力都收走,问他收走的法力和是多少。
思路:
对于每个点,从这个点所收走的法力之和等于最后一次从它那收走的时间(自己想想为什么)。
又由于 m 次操作是按时间顺序给出的,所以我们可以将区间内的点按照时间顺序“染色”,每次染色的值为操作的时间 t。这样一来,每个点就保存了最后一次操作的时间所对应的颜色。
我们要计算结果只需要用 O(n) 的时间把每个点的值相加即可。这个时间不多,耗时的是将区间染色的操作,我们可以利用线段树解决,有点类似于线段树求区间和的操作。
具体实现:
我们可以用线段树的点的 col 属性来记录每个点的“颜色”,即最后一次操作的时间。由于每次对区间染色,所以每次将 col 进行延迟操作(为了节省时间)。由于没直接记录每个点的颜色,所以需要用 query 函数递归查询每个点的颜色,并将点的颜色值相加即结果。
注:
1. 我看网上好多方法是模拟的思路,每次取完都要清空区间,这样比较麻烦一点。
2. 这个题和 poj 2528 很像,poj 2528 的意思是在一个板子上贴海报,给出海报的区间,问最后有多少个海报可见(有一部分能看见即可见)。
代码:
#include<stdio.h>
#include<string.h>
typedef long long LL;//注意a数组开4倍,col数组开16倍
int a[100010*4],col[100010*16];void pushdown(int root)
{ //延迟标记 //让左右子树的根节点染色为当前根节点的染色 col[root<<1]=col[root<<1|1]=col[root]; col[root]=0; //当前节点设为未染色
}void update(int root,int L,int R,int l,int r,int x)
{ //更新函数,参数为:根,大区间,所查询区间, 染第x种色 if(l<=L&&r>=R){ //如果当前区间在查询区间内,则染色 col[root]=x;return;}if(col[root]!=0) pushdown(root);int mid=(L+R)>>1;if(mid>=l) update(root<<1,L,mid,l,r,x); //更新左子树 if(mid<r) update(root<<1|1,mid+1,R,l,r,x); //更新右子树
}LL query(int root,int L,int R,int l,int r)
{ //查询函数,参数为:根,大区间,所查询区间LL ans=0;if(L==R) return col[root];if(col[root]!=0) pushdown(root); //延迟标记 int mid=(L+R)>>1;if(mid>=l) ans+=query(root<<1,L,mid,l,r); //查询左子树 if(mid<r) ans+=query(root<<1|1,mid+1,R,l,r); //查询右子树 return ans;
}int main()
{int i,t,n,m,l,r,color;scanf("%d",&t);while(t--){memset(col,0,sizeof(col)); //初始化,相当于建树 scanf("%d%d",&n,&m); for(i=0;i<m;i++){scanf("%d%d%d",&color,&l,&r);update(1,1,n,l,r,color); //更新区间的颜色 } //用query函数递归查询每个点的颜色并相加 LL ans=query(1,1,n,1,n);printf("%lld\n",ans);}return 0;
}
更多推荐
SDUT 2880 第五届山东省ACM省赛 Devour Magic (线段树+区间处理) 57行代码搞定~
发布评论