[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;
}