具有惰性傳播的分段樹時間限制問題

Question

以下是使用具有惰性傳播的分段樹的http://www.spoj.pl/problems/LITE/的實現。我是新來的細分樹，我不明白爲什麼我得到TLE。有人可以看看它並幫我糾正我的錯誤嗎？

#include <iostream> 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#define MAX 100000 
using namespace std; 
int M[2*MAX+1]; 
int flag[2*MAX+1]; 
int count; 
void refresh(int begin,int end,int n) 
{ 
    M[n] = end-begin+1 - M[n]; 
    flag[n]=0; 
    flag[n*2] =!flag[n*2]; 
    flag[n*2+1] =!flag[n*2+1]; 
} 
void update(int begin,int end,int i,int j,int n=1) 
{ 
    if(flag[n]) 
    { 
     refresh(begin,end,n); 
    } 
    if(begin>=i && end<=j) 
    { 
     if(!flag[n]) 
     { 
      refresh(begin,end,n); 
     } 
     flag[n] = 0; 
     return; 
    } 
    else if(begin>=end) 
    { 
     return; 
    } 
    else 
    { 
     int mid = (begin+end)>>1; 
     if(i<=mid) 
     { 
      update(begin,mid,i,j,n*2); 
     } 
     if(j>mid) 
     { 
      update(mid+1,end,i,j,n*2+1); 
     } 
     if(flag[2*n]) 
     { 
      refresh(begin,mid,2*n); 
     } 
     if(flag[2*n+1]) 
     { 
      refresh(mid+1,end,2*n+1); 
     } 
     M[n] = M[n*2]+ M[n*2+1]; 
    } 
} 
int query(int begin,int end,int i,int j,int n=1) 
{ 
    if(flag[n]) 
    { 
     refresh(begin,end,n); 
    } 
    if(begin>=i && end<=j) 
    { 
     return M[n]; 
    } 
    if(begin>=end) 
    { 
     return 0; 
    } 
    int mid = (begin+end)>>1; 
    int l=0,r=0; 
    if(i<=mid) 
    { 
     l = query(begin,mid,i,j,n*2); 
    } 
    if(j>mid) 
    { 
     r = query(mid+1,end,i,j,n*2+1); 
    } 
    if(flag[2*n]) 
    { 
     refresh(begin,mid,2*n); 
    } 
    if(flag[2*n+1]) 
    { 
     refresh(mid+1,end,2*n+1); 
    } 
    M[n] = M[n*2]+ M[n*2+1]; 
    return l+r; 
} 
int main() 
{ 
    memset(M,0,sizeof M); 
    int n,m,a,b,c; 
    scanf("%d%d",&n,&m); 
    for(int i=0; i<m; i++) 
    { 
     scanf("%d%d%d",&a,&b,&c); 
     if(a==0) 
     { 
      update(1,n,b,c); 
     } 
     else 
     { 
      printf("%d\n",query(1,n,b,c)); 
     } 
    } 
    return 0; 
} 

Answer 1

M[node]^=1;可能會快於M[node] = (M[node]==0)?1:0;和(begin+end)>>1快於(begin/end)/2，但不是很相關

LE：如果試試使得遞歸函數內聯將運行得更快。我認爲它解開了遞歸幾次，並且工作得更快一點。也許發送參數作爲參考將使它運行得更快，試試看。如果測試用例選擇得當，你仍然不能通過這個技巧來通過測試，但它有時會有幫助。