# Timus: 1523. K-inversions

0

Solution Idea:

```
#include &lt;bits/stdc++.h&gt;
//#include &lt;ext/pb_ds/assoc_container.hpp&gt;
//#include &lt;ext/pb_ds/tree_policy.hpp&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000000
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree&lt;int, null_type, less&lt;int&gt;, rb_tree_tag, tree_order_statistics_node_update&gt; ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 20006

ll tree[12][mx];
ll ara[mx],ara2[12][mx];

void update(int id, int idx, ll val)
{
for(; idx&lt;mx &amp;&amp; idx; idx+=idx&amp;-idx)
tree[id][idx]+=val;
}

ll query(int id, int idx)
{
ll ret=0;
for(; idx; idx-=idx&amp;-idx)
ret+=tree[id][idx];
return ret;
}

//vector&lt;ll&gt;v;

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int n,k;
sff(n,k);
//    v.pb(0);
loop1(i,n)
{
sfl(ara[i]);
ara2[1][i]=1;
//        v.pb(ara[i]);
}
//    sort(all(v));

ll ans=0;
for(int j=1; j&lt;k; j++)
{
for(int i=n; i&gt;0; i--)
{
//        int id=lower_bound(all(v),ara[i])-v.begin();
int id=ara[i];
ara2[j+1][i]=query(j,id)%MOD;
update(j,id+1,ara2[j][i]);
//        update(0,id-1,-1);
}
}

//    for(int i=n; i&gt;0; i--)
//    {
////        int id=lower_bound(all(v),ara[i])-v.begin();
//        int id=ara[i];
//        ans+=query(1,id);
//        update(1,id+1,ara2[i]);
////        update(1,id-1,-ara2[i]);
//    }

for(int i=1; i&lt;=n; i++)
ans+=ara2[k][i];

printf(&quot;%lld\n&quot;,ans%MOD);

return 0;
}

```

# SPOJ: TRIPINV – Mega Inversions

0

Solution Idea:

```
#include &lt;bits/stdc++.h&gt;
#include &lt;ext/pb_ds/assoc_container.hpp&gt;
#include &lt;ext/pb_ds/tree_policy.hpp&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree&lt;int, null_type, less&lt;int&gt;, rb_tree_tag, tree_order_statistics_node_update&gt; ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 100006

ll tree[2][mx];
ll ara[mx],ara2[mx];

void update(int id, int idx, ll val)
{
for(; idx&lt;mx &amp;&amp; idx; idx+=idx&amp;-idx)
tree[id][idx]+=val;
}

ll query(int id, int idx)
{
ll ret=0;
for(; idx; idx-=idx&amp;-idx)
ret+=tree[id][idx];
return ret;
}

//vector&lt;ll&gt;v;

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int n;
sf(n);
//    v.pb(0);
loop1(i,n)
{
sfl(ara[i]);
//        v.pb(ara[i]);
}
//    sort(all(v));

ll ans=0;

for(int i=n; i&gt;0; i--)
{
//        int id=lower_bound(all(v),ara[i])-v.begin();
int id=ara[i];

ara2[i]=query(0,id);
update(0,id+1,1);
//        update(0,id-1,-1);
}

for(int i=n; i&gt;0; i--)
{
//        int id=lower_bound(all(v),ara[i])-v.begin();
int id=ara[i];
ans+=query(1,id);
update(1,id+1,ara2[i]);
//        update(1,id-1,-ara2[i]);
}

printf(&quot;%lld\n&quot;,ans);

return 0;
}

```

# Codeforces: 61 E. Enemy is weak

2

Solution Idea:

In this problem we need to count the number of triple inverse triplets on a given array. A triple inverse triplet is three positions i, j, k on an array A=[] such that i < j  Aj > Ak.

Now to solve this problem we need some range update and query data structure like segment tree or binary indexed tree. The idea is at first compress the array by mapping the numbers from range 1 to 10^6. After that read the array from reverse order and query the value of that mapped index on segment tree(let this mapped index is id)and store it on an array let name this array ara2=[]. After that increment the value of the index id+1 to n. It means that when we read any number from id+1 to n we can know that current number id have impact on this number. Here id is the k_th element of the triplet and all the number from id+1 to n is the j_th element of the triplet. Now each ara2[] index hold the number of inverse pair starting at id.

Now read the array element from the reverse order again and do the same thing. This time we need another segment tree. This time when we stand on position id add the value of the segment tree of position id to the answer and update all position in the range id+1 to n by ara2[index_of_id]. Do this for the whole array.

We can repeat this technique for 4,5,6 element inversion too.

```
#include &lt;bits/stdc++.h&gt;
#include &lt;ext/pb_ds/assoc_container.hpp&gt;
#include &lt;ext/pb_ds/tree_policy.hpp&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree&lt;int, null_type, less&lt;int&gt;, rb_tree_tag, tree_order_statistics_node_update&gt; ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 1000006

ll tree[2][mx];
ll ara[mx],ara2[mx];

void update(int id, int idx, ll val)
{
for(; idx&lt;mx &amp;&amp; idx; idx+=idx&amp;-idx)
tree[id][idx]+=val;
}

ll query(int id, int idx)
{
ll ret=0;
for(; idx; idx-=idx&amp;-idx)
ret+=tree[id][idx];
return ret;
}

vector&lt;ll&gt;v;

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int n;
sf(n);
v.pb(0);
loop1(i,n)
{
sfl(ara[i]);
v.pb(ara[i]);
}
sort(all(v));

ll ans=0;

for(int i=n; i&gt;0; i--)
{
int id=lower_bound(all(v),ara[i])-v.begin();
ara2[i]=query(0,id);
update(0,id+1,1);
//        update(0,id-1,-1);
}

for(int i=n; i&gt;0; i--)
{
int id=lower_bound(all(v),ara[i])-v.begin();
ans+=query(1,id);
update(1,id+1,ara2[i]);
//        update(1,id-1,-ara2[i]);
}

printf(&quot;%lld\n&quot;,ans);

return 0;
}

```

# Codeforces: 877E. Danil and a Part-time Job

0

Solution Idea:

Run a dfs on the given for getting the Euler tour order or inorder traversal order. Then the tree is converted to a liner 1D array. Now we can apply range query and update on this array.

Now use a range update query data structure. Here I have used segment tree. Now initialize the tree with the initial value and now our job is to just toggle a subtree of the given tree and perform query operation. Use a propagation for the update and answer the query.

```
#include &lt;bits/stdc++.h&gt;
#include &lt;ext/pb_ds/assoc_container.hpp&gt;
#include &lt;ext/pb_ds/tree_policy.hpp&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree&lt;int, null_type, less&lt;int&gt;, rb_tree_tag, tree_order_statistics_node_update&gt; ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 200005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
pii info[mx];
vector&lt;int&gt;g[mx];
int cnt=0;
int maps[mx],ara[mx];

void dfs(int u, int par)
{
info[u].ff=++cnt;
maps[cnt]=u;
for(int i=0;i&lt;SZ(g[u]);i++)
{
int v=g[u][i];
if(v==par) continue;
dfs(v,u);
}
info[u].ss=cnt;
}

struct data
{
int val, prop;
};

data tree[3*mx];

void push_down(int n, int b, int e)
{
if(tree[n].prop%2)
{
segment_tree;
tree[l].val=(mid-b+1)-tree[l].val;
tree[l].prop++;
tree[r].val=(e-mid)-tree[r].val;
tree[r].prop++;
tree[n].prop=0;
}
}

void init(int n, int b, int e)
{
if(b==e)
{
tree[n].val=ara[maps[b]];
tree[n].prop=0;
return;
}
segment_tree;
init(l,b,mid);
init(r,mid+1,e);
tree[n].val=tree[l].val+tree[r].val;
}

void update(int n, int b, int e, int i, int j)
{
if(b&gt;j || e&lt;i) return;
if(b&gt;=i &amp;&amp; e&lt;=j)
{
tree[n].val=(e-b+1)-tree[n].val;
tree[n].prop++;
return;
}
push_down(n,b,e);
segment_tree;
update(l,b,mid,i,j);
update(r,mid+1,e,i,j);
tree[n].val=tree[l].val+tree[r].val;
}

int query(int n, int b, int e, int i, int j)
{
if(b&gt;j || e&lt;i) return 0;
if(b&gt;=i &amp;&amp; e&lt;=j) return tree[n].val;
push_down(n,b,e);
segment_tree;
int p=query(l,b,mid,i,j);
int q=query(r,mid+1,e,i,j);
return p+q;
}

char str[10];

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int n;
sf(n);
for(int i=2;i&lt;=n;i++)
{
int a;
sf(a);
g[a].pb(i);
}

for(int i=1;i&lt;=n;i++) sf(ara[i]);
dfs(1,1);
init(1,1,n);
int q;
sf(q);
while(q--)
{
int a;
scanf(&quot; %s %d&quot;,str,&amp;a);
if(str[0]=='g')
{
int x=query(1,1,n,info[a].ff,info[a].ss);
printf(&quot;%d\n&quot;,x);
}
else
{
update(1,1,n,info[a].ff,info[a].ss);
}
}

return 0;
}

```

# Codeforce gym: 101484 F. No Link, Cut Tree!

0

Solution Idea:

My solution idea for this problem is at first make the given tree a full binary tree. A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. On the other hand A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. So we can convert a complete binary tree to a full binary tree by adding some dummy node whose cost is 0 so that they don’t contribute anything in the solution as well as they will help us to form our solution.

Now classify the nodes according to their level and make their cumulative sum or insert them in segment tree or in a binary indexed tree. We need this data structure for every level. Now map the nodes by the inorder traversal of the tree and position of the level array like 1,2,3….

Now here comes an important observation in a full binary tree at any level, if I want to delete a subtree starting at node u the will need to delete 1 node from level[u], 2 node from level[u]+1, 4 node from level[u]+2…2^i node form level[u]+i.

Now form the data structure (here I have used Binary Indexed Tree(BIT)) just query the contribution of the deleted node subtract them form the total contribution of that level and take the maximum. We need to do this from level[u] to last level and we need to consider the whole level from level 1 to level[u]-1.

```
#include &lt;bits/stdc++.h&gt;
#include &lt;ext/pb_ds/assoc_container.hpp&gt;
#include &lt;ext/pb_ds/tree_policy.hpp&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree&lt;int, null_type, less&lt;int&gt;, rb_tree_tag, tree_order_statistics_node_update&gt; ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 200005

vector&lt;int&gt;g[mx];

vector&lt;int&gt;level_g[20];

int map1[mx],levell[mx];
int map2_level[mx],cost[mx],max_depth,disc;
int tree[20][mx];
int n,m;

void dfs1(int u, int level)
{
max_depth=max(max_depth,level);
for(int i=0;i&lt;SZ(g[u]);i++)
{
int v=g[u][i];
dfs1(v,level+1);
}
}

void dfs(int u, int par, int level)
{
levell[u]=level;
//    max_depth=max(max_depth,level);
map1[u]=++disc;
level_g[level].pb(u);

if(levell[u]!=max_depth)
{
if(SZ(g[u])==0)
g[u].pb(++n);
if(SZ(g[u])==1)
g[u].pb(++n);
}

for(int i=0;i&lt;SZ(g[u]);i++)
{
int v=g[u][i];
if(v==par) continue;
dfs(v,u,level+1);
}
}

void update(int id, int idx, int val)
{
for(int i=idx;i&lt;mx;i+=(i&amp;-i))
tree[id][i]+=val;
}

int query(int id, int idx)
{
int ret=0;
for(int i=idx;i&gt;0;i-=(i&amp;-i))
ret+=tree[id][i];
return ret;
}

int main()
{
//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

sff(n,m);
sf(cost[1]);

for(int i=1;i&lt;n;i++)
{
int a,b,c;
sfff(a,b,c);
g[b].pb(a);
cost[a]=c;
}
dfs1(1,1);
//    int xx=n;
//    for(int i=1;i&lt;=xx;i++)
//    {
//        if(SZ(g[i])==1)
//            g[i].pb(++n);
//    }

dfs(1,1,1);

for(int i=1;i&lt;=max_depth;i++)
{
int num=0;
for(int j=0;j&lt;SZ(level_g[i]);j++)
{
int v=level_g[i][j];
map2_level[map1[v]]=++num;
update(i,num,cost[v]);
}
}

while(m--)
{
int u;
sf(u);
int ans=0;
for(int i=1;i&lt;levell[u];i++)
ans=max(ans,query(i,mx-1));
int last=levell[u],pp=0,cur=map1[u];
for(int i=levell[u];i&lt;=max_depth;i++)
{
int total=query(i,mx-1);
int sub=query(i,map2_level[cur]+(1&lt;&lt;pp)-1);
int sub1=query(i,map2_level[cur]-1);
total-=(sub-sub1);
ans=max(ans,total);
pp++;
cur++;
}

printf(&quot;%d\n&quot;,ans);

}

return 0;
}

```

# Codechef: Dividing Machine (DIVMAC)

0

Solution Idea:

In this problem, a tricky observation is the primary key of the solution. That observation is the input number is in range 1 to 10^6. So We can perform update operation on an index at most 20 times. Because if we divide a number of range 1 to 10^6 with it’s prime divisors we can divide them at most 20 times.

So in the update section of segment tree we can make a check whether the maximum least prime divisor of this sub tree is 1 or not. If it is a 1 then we don’t need to update in the sub tree. Otherwise we will explore this sub tree and update them.

After this observation this problem is a simple RMQ problem.

```
#include &lt;bits/stdc++.h&gt;
#include &lt;ext/pb_ds/assoc_container.hpp&gt;
#include &lt;ext/pb_ds/tree_policy.hpp&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree&lt;int, null_type, less&lt;int&gt;, rb_tree_tag, tree_order_statistics_node_update&gt; ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
bitset&lt;mx/2&gt;vis;

vector&lt;int&gt;prime;

void sieve()
{
int x=mx/2,y=sqrt(mx)/2;
for(int i=1; i&lt;y; i++)
{
if(vis[i])
{
for(int j=i*(i+1)*2; j&lt;x; j+=(2*i+1))
vis[j]=1;
}
}
prime.pb(2);
for(int i=3; i&lt;mx; i+=2)
if(vis[i/2]==0) prime.pb(i);
}

deque&lt;int&gt;dq[mx];

int tree[3*mx];

void init(int n, int b, int e)
{
if(b==e)
{
tree[n]=dq[b].front();
return;
}
segment_tree;
init(l,b,mid);
init(r,mid+1,e);
tree[n]=max(tree[l],tree[r]);
}

void update(int n, int b, int e, int i, int j)
{
if(b&gt;j || e&lt;i) return;
if(tree[n]==1) return;
if(b==e)
{
dq[b].pop_front();
tree[n]=dq[b].front();
return;
}
segment_tree;
update(l,b,mid,i,j);
update(r,mid+1,e,i,j);
tree[n]=max(tree[l],tree[r]);
}

int query(int n, int b, int e, int i, int j)
{
if(b&gt;j || e&lt;i) return 0;
if(b&gt;=i &amp;&amp; e&lt;=j) return tree[n];
segment_tree;
int p=query(l,b,mid,i,j);
int q=query(r,mid+1,e,i,j);
return max(p,q);
}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

sieve();

//    for(int i=0;i&lt;100;i++)
//        D(prime[i]);

int t;
sf(t);
TEST_CASE(t)
{
int n,m;
sff(n,m);
for(int i=1; i&lt;=n; i++)
{
int a;
sf(a);
int root=sqrt(a);
dq[i].clear();
for(int j=0;prime[j]&lt;=root;j++)
{
if(a%prime[j]==0)
{
while(a%prime[j]==0)
{
dq[i].pb(prime[j]);
a/=prime[j];
}
root=sqrt(a);
}
}
if(a&gt;1)
dq[i].pb(a);
dq[i].pb(1);
}

init(1,1,n);
bool check=0;
while(m--)
{
int a,b,c;
sfff(a,b,c);
if(a==0)
{
update(1,1,n,b,c);
}
else
{
if(check==0)
{
printf(&quot;%d&quot;,query(1,1,n,b,c));
check=1;
}
else
printf(&quot; %d&quot;,query(1,1,n,b,c));
}
}
printf(&quot;\n&quot;);
}

return 0;
}

```

# Light OJ: 1424 – New Land

0

Solution Idea: I think this problem can be solved with a 2D Segment Tree. But here I use the histogram technique to solve this problem. You can try Spoj – HISTOGRA – Largest Rectangle in a Histogram and Light OJ – 1083 – Histogram . Both are same problem on different website. This problems can be using a niche technique called histogram which can be implemented using a stack. the algorithm determine the index of the bar before the current bar which is smaller than the current bar also determine the index of the bar after the current bar which is smaller than the current bar. Here the function func is the answer of the above two problem.

In this problem for each row we consider a histogram from current row and the rows which are above the current row with continuous 0. Then determine the maximum answer.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 2002

char grid[mx][mx];

int dp[mx][mx];

int func(int ara[], int n)
{
int left[mx];

stack&lt;int&gt;st;

for(int i=0; i&lt;n; i++)
{
while(!st.empty() &amp;&amp; ara[st.top()]&gt;=ara[i]) st.pop();
left[i]=(st.empty()?-1:st.top());
st.push(i);
}

while(!st.empty()) st.pop();

int ret=0;
int right;
for(int i=n-1; i&gt;=0; i--)
{
while(!st.empty() &amp;&amp; ara[st.top()]&gt;=ara[i]) st.pop();
right=(st.empty()?n:st.top());
ret=max((right-left[i]-1)*ara[i],ret);
st.push(i);
}
return ret;
}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);
TEST_CASE(t)
{
int n,m;
sff(n,m);
getchar();
for(int i=0; i&lt;n; i++)
sc(&quot;%s&quot;,grid[i]);

for(int j=0; j&lt;m; j++)
{
dp[0][j]=(grid[0][j]=='0')?1:0;
}

int ans=func(dp[0],m);

for(int i=1; i&lt;n; i++)
{
for(int j=0; j&lt;m; j++)
{
dp[i][j]=dp[i-1][j]+((grid[i][j]=='0')?1:-dp[i-1][j]);
}
ans=max(ans,func(dp[i],m));
}
PRINT_CASE;
pf(&quot;%d\n&quot;,ans);

}

return 0;
}

```

# ACM-ICPC Live Archive : 4108 – SKYLINE

0

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 100005

struct data
{
ll maxi, mini, prop;

};

struct inp
{
int l, r, v;
inp(int a, int b, int c)
{
l=a,r=b,v=c;
}
};

data tree[mx*4];

int ls,rs,h;

void push_down(int n)
{
int val=tree[n].prop;
if(tree[n].prop!=0)
{
tree[n*2].prop=val;
tree[n*2+1].prop=val;
tree[n*2].maxi=val;
tree[n*2+1].maxi=val;
tree[n*2].mini=val;
tree[n*2+1].mini=val;
tree[n].prop=0;
}
}

void push_up(int n)
{
tree[n].maxi=max(tree[n*2].maxi,tree[n*2+1].maxi);
tree[n].mini=min(tree[n*2].mini,tree[n*2+1].mini);
}

int anss=0;

void update(int n, int b, int e, int i, int j)
{
if(b&gt;j || e&lt;i) return;
if(b&gt;=i &amp;&amp; e&lt;=j)
{
if(tree[n].maxi&lt;h)
{
tree[n].maxi=h;
tree[n].prop=h;
tree[n].mini=h;
return;
}
else if(tree[n].mini&gt;h)
{
anss+=(e-b+1);
return;
}
}
if(b==e) return;
push_down(n);
int l=n*2;
int r=l+1;
int mid=(b+e)/2;
update(l,b,mid,i,j);
update(r,mid+1,e,i,j);
push_up(n);
}

int main()
{

///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
int n;
sf(t);
{
TEST_CASE(t)
{
sf(n);
ll ans=0;

ms(tree,0);

vector&lt;inp&gt;vv;
loop(i,n)
{

sfff(ls,rs,h);
vv.pb(inp(ls,rs,h));
}

for(int i=0; i&lt;n; i++)
{
ls=vv[i].l;
rs=vv[i].r;
h=vv[i].v;
anss=0;
ans+=(rs-ls-anss);

}
pf(&quot;%lld\n&quot;,ans);
}
}

sf(t);

return 0;
}

```

# Light OJ: 1207 – Posters for Election

0

```
/*
If opportunity doesn't knock, build a door.

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|.|S|.|R|.|A|.|S|.|A|.|M|.|K|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Success is how high you bounce when you hit bottom.
*/

#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

struct data
{
int sum, prop;
};

data tree[3*200005];

void push_down(int n, int b, int e)
{
if(tree[n].prop!=-1)
{
int mid=(b+e)/2;
tree[n*2].sum=(mid-b+1)*tree[n].prop;
tree[n*2+1].sum=(e-mid)*tree[n].prop;
tree[2*n].prop=tree[n].prop;
tree[2*n+1].prop=tree[n].prop;
tree[n].prop=-1;
}
}

void push_up(int n)
{
tree[n].sum=tree[n*2].sum+tree[n*2+1].sum;
}

void update(int n, int b, int e, int i, int j, int x)
{
if(i&gt;e || j&lt;b) return;
if(b&gt;=i &amp;&amp; e&lt;=j)
{
tree[n].sum=x;
tree[n].prop=x;
return;
}

push_down(n,b,e);

int l=n*2;
int r=l+1;
int mid=(b+e)/2;

update(l,b,mid,i,j,x);
update(r,mid+1,e,i,j,x);

push_up(n);

}

bool query(int n, int b, int e, int i, int j)
{
if(i&gt;e || j&lt;b) return 0;
if(b&gt;=i &amp;&amp; e&lt;=j) return tree[n].sum;
push_down(n, b, e);
int l=n*2;
int r=l+1;
int mid=(b+e)/2;

int p=query(l,b,mid,i,j);
int q=query(r,mid+1,e,i,j);
push_up(n);
return p|q;
}

int main()
{
///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);
TEST_CASE(t)
{
vector&lt;pii&gt;v;
int n;
sf(n);

loop(i,n)
{
int a,b;
sff(a,b);
v.pb(MP(a,b));
}
reverse(all(v));

int ans=0;

update(1,1,200000,1,200000,1);

loop(i,n)
{
if(query(1,1,200000,v[i].ff,v[i].ss))
{
ans++;
update(1,1,200000,v[i].ff,v[i].ss,0);
}
}
PRINT_CASE;
printf(&quot;%d\n&quot;,ans);
}

return 0;
}

```

# Light OJ: 1097 – Lucky Number

0

```

/*
If opportunity doesn't knock, build a door.

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|.|S|.|R|.|A|.|S|.|A|.|M|.|K|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Success is how high you bounce when you hit bottom.
*/

#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int mm=1429431;

int tree[1429450*4];

void init(int n,int b, int e)
{
if(b==e)
{
if(b%2==1) tree[n]=1;
else tree[n]=0;
return;
}
int mid=(b+e)/2;
int l=n*2;
int r=l+1;
init(l,b,mid);
init(r,mid+1,e);
tree[n]=tree[l]+tree[r];
}

int query(int n, int b, int e, int x)
{
if(x==1 &amp;&amp; b==e) return b;
int l=n*2;
int r=l+1;
int mid=(b+e)/2;
if(x&gt;tree[l]) return query(r,mid+1,e,x-tree[l]);
else
return query(l,b,mid,x);
}

void update(int n, int b, int e, int x)
{
if(x==1 &amp;&amp; b==e)
{
tree[n]=0;
return;
}
int l=n*2;
int r=l+1;
int mid=(b+e)/2;
if(x&gt;tree[l]) update(r,mid+1,e,x-tree[l]);
else
update(l,b,mid,x);
tree[n]=tree[l]+tree[r];
}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//    freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

init(1,1,mm);
for(int i=2; i&lt;=100000; i++)
{
int x=query(1,1,mm,i);
int xx=x;
while(x&lt;tree[1])
{
update(1,1,mm,x);
x+=xx;
x-=1;
}
}

int t;
sf(t);
TEST_CASE(t)
{
int a;
sf(a);
PRINT_CASE;
pf(&quot;%d\n&quot;,query(1,1,mm,a));
}
return 0;
}

```