文章目录


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