8
HDU1556 Color the ball（树状数组 区间更新）
source link: https://arminli.com/hdu1556/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU1556 Color the ball（树状数组 区间更新）
March 05, 2016
对于每次对[a, b]的涂色，做如下更新：add(a, 1)和 add(b+1, -1)。前缀和就代表了涂色次数。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int n;
int a[100005];
int lowbit(int x){
return x&(-x);
}
void add(int pos , int num){
while(pos <= n){
a[pos] += num;
pos += lowbit(pos);
}
}
int sum(int n){
int sum = 0;
while(n > 0){
sum += a[n];
n -= lowbit(n);
}
return sum;
}
int main(){
//freopen("a.txt", "r", stdin);
while(~scanf("%d", &n) && n){
memset(a, 0, sizeof(a));
for(int j = 0; j < n; j++){
int x, y;
scanf("%d %d", &x, &y);
add(x, 1);
add(y+1, -1);
}
for(int i = 1; i <= n; i++){
cout << sum(i);
if(i != n) cout << " ";
}
cout <<endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK