Lazy Segment Tree

Question

The following is an implementation of http://www.spoj.pl/problems/LITE/ using a segment tree with lazy distribution. I am new to the tree segment and I cannot understand why I get TLE. Can someone look at it and help me fix my mistake?

#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; maybe faster than M[node] = (M[node]==0)?1:0; , and (begin+end)>>1 faster than (begin/end)/2 , but not very relevant

LE: try if running inline recursive functions will be faster. I think it solves recursion a couple of times and runs a little faster. Perhaps sending parameters as links will make it work faster, try this. If the test cases are selected correctly, you still will not be able to pass the tests using this deception, but sometimes it helps.