4

The following is the implementation of http://www.spoj.pl/problems/LITE/ using Segment Tree's with lazy propagation. I am new to segment trees and I cannot understand why I am getting TLE. Could someone please look at it and help me correct my error?

#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;
}
Ronzii
  • 247
  • 1
  • 3
  • 12
  • What input causes your program to fail? – sarnold Jul 04 '11 at 02:43
  • I tried getting correct outputs via a brute force approach complexity O(m*n) and matching those generated by my segment tree approach. But that seems to be working correctly on my system and I dont get TLE since SPOJ uses a slower processor – Ronzii Jul 04 '11 at 04:19
  • tried reading a block at a time and parsing the block? maybe the IO is the bottleneck – titus Jul 04 '11 at 05:03
  • I did a little digging at SPOJ forums it turns out that I am not using lazy propagation at all. If we were to update range [1,8] we would effectively have to update every node in the tree. Lazy propagation means that we would only update node [1,8] and leave a flag that says that it's children need to be updated. Then when we have to query deeper than [1,8] we push the update down to the children, along with the flag. This way we only update when needed. – Ronzii Jul 04 '11 at 05:17
  • 1
    http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296 – titus Jul 04 '11 at 05:25

1 Answers1

1

M[node]^=1; might be 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 making the recursive functions inline will run faster. I think it unravels the recursion a couple of times and works a little bit faster. Maybe sending the parameters as references will make it run faster, try that out. If the test cases are chosen properly you still shouldn't be able to pass the tests with this trickery, but it helps sometimes.

titus
  • 5,512
  • 7
  • 25
  • 39