Codeforces 500E. New Year Domino 倍增/线段树+离线 - c++编程基础

$\$ $\$ $\$
方法1: 就是求某一段区间没有被覆盖的长度是多少,可以离线询问用线段树解决
/* ***********************************************
Author        :CKboss
Created Time  :2015年03月23日 星期一 12时38分27秒
File Name     :CF500_2.cpp
************************************************ */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             using namespace std; const int maxn=400100; int n,q; struct Gun { int h,l,r; }gn[maxn]; struct QUE { int l,r,ans,id; }que[maxn]; bool cmp1(QUE A,QUE B) { if(A.l!=B.l) return A.l>B.l; return A.r>B.r; } bool cmp2(QUE A,QUE B) { return A.id
             
              m) insert(L,R,rson); push_up(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return tree[rt]; } push_down(l,r,rt); int m=(l+r)/2; int ret=0; if(L<=m) ret+=query(L,R,lson); if(R>m) ret+=query(L,R,rson); return ret; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&n); an++; for(int i=0;i
              
               =que[i].l-1) { /// add nx 加入第nx颗柱子 int L=lower_bound(arr+1,arr+an,gn[nx].l)-arr; int R=lower_bound(arr+1,arr+an,gn[nx].r)-arr-1; insert(L,R,1,an-2,1); nx--; } int a = que[i].l-1 , b = que[i].r-1; int L=lower_bound(arr+1,arr+an,gn[a].l)-arr; int R=lower_bound(arr+1,arr+an,gn[b].l)-arr-1; que[i].ans=gn[b].l-gn[a].l-query(L,R,1,an-2,1); } sort(que,que+q,cmp2); for(int i=0;i
               
                ?
                ?
                方法2: 倍增法预处理到前为2^j的线段是哪一个,距离是多少
                ?






                ?
                /* ***********************************************
Author        :CKboss
Created Time  :2015年03月23日 星期一 21时39分56秒
File Name     :CF500E_3.cpp
/// 倍增法
************************************************ */

#include 
                 
                  
#include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                         
                           #include 
                          
                            #include
                            using namespace std; const int maxn=200200; const int INF=2100000000; int n; int a[maxn],b[maxn]; int d[maxn],dn; int p[maxn][20]; int q[maxn][20]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&n); for(int i=0;i
                            
                             =0;i--) { while(a[d[dn-1]]+b[d[dn-1]]<=a[i]+b[i]) dn--; p[i][0]=d[dn-1]; if(a[i]+b[i]>=a[d[dn-1]]) q[i][0]=0; else q[i][0]=a[d[dn-1]]-a[i]-b[i]; d[dn++]=i; } for(int j=1;j<20;j++) { for(int i=n;i>=0;i--) { p[i][j]=p[p[i][j-1]][j-1]; q[i][j]=q[i][j-1]+q[p[i][j-1]][j-1]; } } int T_T; scanf("%d",&T_T); while(T_T--) { int l,r,ans=0; scanf("%d%d",&l,&r); l--; r--; for(int i=19;i>=0;i--) { if(p[l][i]<=r) { ans+=q[l][i]; l=p[l][i]; } } printf("%d\n",ans); } return 0; } 
                            
                          
                         
                        
                       
                      
                     
                    
                   
                  
                  
                
 
                
 
                ? 
                ? 
                ? 
                ?
Codeforces 500E. New Year Domino 倍增/线段树+离线(二)
