/* 操作a b c:[a,b]区间上的节点加上c,若节点的值已经超过P(包括等于),则加上2*c 最后求每个节点的值 和hdu3954很类似,具体参考:http://blog.csdn.net/wsniyufang/article/details/6702560 每个区间设定min_dis; 当区间中有一个点超过P时,释放lazy */ using namespace std; const int N=200001; int n,m,P; struct Node { int L,R;//区间左右边界 int level,exp;//点的等级,1为正常,2为伤害超过P后的等级,exp为当前的伤害 (这两个属性只有叶子节点有) int min_dis;//本区间存在中的点和P最小距离(不含已经超过P的) int lazy;//本区间还有多少伤害没有释放到其子树 }tree[4*N]; inline void search_up(int t)//向上更新节点的信息 { int nl=2*t,nr=2*t+1; tree[t].min_dis=min(tree[nl].min_dis,tree[nr].min_dis); // tree[t].exp=max(tree[nl].exp,tree[nr].exp); // tree[t].level=max(tree[nl].level,tree[nr].level); } void create(int t,int L,int R)//建树 { tree[t].L=L; tree[t].R=R; tree[t].lazy=0; tree[t].level=1; tree[t].exp=0; tree[t].min_dis=P; if(L==R)//叶子节点 { return ; } // tree[t].min_dis<<30; int mid=(L+R)>>1; create(t<<1,L,mid); create((t<<1)+1,mid+1,R); } inline void down(int t)//将t的lazy值释放到其子树 { int nl=t<<1,nr=(t<<1)+1; if(tree[nl].L==tree[nl].R)//叶子节点要计算exp tree[nl].exp+=tree[nl].level*tree[t].lazy; tree[nl].lazy+=tree[t].lazy; tree[nl].min_dis-=tree[t].lazy; if(tree[nr].L==tree[nr].R) tree[nr].exp+=tree[nr].level*tree[t].lazy; tree[nr].lazy+=tree[t].lazy; tree[nr].min_dis-=tree[t].lazy; tree[t].lazy=0; } void update(int t,int L,int R,int val) { int mid=(tree[t].R+tree[t].L)>>1,nl=t<<1,nr=(t<<1)+1; if(tree[t].L==tree[t].R)//如果为叶子节点,更新其等级、经验和min_dis { tree[t].exp+=tree[t].level*val; if(tree[t].exp>=P) { tree[t].level=2; tree[t].min_dis=1<<30; } else { tree[t].min_dis=P-tree[t].exp; } return ; } if(tree[t].L==L&&tree[t].R==R) { if(val>=tree[t].min_dis)//本区间有点要升级,释放区间的lazy { down(t); update(nl,tree[nl].L,tree[nl].R,val);//将本次系数下放,递归到区间没有超过P的叶子节点为止 update(nr,tree[nr].L,tree[nr].R,val); search_up(t);//向上维护t的信息 } else //本区间没有要升级的点 { tree[t].min_dis-=val; tree[t].lazy+=val; } return ; } if(tree[t].lazy)//向下松弛操作 { down(t); } if(R<=mid) update(nl,L,R,val); else if(L>mid) update(nr,L,R,val); else { update(nl,L,mid,val);update(nr,mid+1,R,val);} search_up(t);//每次update后必有search_up,因为t的子节点更新后,t的dis_min都有可能改变 } int ans[N]; void query(int t,int L,int R) { int nl=t<<1,nr=(t<<1)+1; int mid=(tree[t].R+tree[t].L)>>1,tmp; if(tree[t].L==L&&tree[t].R==R&&L==R) { ans[L]=tree[t].exp; return ; } if(tree[t].lazy)//向下松弛操作 { down(t); } if(R<=mid)query(nl,L,R); else if(L>mid)query(nr,L,R); else {query(nl,L,mid),query(nr,mid+1,R);} return ; } //优化输入 inline int nextInt() { char c; while (c = getchar(), c < '0' || c > '9'); int r = c - '0'; while (c = getchar(), c >= '0' && c <= '9') r = r * 10 + c - '0'; return r; } int main() { int L,R,Case,de,ti,temp; char op[3]; while(scanf("%d%d%d",&n,&de,&P)!=EOF) { create(1,1,n); while(de--) { L=nextInt(); R=nextInt(); temp=nextInt(); update(1,L,R,temp); } query(1,1,n); for(int i=1;i<n;i++) printf("%d ",ans[i]); printf("%d\n",ans[n]); } }