## Mock CCC '23 1 S5 - The Obligatory Data Structures Problem

View as PDF

Points: 25 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem type

Mock CCC wouldn't be a real mock CCC without a data structures problem, would it?

You're given two sequences of integers and , and you need to support two operations:

• Update(l, r, x) - set through to all be equal to .
• Query(l, r) - compute the number of indices where and .

DMOJ has been having some issues with test data taking up too much space, so you're going to generate the operations and solve the problem for us!

#### Constraints

In tests worth 1 mark, .

In tests worth an additional 2 marks, .

In tests worth an additional 4 marks, .

#### Input Specification

The first line contains four integers, , , , and .

The second line contains integers, the sequence .

The third line contains integers, the sequence .

Because the number of operations is large, you'll be generating the operations using the following code.

int a = A, b = B, C = ~(1<<31), M = (1<<16)-1;
int rnd(int last) {
a = (36969 + (last >> 3)) * (a & M) + (a >> 16);
b = (18000 + (last >> 3)) * (b & M) + (b >> 16);
return (C & ((a << 16) + b)) % 1000000000;
}

The intended solution does not exploit the random number generation used; it would work even if the operations were hand-constructed.

For the th operation, call rnd three times, setting to be rnd(last) % n + 1, then to be rnd(last) % n + 1, then to be rnd(last) + 1. If , then swap them. if is even, the th operation is Query(l, r). Otherwise, it is Update(l, r, x).

last is always the last return value of Query. last starts out being 0.

#### Output Specification

Let be if the th operation was an Update, and the result of the Query operation otherwise. Output modulo 998244353.

#### Sample Input

5 10 5 6
5 4 5 2 1
1 2 2 4 5

#### Sample Output

87