[hdoj1556]Color the ball

Color the ball

题意

给定$n$次操作,吧$l,r$区间内+1,最后问每个点是多少。

题解

树状数组骚操作。

既然我单点更新只能更新一个点,那么我就更新$l$点加上1,之后$r+1$的点减1,那么我对于在区间中的点,求得就是他之前$l$出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
const int maxn = 1e5 + 10;
int bit[maxn];
int lowbit(int x){return x&-x;}
void update(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
bit[i] += val;
}
}
int sum(int x){
int res = 0;
for(int i=x;i;i-=lowbit(i)){
res += bit[i];
}
return res;
}
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
while(scanf("%d",&n) && n){
memset(bit,0,sizeof(int)*(n+1));
rep(i,0,n){
int a,b;scanf("%d%d",&a,&b);
update(a,1);update(b+1,-1);
}
rep(i,1,n+1){
printf("%d%c",sum(i),i==n?'\n':' ');
}
}
return 0;
}