I am trying to solve the flipping coin problem and unable to understand the lazy propagation method clearly. I searched on internet and found some codes.
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<cstdio>
#include<cmath>
#define MAX 300000
#define loop0(i,j) for(int i=0;i<j;i++)
#define loop1(i,j) for(int i=1;i<j;i++)
using namespace std;
bool flag[MAX];
int value[MAX];
/*void initialize(int node, int b, int e)
{
if (b == e)
{
flag[node] = false;
value[node] = 0;
}
else
{
initialize(2 * node, b, (b + e) / 2);
initialize(2 * node + 1, (b + e) / 2 + 1, e);
value[node] = 0;
flag[node] = false;
}
}*/
int update(int node, int b, int e, int i, int j)
{
int p1, p2;
if (i > e || j < b)
return 0;
if (b >= i && e <= j)
{
if(b==e)
{
if(flag[node] == true)
return 1;
else
return 0;
}
else if(flag[node] == true)
{
flag[node] = false;
flag[2*node] = !flag[2*node];
flag[2*node+1] = !flag[2*node+1];
p1 = update(2 * node, b, (b + e) / 2, i, j);
p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
return value[node] = p1 + p2;
}
else
return value[node];
}
else
{
if(flag[node]==true)
{
flag[node]=false;
flag[2*node]=!flag[2*node];
flag[2*node+1]=!flag[2*node+1];
}
p1 = update(2 * node, b, (b + e) / 2, i, j);
p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
return value[node] = p1 + p2;
}
}
int query(int node, int b, int e, int i, int j)
{
int p1, p2;
if (i > e || j < b)
return 0;
if (b >= i && e <= j)
{
flag[node] = !flag[node];
return value[node] = e - b + 1 - value[node];
}
else
{
if(flag[node]==true)
{
flag[node]=false;
flag[2*node]=!flag[2*node];
flag[2*node+1]=!flag[2*node+1];
}
p1 = query(2 * node, b, (b + e) / 2, i, j);
p2 = query(2 * node + 1, (b + e) / 2 + 1, e, i, j);
if(p1==-1)
p1=0;
if(p2==-1)
p2=0;
return (value[node] = p1 + p2);
}
}
int main()
{
int k, t, tests, m, n;
int f, a, b, z;
// cin >> tests >> m;
scanf("%d %d",&tests,&m);
// initialize(1, 0, tests-1);
loop0(i, m)
{
scanf("%d %d %d",&f,&a,&b);
// cin >> f >> a >> b;
if(f==0)
value[1] = query(1,0,tests-1,a,b);
else
printf("%d\n",update(1,0,tests-1,a,b));
// cout << update(1,0,tests-1,a,b) <<"\n";
}
return 0;
}
I don't know whether this is correct or not because its still giving TLE on Codechef. Please explain lazy propagation in detail or tell whether this code is correct or not. I will try to understand it according to the code.