Author: Vishal
Tester: Vishal
Editorialist: Vishal
DIFFICULTY:
HARD
PREREQUISITES:
Euler Tour, Segment Trees, Lazy Propagation
PROBLEM:
Given queries, you have to either increase the values of all nodes in a subtree by some value, or find the number of nodes with an odd value in a subtree.
EXPLANATION:
The first observation we can make is since only the parity of the numbers matters, and not the numbers themselves, we can represent all values using bits, with 1 representing Odd and 0 representing Even.
The second observation to be made is, during the Update queries, adding an even number to all values does not change their parity. So update queries with an even value can be ignored.
If the Update query has an odd number, all the bits in the subtree must be flipped.
We can flatten the tree into an array and use a Segment Tree to flip all bits in a range and also find the number of set bits in any range.
Since the Segment Tree takes O(log n) time per query, the overall time complexity is O(N + QlogN).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int MAX = 4e5+3;
int arr[MAX],lazy[MAX],tree[MAX],in[MAX],out[MAX],cnt,n;
vector<int> adj[MAX];
/*Flips bits on the range [i, j]*/
void flip_bits(int node, int a, int b, int i, int j) {
if(lazy[node] != 0)
{ // This node needs to be updated
tree[node] = b-a+1-tree[node]; // Update it
if(a != b)
{
lazy[node*2]^=1; // Mark child as lazy
lazy[node*2+1]^=1; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a > b || a > j || b < i) // Current segment is not within range [i, j]
return;
if(a >= i && b <= j)
{ // Segment is fully within range
tree[node] = b-a+1-tree[node];
if(a != b)
{ // Not leaf node
lazy[node*2]^=1;
lazy[node*2+1]^=1;
}
return;
}
flip_bits(node*2, a, (a+b)/2, i, j); // Updating left child
flip_bits(1+node*2, 1+(a+b)/2, b, i, j); // Updating right child
tree[node] = tree[node*2] + tree[node*2+1]; // Updating root with max value
}
/* Query tree to get number of set bits in the range [i, j] */
int set_bits(int node, int a, int b, int i, int j) {
if(a > b || a > j || b < i) return 0; // Out of range
if(lazy[node] != 0)
{ // This node needs to be updated
tree[node] = b-a+1-tree[node]; // Update it
if(a != b)
{
lazy[node*2]^=1; // Mark child as lazy
lazy[node*2+1]^=1; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a >= i && b <= j) // Current segment is totally within range [i, j]
return tree[node];
int q1 = set_bits(node*2, a, (a+b)/2, i, j); // Query left child
int q2 = set_bits(1+node*2, 1+(a+b)/2, b, i, j); // Query right child
int res = q1+q2; // Return final result
return res;
}
// DFS to Flatten array
void dfs(int node,int par)
{
in[node]=cnt++;
if(arr[node]&1) flip_bits(1, 0, n-1, in[node], in[node]); //If arr[node] is odd, make this bit 1
for(int i:adj[node])
{
if(i!=par)
dfs(i,node);
}
out[node]=cnt;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
cin>>n>>q;
for(int i=0;i<n-1;++i)
{
int x,y;
cin>>x>>y;
x--,y--;
adj[x].emplace_back(y),adj[y].emplace_back(x);
}
for(int i=0;i<n;++i)
cin>>arr[i];
dfs(0,0);
while(q--)
{
int t;
cin>>t;
if(t==1)
{
int x,y;
cin>>x>>y;
x--;
if(y&1) flip_bits(1, 0, n-1, in[x], out[x]-1);
// If y is odd, flip bits in the subtree
}
else
{
int x;
cin>>x;
x--;
cout<<set_bits(1, 0, n-1, in[x], out[x]-1)<<"\n";
// Print number of set bits in the range
}
}
}