首页 > 代码库 > hdu4970(线性区间更新的懒操作)
hdu4970(线性区间更新的懒操作)
思路是求出从每一点出发走到终点分别要受到多少伤害，然后和每个怪兽的血量比一下。给一个数组，告了哪些区间需要更新，我需要的就是都更新以后每个点的伤害值是多少。不涉及到区间查询，没必要用线段树或树状数组（据说用了也会超时。。）。如果每个区间都一个for循环把对应的几个数更新了，必然超时。那么这里的技巧就是一种懒操作。需要a[l]到a[r]每个加d，那么我就标记a[l]+=d;a[r+1]-=d;几组更新都标好了以后，扫一遍数组，把这些信息加上就行了。时间复杂度O(n)。
这种技巧非常实用。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long intconst int maxn=100009;int n,m,k,a[maxn],l,r,d,x[maxn];LL h[maxn],f[maxn];int main(){ //freopen("in6.txt","r",stdin); while(scanf("%d",&n)==1&&n) { memset(a,0,sizeof(a)); memset(f,0,sizeof(f)); scanf("%d",&m); for(int i=1; i<=m; i++) { scanf("%d%d%d",&l,&r,&d); a[l]+=d; a[r+1]-=d; } int t=0; for(int i=1; i<=n; i++) { if(a[i]!=0) { t+=a[i]; a[i]=t; } else a[i]+=t; } for(int i=n; i>=1; i--) { f[i]=f[i+1]+a[i]; } //for(int i=1;i<=n;i++) cout<<a[i]<<‘,‘<<f[i]<<endl; int ans=0; scanf("%d",&k); for(int i=1; i<=k; i++) { scanf("%I64d%d",&h[i],&x[i]); if(f[x[i]]<h[i]) ans++; } printf("%d\n",ans); } return 0;}
hdu4970(线性区间更新的懒操作)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。