HDU 1566 Color The Ball [Tree Array Interval Update] [Data Structure]

Subject link: http://acm.hdu.edu.cn/showproblem.php?pid=1556
——————————— —————-.
Color the ball

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission( s): 17629 Accepted Submission(s): 8823

Problem Description
N balloons are arranged in a row, numbered from left to right as 1, 2, 3…. N. Give each time Set two integers ab (a <= b), and lele will paint each balloon once in order from balloon a to balloon b to ride on his "Little Flying Pigeon" electric car. But after N times, Lele has forgotten that the first balloon has been painted several times. Can you help him figure out how many times each balloon has been painted?

Input
The first line of each test instance is an integer N, (N <= 100000). The next N lines, each line includes 2 integers ab(1 <= a <= b <= N).
When N = 0, the input ends.

Output
Each test instance outputs one line, including N integers, and the I-th number represents the total number of times the I-th balloon is painted.

Sample Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0

Sample Output
1 1 1
3 2 1

Author
8600

Source
HDU 2006-12 Programming Contest

—————————————————-.

The main idea of ​​the title:. . .

Question-solving ideas:

The question is very clear that it is an interval update, so I think about it.
Every time each value in the interval is +1, then consider the line segment tree and tree array in the data structure.
Here, the tree array method is used.
Here, just do it directly according to the meaning of the tree array,
because the tree array is nothing more than a dynamic prefix sum.
In this case, if a value is not updated, then all the following values ​​are also equivalent to update;
So the update interval can only be updated twice in a single point
For the interval (a, b)
Just update a by +1, and update b by -1;

Attach the code of this question
——————————————-.

#include #define abs(x) (((x)>0)?(x):-( x))#define lalal puts("*********")#define Rep(a,b,c) for(int a=(b);a<=(c);a++)#define Req(a,b,c) for(int a=(b);a>=(c);a--)#define Rop(a,b,c) for(int a=(b);a<(c) ;a++)#define s1(a) scanf("%d",&a)typedef long long int LL;using namespace std;const < span class="hljs-keyword">int inf = 0x3f3f3f3f;const int MOD = 9901;/**************************** **********/#define lowbit(x) (x&-x)const int N = 100000+5; int sum[N];void update(int index,int val){ for(int i=index;i<= N;i+=lowbit(i)) sum[i]+=val;}int getSum(int index){ int ans=0; for(int i=index;i>0;i-=lowbit(i)) ans+=sum[i]; return ans ;}int main(){ int n; while(~s1(n)&&n) {Rep(i,1,n) sum[i]=0; int a,b; Rep(i,1,n){ s1(a),s1(b); update(a, 1); update(b+1,-1);} Rop(i,1,n) printf("%d ",getSum( i)); printf("%d
",getSum(n));} return < span class="hljs-number">0;}