All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Big Number Array
Tag(s):

Advanced Data Structures, Data Structures, Easy-Medium, Fenwick Tree, Segment Trees

Problem
Editorial
Analytics

Given an array of n integers. Initially, all elements are zero. You are asked to complete q queries of two kinds:

1 x y l r: for each i in range [x, y] flip the l-th bit to r-bit of i-th element.

2 x y: check if x-th element equals y-th element.

Input Format

The first line contains an integer T denoting the number of test cases. Each test case is described as follow:

A line contains two space-separated integers n, q denoting the size of array and the number of queries. q queries follow are described as in the statement.

Output Format

For each query of kind 2, output a single line contains "YES" if two numbers are equal, otherwise "NO".

Constraints

  • 1 ≤ T ≤ 100
  • 1 ≤ n ≤ 105
  • 1 ≤ q ≤ 105
  • 1 ≤ sum of n over all test cases ≤ 2.105
  • 1 ≤ sum of q over all test cases ≤ 2.105
  • 1 ≤ xyn
  • 0 ≤ lr ≤ 109

 

SAMPLE INPUT
1
2 4
1 1 1 5 6
2 1 2
1 2 2 5 6
2 1 2

SAMPLE OUTPUT
NO
YES
Explanation

The initial array is [0, 0].

Query 1: 1 1 1 5 6, the array becomes [96, 0]. Note that 96 = 25 + 26.

Query 2: 2 1 2, output "NO".

Query 3: 1 2 2 5 6, the array becomes [96, 96].

Query 4: 2 1 2, output "YES".

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 64 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?