Grouping Boys by Clothing Characteristics

Zarathustra was once listening to a wise man talk about the virtues of sleep – when he suddenly became bored and started observing the boys in the audience. He noticed that each boy’s clothing had 60 distinct features; the i^th feature has a characteristic value of \(2^{i-1}\). When he compares any two boys, for each feature that appears on exactly one of them (and not on the other) he accumulates a disgust score equal to that feature’s value. In other words, the disgust score for two boys is precisely the bitwise XOR of their outfit‐values.

Zarathustra wants to partition the boys into several groups such that within any group, no matter which two boys you pick, their pairwise disgust score is less than a given threshold \(x\). (Note that a group consisting of a single boy is always good.) He is curious: what is the maximum number of boys that can be placed in one such “good” group? Moreover, from time to time a boy goes home to change his clothes – his outfit (and thus his feature‐value) may change. Your task is to answer his queries.

Problem Summary

• You are given \(n\) boys and an integer \(x\). Each boy’s outfit is encoded as an integer. The disgust score for two boys is defined as the XOR of their outfit values. A group is "good" if for every pair of boys in the group the value of their XOR is < \(x\).
• You will then process \(q\) queries. A query may ask for the maximum size of a good group, or update the outfit of a given boy.

Key observation

Notice that each outfit is a sum of distinct powers of two. The XOR of two outfits essentially picks out the features on which they differ. In order for the XOR of any two outfits to be less than \(x\), a necessary condition is that all boys chosen must share the same configuration in all the high–order bits (above a certain position). In fact, if we let \(p=\lfloor \log_2(x)\rfloor\) so that \(2^p \le x < 2^{p+1}\) and write \(x=2^p + r\) (with \(0 \le r < 2^p\)), then any two boys coming from different high–bit groups (when dividing their outfit by \(2^{p+1}\)) would differ in those high bits and yield an XOR of at least \(2^{p+1}\), which is \(\ge x\).

Thus, the problem reduces to processing the boys partitioned by their high bits (i.e. \(high = \lfloor outfit / 2^{p+1}\rfloor\)). For the boys in each such block, their outfits (more precisely, their lower \(p+1\) bits) are considered. In each block, if we further split according to the most significant bit of the lower part, then any two boys within the same sub–group automatically satisfy the condition (their XOR is less than \(2^p\)). When considering one boy from each of the two sub–groups, the XOR becomes \(2^p\) plus the XOR of the remaining \(p\) bits. Hence, a conflict (i.e. a pair whose XOR \(\ge x\)) arises only if this latter part is \(\ge r\).

This observation allows a solution that in each block finds the maximum subset of boys with pairwise XOR less than \(x\) by splitting the block into two groups and then solving a bipartite "conflict removal" problem via maximum matching (using Kőnig’s theorem). The maximum size obtainable within that block is the maximum of:

1. the size of one sub–group, or
2. the sum of the sizes of both sub–groups minus the size of a minimum vertex cover (which equals the maximum matching) in the bipartite conflict graph.

The final answer is the maximum over all high–bit groups. Additionally, update queries simply change the outfit value for one boy, and subsequent queries must use the updated values.

inputFormat

The first line contains three integers \(n\), \(q\) and \(x\) (with \(x > 0\)), where \(n\) is the number of boys, \(q\) is the number of queries, and \(x\) is the threshold.

The second line contains \(n\) non–negative integers: the initial outfit values for boys 1 through \(n\).

Each of the following \(q\) lines contains a query. There are two types of queries:

• Update Query: "1 i v" – update the outfit of boy \(i\) to the new value \(v\).
• Answer Query: "2" – output the maximum size of a good group (i.e. a subset of boys such that the XOR of every pair is less than \(x\)).

It is guaranteed that at least one query is of type 2.

outputFormat

For each query of type 2, output a single integer – the maximum number of boys that can form a good group under the current outfit configuration.

sample

3 3 8
1 1 2
2
1 2 2
2

3
3

</p>