## CPC '19 Contest 1 P6 - Maintaining Some Coins

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 32M

Authors:
Problem type

Angie is maintaining some coins!

She begins with an array of coins, and then assigns each coin with a number . Next, she will perform operations of one of the following types on the coins.

• I i x: Insert a coin with value directly after coin . If then the coin is inserted at the beginning
• D j: Delete coin
• C l r x: Output how many coins between coin and (inclusive) have a value of

Because the amount of coins can grow very large, she has decided to enlist your help to keep track of the coins. Can you help her do it?

Important Note: The test cases are Online Enforced. That means all numbers in the input will be encrypted with the formula , where is the original number in the query, is the Bitwise XOR operation, and is the answer to the last C operation given (or if none have been answered yet).

#### Constraints

is the length of the coin array at the time of the query.

All elements in the initial array and all inserted elements are distinct.

#### Input Specification

The first line of input will contain the space separated integers and .

The second line will contain space separated integers: .

The final lines will contain operations in the format described above.

#### Output Specification

Output the answer for each C query on its own line.

#### Sample Input

10 10
5 1 6 1 5 1 2 2 7 8
C 2 5 1
D 0
C 0 6 3
I 1 4
I 11 11
C 0 2 4
C 8 9 8
I 2 7
C 0 7 7
C 3 14 0

#### Sample Input (Not Encrypted)

For your convenience, here is a version of the sample input that is NOT encrypted. Remember, all of the real test files will be encrypted (like the input above).

10 10
5 1 6 1 5 1 2 2 7 8
C 2 5 1
D 2
C 2 4 1
I 0 5
I 10 10
C 1 3 5
C 10 11 10
I 3 6
C 1 6 6
C 1 12 2

#### Sample Output

2
1
2
1
2
2

#### Sample Explanation

This is what the array begins as: 5 1 6 1 5 1 2 2 7 8

The first query asks for this range: 5 [1 6 1 5] 1 2 2 7 8

The second query changes the array to this: 5 6 1 5 1 2 2 7 8

The third query asks for this range: 5 [6 1 5] 1 2 2 7 8

The fourth query changes the array to this: 5 5 6 1 5 1 2 2 7 8

The fifth query changes the array to this: 5 5 6 1 5 1 2 2 7 8 10

The sixth query asks for this range: [5 5 6] 1 5 1 2 2 7 8 10

The seventh query asks for this range: 5 5 6 1 5 1 2 2 7 [8 10]

The eighth query changes the array to this: 5 5 6 6 1 5 1 2 2 7 8 10

The ninth query asks for this range: [5 5 6 6 1 5] 1 2 2 7 8 10

The tenth and final query asks for the entire array.