Problem Description
There are two groups of gangsters fighting with each other. The first group stands in a line, but the other group has a magic gun that can shoot a range [a, b], and everyone in that range will take a damage of c points. When a gangster
is taking damage, if he has already taken at least P point of damage, then the damage will be doubled. You are required to calculate the damage that each gangster in the first group toke.
To simplify the problem, you are given an array A of length N and a magic number P. Initially, all the elements in this array are 0.
Now, you have to perform a sequence of operation. Each operation is represented as (a, b, c), which means:
For each A[i] (a <= i <= b), if A[i] < P, then A[i] will be A[i] + c, else A[i] will be A[i] + c * 2.
Compute all the elements in this array when all the operations finish.
is taking damage, if he has already taken at least P point of damage, then the damage will be doubled. You are required to calculate the damage that each gangster in the first group toke.
To simplify the problem, you are given an array A of length N and a magic number P. Initially, all the elements in this array are 0.
Now, you have to perform a sequence of operation. Each operation is represented as (a, b, c), which means:
For each A[i] (a <= i <= b), if A[i] < P, then A[i] will be A[i] + c, else A[i] will be A[i] + c * 2.
Compute all the elements in this array when all the operations finish.
Input
The input consists several testcases.
The first line contains three integers n, m, P (1 <= n, m, P <= 200000),
denoting the size of the array, the number of operations and the magic number.
Next m lines represent the operations. Each operation consists of three integers a; b and c (1 <= a <= b <= n, 1 <= c <= 20).
The first line contains three integers n, m, P (1 <= n, m, P <= 200000),
denoting the size of the array, the number of operations and the magic number.
Next m lines represent the operations. Each operation consists of three integers a; b and c (1 <= a <= b <= n, 1 <= c <= 20).
Output
Print A[1] to A[n] in one line. All the numbers are separated by a space.
Sample Input
3 2 1 1 2 1 2 3 1
Sample Output
1 3 1题目意思是：第一行有三个数n,m,p,分别代表数组的大小，设制的次数，作为一个标准加值，然后有m组，第组有a,b,c三个数， [a,b]是范围。解题技巧：每个段设三个变量，当前段共同要再加的值ans,当前段的数组值最大max,和最小min. 因为当最大值小于p时，那么这 一段一定加c,当最小值大于等于p时，那么这一段一定同加2*c.否则就更新下去。 当更新到当前段属于要更新的范围 并且满足同加一个值的条件时，则停止往下更新，否则左右子节点的每个数先加上父节点的ans，再把父节点的ans=0, 当更新定完左右子节点时再更新父点的最大最小值。#include<stdio.h> #define N 200000 struct node { int ans,max,min;//ans为当前段共同要再加的值，max,min分别是最大值和最小值 }tree[4*N]; int min(int a,int b){return a<b?a:b;} int max(int a,int b){return a>b?a:b;} void biulde(int l,int r,int k)//初始化 { int m=(l+r)/2; tree[k].ans=0; tree[k].max=tree[k].min=0; if(l==r) return ; biulde(l,m,k*2); biulde(m+1,r,k*2+1); } void ADD(int k)//更新左右子节点 { tree[k*2].ans+=tree[k].ans; tree[k*2].max+=tree[k].ans; tree[k*2].min+=tree[k].ans; tree[k*2+1].ans+=tree[k].ans; tree[k*2+1].max+=tree[k].ans; tree[k*2+1].min+=tree[k].ans; } int p; void updata(int L,int R,int c,int l,int r,int k) { int m=(l+r)/2; if(L<=l&&r<=R&&(tree[k].min>=p||tree[k].max<p))//当前段同加一种值 { if(tree[k].max<p) {tree[k].ans+=c;tree[k].max+=c;tree[k].min+=c;} else {tree[k].ans+=2*c;tree[k].max+=2*c;tree[k].min+=2*c;} return ; } ADD(k); if(L<=m) updata(L,R,c,l,m,k*2); if(R>m) updata(L,R,c,m+1,r,2*k+1); tree[k].ans=0;//重制为0 tree[k].max=max(tree[k*2].max,tree[k*2+1].max); tree[k].min=min(tree[k*2].min,tree[k*2+1].min); } void print(int l,int r,int k) { int m=(l+r)/2; if(l==r) { if(l==1) printf("%d",tree[k].ans); else printf(" %d",tree[k].ans); return ; } ADD(k); print(l,m,k*2); print(m+1,r,k*2+1); } int main() { int n,m,c,L,R; while(scanf("%d%d%d",&n,&m,&p)>0) { biulde(1,n,1); while(m--) { scanf("%d%d%d",&L,&R,&c); updata(L,R,c,1,n,1); } print(1,n,1); printf("\n"); } }