Ross's friends

0

0 votes
Segment tree
Problem

Ross is remembering his college days and how he designed an algorithm to join a friend circle - 

There were N people in his class and each had a favourite number. Ross collected all their favourite numbers in the array A

Any set of people formed a suitable friend circle if the bitwise xor of all the favourite numbers in a group was strictly greater than a given Ross Rating (a positive integer) R given by ross for that group of people.

But there was a catch. The favourite numbers kept changing but Ross had his sources which kept him updated.

Ross gives you q queries of two types-

  •  Type 'u' indicates updation of a favourite number at the index p with a new value x.
  • Type 'c' where, in each query, he gives an index range l,r (both inclusive) from the array and the ross rating for that group.  

For every query of the type 'c', you have to find if the people in the given group form a friend circle or not.

NOTE - Indexing starts from 1

Input format -

  • The first line contains the number of Test Cases T
  • For each Test Case, 
    • First line contains a single integer N denoting the number of students in ross's class. 
    • The second line contains N space separated integers of the array A denoting their favourite numbers.
    • The third line contains a single integer q  denoting the number of queries.
    • Each of the next q lines contains either of the following- 
      • Character 'c' followed by three space separated integers l , r and R where l,r are the indexes of some range in the array (both inclusive) and R is the Ross rating.
      • Character 'u' followed by two space separated integers p,x denoting that the value of the array at position p Has to be updated to x

Output format -.

  • For each query of type 'c', a line should be printed containing "YES"  if a suitable friend circle is formed by the people in the given range and "NO" otherwise. (without quotes)

Constraints -

  • 1T100
  • 3N100000
  • 1Ai109
  • 1l,r,pN
  • 1x,R109
  • 1q1000

 

Time Limit: 0.5
Memory Limit: 256
Source Limit:
Explanation

- For the first query, 26=4 hence the output is NO

- In the second query 2 is changed to 3

- In the third query, 36=5 hence, the answer is YES

Editor Image

?