Color the ball

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 27513 Accepted Submission(s): 13359

Problem Description

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，输入结束。

Output

每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

Sample Input

      3 1 1 2 2 3 3 3 1 1 1 2 1 3 0 

Sample Output

      1 1 1 3 2 1 

分析：线段树模板题，跟着题意走就好。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #define range(i,a,b) for(auto i=a;i<=b;++i)#define LL long long#define itrange(i,a,b) for(auto i=a;i!=b;++i)#define rerange(i,a,b) for(auto i=a;i>=b;--i)#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))using namespace std;template 
                
                 class segtree{private: T* add,*sum; void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void pushdown(int rt,int m){ if(add[rt]){ add[rt<<1]+=add[rt]; add[rt<<1|1]+=add[rt]; sum[rt<<1]+=add[rt]*(m-(m>>1)); sum[rt<<1|1]+=add[rt]*(m>>1); add[rt]=0; } }public: explicit segtree(int len=int(1e5+5)){ add=new T[len<<2]; sum=new T[len<<2]; fill(add,0);fill(sum,0); } void build(int l,int r,int rt=1){ add[rt]=0; if(l==r){ sum[rt]=0; return; } int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); pushup(rt); } void update(int L,int R,T c,int l,int r,int rt=1){ if(L<=l&&r<=R){ add[rt]+=c; sum[rt]+=c*(r-l+1); return; } pushdown(rt,r-l+1); int m=(l+r)>>1; if(L<=m)update(L,R,c,l,m,rt<<1); if(m
                 
                  <<1|1); pushup(rt); } T query(int L,int R,int l,int r,int rt=1){ if(L<=l&&r<=R)return sum[rt]; pushdown(rt,r-l+1); int m=(l+r)>>1; T ret=0; if(L<=m)ret+=query(L,R,l,m,rt<<1); if(m
                  
                   <<1|1); return ret; }};segtree
                   
                    tree;int n,a,b;void init(){}void solve(){ while(cin>>n,n){ tree.build(1,n); range(i,1,n){ cin>>a>>b; tree.update(a,b,1,1,n); } range(i,1,n){ int ans=tree.query(i,i,1,n); cout<
                    
                     <<(i==n?'\n':' '); } }}int main() { init(); solve(); return 0;}

View Code

转载于:https://www.cnblogs.com/Rhythm-/p/9406223.html

你可能感兴趣的文章