Comrades - III
Problem
Editorial
My Submissions
Analytics
The human army has proved itself against the mighty aliens by winning the Great War.
But even in times of peace, the army should remain alert and disciplint.
But even in times of peace, the army should remain alert and disciplint.
The army has N soldiers. The soldiers are numbered from 1 to N. The army has a superiority hierarchy. Every soldier has one immediate superior. The superior of a superior of a soldier is also a superior to that soldier. So, a soldier may have one or more superiors but only one immediate superior.
As a exercise to determine the efficiency of the army, the following drill has been designed.
You are given a list of orders. Each order is of the form "
where Type is either 1,2 or 3 and ID is a number S (1<=S<=N) that denotes a soldier.
<Type><space><ID>"where Type is either 1,2 or 3 and ID is a number S (1<=S<=N) that denotes a soldier.
There are three types of orders:
Type 1:
All the soldiers who have S as one of their superior will wake up.
Type 1:
All the soldiers who have S as one of their superior will wake up.
Type 2:
All the soldiers who have S as one of their superior will go to sleep.
All the soldiers who have S as one of their superior will go to sleep.
Type 3:
Count and output the number of soldiers who are awake and have S as one of their superior.
Count and output the number of soldiers who are awake and have S as one of their superior.
NOTE: Among all soldiers there is one soldier who does not have any superior. He is the commander of the whole army.
Input :
The first line contains N, the number of soldiers. The next line contains N space separated integers. The ith integer represents the immediate superior of the ith soldier.
The immediate superior of the commander of the army will be '0'.
The immediate superior of the commander of the army will be '0'.
The third line contains Q, the number of orders.
Each of the next Q lines contain two integers, the type of order and S.
Each of the next Q lines contain two integers, the type of order and S.
Output :
For each Type-3 order, output the number of soldiers who are awake and have the given soldier as their superior.
Constraints :
1 <= N <= 100000
1 <= Q <= 100000
1 <= Type <= 3
1 <= S <= N
1 <= Q <= 100000
1 <= Type <= 3
1 <= S <= N
A soldier cannot be his own superior.
Explanation
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli arr[1000000];
struct abc
{
lli sleep;
lli awk;
} tree[1000000];
lli lazy[1000000];
list<lli> li[1000000];
lli visited[1000000];
vector<pair<lli,lli> > v;
lli times;
lli ans=0;
#define mp make_pair
#define pb push_back
#define inf 999999999
#define ff first
#define ss second
lli query(lli node,lli start,lli end,lli r1,lli r2)
{
if(lazy[node]!=0)
{
if(lazy[node]==1)
{
tree[node].awk=(end-start)+1;
tree[node].sleep=0;
if(start!=end)
{
lazy[2*node]=1;
lazy[2*node+1]=1;
}
}
else
{
tree[node].sleep=(end-start)+1;
tree[node].awk=0;
if(start!=end)
{
lazy[2*node]=-1;
lazy[2*node+1]=-1;
}
}
lazy[node]=0;
}
if(start>end || r1>end || r2<start) return 0;
if(r1<=start && r2>=end)
{
return tree[node].awk;
}
else
{
lli q1=query(2*node,start,(start+end)/2,r1,r2);
lli q2=query(2*node+1,((start+end)/2)+1,end,r1,r2);
ans+=q1+q2;
return q1+q2;
}
}
void update(lli node ,lli start,lli end,lli r1,lli r2,lli type)// type is type of update 1 means wake all under that superior
{
if(lazy[node]!=0)
{
if(lazy[node]==1)
{
tree[node].awk=(end-start)+1;
tree[node].sleep=0;
if(start!=end)
{
lazy[2*node]=1;
lazy[2*node+1]=1;
}
}
else
{
tree[node].sleep=(end-start)+1;
tree[node].awk=0;
if(start!=end)
{
lazy[2*node]=-1;
lazy[2*node+1]=-1;
}
}
lazy[node]=0;
}
if(r1>end || r2<start || start>end) return ;
if(r1<=start && r2>=end)
{
if(type==1)
{
tree[node].awk=(end-start)+1;
tree[node].sleep=0;
if(start!=end)
{
lazy[2*node]=1;
lazy[2*node+1]=1;
}
}
else
{
tree[node].sleep=(end-start)+1;
tree[node].awk=0;
if(start!=end)
{
lazy[2*node]=-1;
lazy[2*node+1]=-1;
}
}
return ;
}
update( 2*node ,start,(start+end)/2,r1,r2,type);
update( 2*node+1 ,(start+end)/2+1,end,r1,r2,type);
tree[node].sleep=tree[2*node].sleep+tree[2*node+1].sleep;
tree[node].awk=tree[2*node].awk+tree[2*node+1].awk;
}
void build(lli node , lli start,lli end)
{
if(start==end)
{
// since initily all solders are awake .
tree[node].sleep=0;
tree[node].awk=1;
}
else if(start>end) return ;
else
{
build(2*node,start,(start+end)/2);
build(2*node+1,((start+end)/2)+1,end);
tree[node].sleep=tree[2*node].sleep+tree[2*node+1].sleep;
tree[node].awk=tree[2*node].awk+tree[2*node+1].awk;
}
}
/// finding starting and ending time of all solders all soleders b/w start_time+1 to end _time will be under thta solder
// also tree is lenear and rooted at node 0.
lli dfs(lli start)
{
list<lli>:: iterator it;
it=li[start].begin();
// start time of node start
v[start].first=times;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(!visited[*it])
{
visited[*it]=1;
times++;
dfs(*it);
}
}
// end time of node start
v[start].second=times;
}
int main()
{
lli n;
cin>>n;
lli st;
for(lli i=1;i<=n;i++)
{
lli a;
cin>>a;
if(a==0)st=i;
li[a].pb(i);
}
for(lli i=0;i<n+1;i++)
{
v.pb(mp(0,0));
}
v[0].first=0;
dfs(st);
build(1,0,n-1);
lli q;
cin>>q;
while(q--)
{
ans=0;
lli a, b;
cin>>a>>b;
if(a==3)
{
// v[b].ff+1 since superior is not counted
if(v[b].ff+1<=v[b].ss)
{
lli an=query(1,0,n-1,v[b].ff+1,v[b].ss);
cout<<an<<endl;
}
else
cout<<"0"<<endl;
}
else if(a==1)
{
// v[b].ff+1 since superior is not counted
if(v[b].ff+1<=v[b].ss)
update(1,0,n-1,v[b].ff+1,v[b].ss,1);
}
else
{
// v[b].ff+1 since superior is not counted
//cout<<" q range "<<v[b].ff+1<<" "<<v[b].ss<<endl;
if(v[b].ff+1<=v[b].ss)
update(1,0,n-1,v[b].ff+1,v[b].ss,0);
}
}
return 0;
}
Initially all soldiers are awake. There is only one soldier who has soldier 1 as his superior i.e. soldier 3. So the answer of the first Type 3 order is 1. After the order "2 1", all soldiers who have 1 as one of their superiors (here, only soldier 3) will go to sleep. Therefore, the answer of the next order "3 1" is 0.
--------------------------------------------editorial----------------------------------------------------------------------------------------
my editorial
construct a dfs tree which will give all lower of any superior.also note thta this is linear tree.........
now
for query 3 just give no of solder awake (except superior );
now there are many time query can be in a range l to r, of any type 2,3 ,, main observation is that consider last update in the range , since what ever will be the query befor wiil not affact sice effect of latest querry will affect now.........
------------------------------------------------------------------------------------------------------------------------------------------------
First of all, construct a tree of the hierarchy given in the question. The commander of the army will be the root of the tree and there will be an edge between every soldier and his immediate superior. All the soldiers that have a soldier x as their superior will be present in the subtree rooted at x.
Next, we convert the tree into an array, arr, by performing a DFS traversal of this tree and noting down the DFS numberfor each node. The DFS number tells us about the order in which the nodes were encountered during DFS. Eg. the DFS number of root will be 0, that of the next node visited will be 1 and so on. The position of a node in array will be equal to its DFS number. For each node, record the smallest and largest DFS number in its subtree. If the smallest DFS number in a subtree is a and the largest DFS number is b, it means that the subtree is represented by the subarray [a, b] in arr.
For a soldier x, arr [x.DFSnumber] ==1 if the soldier is awake and 0 if he is asleep. As all soldiers are initially awake, set all elements in arr to 1.
For a soldier x, arr [x.DFSnumber] ==1 if the soldier is awake and 0 if he is asleep. As all soldiers are initially awake, set all elements in arr to 1.
The problem is now converted into a Range Update, Range Query problem. Now, build a segment tree on arr.
For a type-1 or type-2 query like: 1 x or 2 x, we'll first find the concerned range in the array. The concerned range will be [a+1 , b] where a is the smallest DFS number in the subtree rooted at x and b is the largest DFS number in the subtree rooted at x. (We use a+1 instead of a because we don't have to change the state of the soldier x; we have to change state of only the soldiers that have x as their superior ) Depending on whether the query is type-1 or type-2, either convert all numbers in [a+1 , b ] to 1 or 0 respectively. This can be done by Range Update using Lazy Propagation in Segment Tree.
For a type-3 query, first find the range in the same way as mentioned above and perform a range query operation to count the summation of numbers in [a+1 , b].
For a type-1 or type-2 query like: 1 x or 2 x, we'll first find the concerned range in the array. The concerned range will be [a+1 , b] where a is the smallest DFS number in the subtree rooted at x and b is the largest DFS number in the subtree rooted at x. (We use a+1 instead of a because we don't have to change the state of the soldier x; we have to change state of only the soldiers that have x as their superior ) Depending on whether the query is type-1 or type-2, either convert all numbers in [a+1 , b ] to 1 or 0 respectively. This can be done by Range Update using Lazy Propagation in Segment Tree.
For a type-3 query, first find the range in the same way as mentioned above and perform a range query operation to count the summation of numbers in [a+1 , b].
--------------------------------------------------------------code----------------------------------------------------------------------------
using namespace std;
typedef long long int lli;
lli arr[1000000];
struct abc
{
lli sleep;
lli awk;
} tree[1000000];
lli lazy[1000000];
list<lli> li[1000000];
lli visited[1000000];
vector<pair<lli,lli> > v;
lli times;
lli ans=0;
#define mp make_pair
#define pb push_back
#define inf 999999999
#define ff first
#define ss second
lli query(lli node,lli start,lli end,lli r1,lli r2)
{
if(lazy[node]!=0)
{
if(lazy[node]==1)
{
tree[node].awk=(end-start)+1;
tree[node].sleep=0;
if(start!=end)
{
lazy[2*node]=1;
lazy[2*node+1]=1;
}
}
else
{
tree[node].sleep=(end-start)+1;
tree[node].awk=0;
if(start!=end)
{
lazy[2*node]=-1;
lazy[2*node+1]=-1;
}
}
lazy[node]=0;
}
if(start>end || r1>end || r2<start) return 0;
if(r1<=start && r2>=end)
{
return tree[node].awk;
}
else
{
lli q1=query(2*node,start,(start+end)/2,r1,r2);
lli q2=query(2*node+1,((start+end)/2)+1,end,r1,r2);
ans+=q1+q2;
return q1+q2;
}
}
void update(lli node ,lli start,lli end,lli r1,lli r2,lli type)// type is type of update 1 means wake all under that superior
{
if(lazy[node]!=0)
{
if(lazy[node]==1)
{
tree[node].awk=(end-start)+1;
tree[node].sleep=0;
if(start!=end)
{
lazy[2*node]=1;
lazy[2*node+1]=1;
}
}
else
{
tree[node].sleep=(end-start)+1;
tree[node].awk=0;
if(start!=end)
{
lazy[2*node]=-1;
lazy[2*node+1]=-1;
}
}
lazy[node]=0;
}
if(r1>end || r2<start || start>end) return ;
if(r1<=start && r2>=end)
{
if(type==1)
{
tree[node].awk=(end-start)+1;
tree[node].sleep=0;
if(start!=end)
{
lazy[2*node]=1;
lazy[2*node+1]=1;
}
}
else
{
tree[node].sleep=(end-start)+1;
tree[node].awk=0;
if(start!=end)
{
lazy[2*node]=-1;
lazy[2*node+1]=-1;
}
}
return ;
}
update( 2*node ,start,(start+end)/2,r1,r2,type);
update( 2*node+1 ,(start+end)/2+1,end,r1,r2,type);
tree[node].sleep=tree[2*node].sleep+tree[2*node+1].sleep;
tree[node].awk=tree[2*node].awk+tree[2*node+1].awk;
}
void build(lli node , lli start,lli end)
{
if(start==end)
{
// since initily all solders are awake .
tree[node].sleep=0;
tree[node].awk=1;
}
else if(start>end) return ;
else
{
build(2*node,start,(start+end)/2);
build(2*node+1,((start+end)/2)+1,end);
tree[node].sleep=tree[2*node].sleep+tree[2*node+1].sleep;
tree[node].awk=tree[2*node].awk+tree[2*node+1].awk;
}
}
/// finding starting and ending time of all solders all soleders b/w start_time+1 to end _time will be under thta solder
// also tree is lenear and rooted at node 0.
lli dfs(lli start)
{
list<lli>:: iterator it;
it=li[start].begin();
// start time of node start
v[start].first=times;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(!visited[*it])
{
visited[*it]=1;
times++;
dfs(*it);
}
}
// end time of node start
v[start].second=times;
}
int main()
{
lli n;
cin>>n;
lli st;
for(lli i=1;i<=n;i++)
{
lli a;
cin>>a;
if(a==0)st=i;
li[a].pb(i);
}
for(lli i=0;i<n+1;i++)
{
v.pb(mp(0,0));
}
v[0].first=0;
dfs(st);
build(1,0,n-1);
lli q;
cin>>q;
while(q--)
{
ans=0;
lli a, b;
cin>>a>>b;
if(a==3)
{
// v[b].ff+1 since superior is not counted
if(v[b].ff+1<=v[b].ss)
{
lli an=query(1,0,n-1,v[b].ff+1,v[b].ss);
cout<<an<<endl;
}
else
cout<<"0"<<endl;
}
else if(a==1)
{
// v[b].ff+1 since superior is not counted
if(v[b].ff+1<=v[b].ss)
update(1,0,n-1,v[b].ff+1,v[b].ss,1);
}
else
{
// v[b].ff+1 since superior is not counted
//cout<<" q range "<<v[b].ff+1<<" "<<v[b].ss<<endl;
if(v[b].ff+1<=v[b].ss)
update(1,0,n-1,v[b].ff+1,v[b].ss,0);
}
}
return 0;
}
No comments:
Post a Comment