Color the ball HDU - 1556

文章目录

解法一解法二解法三 N个气球排成一排，从左到右依次编号为1,2,3…N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？ Input 每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。 当N = 0，输入结束。

提供三种解法, 线段树, 前缀和, 树状数组

解法一

线段树求解, 区间更新,单点查询 **我去掉了query函数,换成了push,用ans数组储存最后的值,因为是只有最后一次查询,全部查询 **

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int LEN = 1e6+4; int tree[LEN]; int ans[LEN]; void Update(int root,int Left,int Right,int L,int R) { if(L==Left&&R==Right) { tree[root]++; return ; } int mid = (Left+Right)/2; if(R<=mid) { Update(root*2,Left,mid,L,R); } else if(L>mid) Update(root*2+1,mid+1,Right,L,R); else { Update(root*2,Left,mid,L,mid); Update(root*2+1,mid+1,Right,mid+1,R); } } void Push(int root,int L,int R) { if(L==R) { ans[L] = tree[root]; return; } // cout<<L<<R<<endl; if(L!=R&&tree[root]) { tree[root*2] += tree[root]; tree[root*2+1] += tree[root]; tree[root] = 0; } Push(root*2,L,(L+R)/2); Push(root*2+1,(L+R)/2+1,R); // cout<<1<<endl; } //void Query(int root,int Left,int Right,int x) //{ // if(Left==Right) // { // printf("%d",tree[root]); // return ; // return tree[root]; // } // int mid = (Left+Right)/2; // if(x<=mid) // return Query(root*2,Left,mid,x); // else // return Query(root*2+1,mid+1,Right,x); // //} int main() { // freopen("D:\\in.txt","r",stdin); int N; while(scanf("%d",&N)!=EOF&&N) { memset(tree,0,sizeof(tree)); for(int i = 1;i <= N; ++i) { int a,b; scanf("%d %d",&a,&b); // cout<<a<<b<<endl; Update(1,1,N,a,b); } Push(1,1,N); for(int i = 1;i <= N; ++i) { if(i>1) printf(" "); printf("%d",ans[i]); } printf("\n"); } return 0; }

解法二

前缀和求解

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int LEN = 100000; int ar[LEN+4]; int main() { int N; while(cin>>N&&N) { memset(ar,0,sizeof(ar)); int a,b; for(int i = 1;i <= N; ++i) { scanf("%d %d",&a,&b); ar[a]++; ar[b+1]--; } int s = 0;//s就是前缀和 for(int i = 1;i <= N; ++i) { s+= ar[i]; cout<<s<<endl; /* ar[i] = s+ar[i]; s = ar[i]; cout<<ar[i];*/ if(i!=N) cout<<" "; } cout<<endl; } return 0; }

解法三

3 树状数组求解 因为本题只在最后一次全部查询,明显前缀和的方式最优,但是如果是边修改边查询,那就需要用到树状数组了 树状数组用于快速求和, 正好可以用来求前缀和

#define lowbit(x) (x&(-x)) using namespace std; typedef long long LL; typedef unsigned long long ULL; const int prime = 999983; const int INF = 0x3f3f3f3f; const LL INFF = 0x3f3f; const double pi = acos(-1.0); const double inf = 1e18; const double eps = 1e-9; const LL mod = 1e9 + 7; const int MAXN = 100000; const int LEN = MAXN + 100; int tree[LEN];//创建树形数组 //将区间更新转换为点更新 int N; void Add(int x,int p)// { while(x<=N) { tree[x] += p; x += lowbit(x); } } int Query(int x) { int sum = 0; while(x) { sum += tree[x]; x -= lowbit(x); } return sum; } int main() { //树状数组的解法 while(cin>>N&&N) { me(tree);//将tree置为0 fo1(i,N) { int a,b; scanf("%d %d",&a,&b); Add(a,1); Add(b+1,-1); } fo1(i,N) { if(i>1) printf(" "); printf("%d",Query(i)); } cout<<endl; } return 0; }