首页 > 代码库 > HDU-3577-Fast Arrangement-区间更新
HDU-3577-Fast Arrangement-区间更新
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3577
好吧,我认为这道题有必要说一下题目意思;毕竟我刚開始是没有看太懂,原谅我这个英语渣渣。。。ORZ.....
题意:输入一个t,表示有t组測试数据;
接下来一行,输入两个数,k。m,当中k表示这个辆车最多能够坐这么多人,m表示有m次询问是否能上车;
每一次询问。输入两个数a,b,表示该乘客是否能在a站台上车,b站台下车。乘车区间为(a,b--),先后次序;
即我每次询问。你就推断在a站台处将会有多少人还在车上,小于k则表示可以上车,更新数据。反之不能上车;
这到题要注意的是,尽管是考线段树的区间更新,可是得用到lazy思想,否则非常显然的会TLE;
事实上也非常easy理解,每当我找到全然重合的区间,我就不往下找了,先保存子节点要更新的数据,当我下次要用的时候,用一层,更新一层,
这就好比方说,我如今找第一层,发现没有找到全然重合的区间。那么我就利用之前保存的数据更新一下我下一层的数据。然后我再找下一层。以此类推;
当然,链接:http://www.douban.com/note/273509745/这里有简单的介绍Lazy思想,不懂的能够去看看;
好了,直接看代码吧;
#include<iostream> #include<string> #include<queue> #include<map> #include<set> #include<vector> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int N=1000005; int ans[N]; struct node { int l,r,v,lazy; }node[N<<2]; // 线段树的空间大概是数组空间的4倍。 void build(int l,int r,int numb) // 线段树的建立; { node[numb].l=l; node[numb].r=r; node[numb].v=0; node[numb].lazy=0; // 用了lazy思想。提高了效率。 if(l==r) return; int mid=(l+r)>>1; build(l,mid,numb<<1); build(mid+1,r,numb<<1|1); } void PushUp(int numb) // 往上往父节点方向更新数据;可是这里不是左右儿子的和。而是最大值。由于是站台人数。 { node[numb].v=max(node[numb<<1].v,node[numb<<1|1].v); } void PushDown(int numb) // 向下往左右儿子方向更新数据; { node[numb<<1].lazy+=node[numb].lazy; node[numb<<1|1].lazy+=node[numb].lazy; node[numb<<1].v+=node[numb].lazy; node[numb<<1|1].v+=node[numb].lazy; node[numb].lazy=0; // 更新完了要清零; } void Insert(int l,int r,int numb) // 插入更新数据; { if(node[numb].l==l&&node[numb].r==r) // 假设区间全然重合,则不须要再往下更新了,先保存起来,能够节约非常多的时间(lazy思想) { node[numb].v+=1; node[numb].lazy+=1; return; } if(node[numb].lazy) PushDown(numb); // 由于没有找到全然重合的区间,所以要先更新下一层区间; int mid=(node[numb].r+node[numb].l)>>1; if(l>mid) Insert(l,r,numb<<1|1); else if(r<=mid) Insert(l,r,numb<<1); else{ Insert(l,mid,numb<<1); Insert(mid+1,r,numb<<1|1); } PushUp(numb); // 最后还得往上返回,更新父节点区间。 } int query(int l,int r,int numb) // 查询区间l到r。 { if(node[numb].l==l&&node[numb].r==r){ return node[numb].v; } if(node[numb].lazy) PushDown(numb); // 道理同48行; int mid=(node[numb].r+node[numb].l)>>1; if(l>mid) return query(l,r,numb<<1|1); else if(r<=mid) return query(l,r,numb<<1); else{ return max(query(l,mid,numb<<1),query(mid+1,r,numb<<1|1)); // 道理同28行; } } int main() { int t,Case=1,len=0,k,m,a,b; scanf("%d",&t); while(t--){ len=0; memset(ans,0,sizeof(ans)); scanf("%d%d",&k,&m); build(1,1000000,1); for(int i=0;i<m;i++){ scanf("%d%d",&a,&b); b--; // 这里有一个问题,就是乘客从a上车,b下车,所以乘客在车上的区间为(a,b--); if(query(a,b,1)<k){ // 表示能够上车; ans[len++]=i+1; Insert(a,b,1); } } printf("Case %d:\n",Case++); for(int i=0; i<len; i++) // 格式问题害我又WA了一次; printf("%d ",ans[i]); printf("\n\n"); } return 0; }
HDU-3577-Fast Arrangement-区间更新
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。