Where should I optimise my code.
#include
#include
#define ll long long int
#define mod 1000000007
using namespace std ;
void segment_tree( vector &tree, ll ss , ll se , ll index)
{
//Base Case
if(ss == se)
{
string v = “0”;
tree[index] = v;
return ;
}
//Recursive Calls and Small calculation
ll mid = (ss + se)/2;
segment_tree(tree,ss,mid,2*index);
segment_tree(tree,mid+1,se,2*index+1);
tree[index] = tree[2*index] + tree[2*index+1];
return ;
}
//tree,lazy,num,l,r,ss,se,index
void range_update(vector &tree, char lazy[] ,char ch , ll l , ll r , ll ss , ll se , ll index )
{
if(lazy[index] != ‘.’)
{
for(ll i = 0 ; i <tree[index].size() ; i++)
{
tree[index][i] = lazy[index];
}
if(ss != se)
{
lazy[2index] = lazy[index];
lazy[2index+1] = lazy[index];
}
lazy[index] = ‘.’;
}
if(ss > r || se < l)
{
return ;
}
if(ss>= l && se <= r)
{
for(ll i = 0 ; i <tree[index].size() ; i++)
{
tree[index][i] = ch;
}
if(ss != se)
{
lazy[2*index] =ch;
lazy[2*index+1] = ch;
}
return ;
}
ll mid = (ss + se)/2;
range_update(tree, lazy ,ch , l , r , ss , mid , 2*index);
range_update(tree, lazy ,ch , l , r , mid+1 , se , 2*index+1);
tree[index] = tree[2*index] + tree[2*index+1];
return ;
}
string query(vector&tree, char lazy[] ,ll l,ll r,ll ss,ll se,ll index)
{
if(lazy[index] != ‘.’)
{
for(ll i = 0 ; i <tree[index].size() ; i++)
{
tree[index][i] = lazy[index];
}
if(ss != se)
{
lazy[2index] = lazy[index];
lazy[2index+1] = lazy[index];
}
lazy[index] = ‘.’;
}
if(ss>r || se < l)
{
string v = “”;
return v ;
}
if(ss>= l && se <= r)
{
string v = "" ;
for(int i = 0 ; i < tree[index].size() ; i++)
{
char ch = tree[index][i];
v += ch ;
}
return v ;
}
int mid = (ss + se)/2;
string v1 = query(tree,lazy,l,r,ss,mid,2*index);
string v2 = query(tree,lazy,l,r,mid+1,se,2*index+1);
return v1 + v2 ;
}
int main()
{
ll n, q;
cin >> n >> q ;
vector<string > tree(4*n+1);
//Making segment tree
segment_tree(tree,0,n-1,1);
/*for(int i = 1 ; i <=5 ; i++)
{
cout << i << "-> " << " ";
for(int j = 0 ; j < tree[i].size() ; j++)
{
cout << tree[i][j] << " ";
}
cout << endl;
}*/
char lazy[4*n+1];
for(int i = 0 ; i < 4*n+1 ; i++)
{
lazy[i] = '.';
}
while(q--)
{
ll num , l ,r ;
cin >> num >> l >> r;
char ch ;
if(num == 0)
{
ch = 48;
}
if(num == 1)
{
ch = 49;
}
if(num == 0 || num == 1)
{
//tree,lazy,num,l,r,ss,se,index
range_update(tree,lazy,ch,l,r,0,n-1,1);
}
else
{
//tree , lazy , l ,r , ss , se , index
string v = query(tree,lazy,l,r,0,n-1,1);
ll bin = 1;
ll i = v.length() -1 ;
ll ans = 0 ;
while(i >= 0 )
{
int num = v[i] - '0' ;
ans += (num * bin);
ans %= mod;
bin *= 2;
i--;
}
cout << ans << endl;
}
}
}