Truy vấn k trực tuyến (K-Query Online)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $a_1,\ldots,a_n$ và các truy vấn trực tuyến. Gọi last là đáp án truy vấn trước, ban đầu bằng $0$. Với một dòng gồm $x,y,z$, giải mã $i=x\oplus last$, $j=y\oplus last$, $k=z\oplus last$. Nếu $i<1$ thì đặt $i=1$; nếu $j>n$ thì đặt $j=n$. Nếu $i>j$ thì đáp án là $0$; ngược lại hãy đếm số phần tử lớn hơn $k$ trong $a_i..a_j$. Sau đó cập nhật last bằng đáp án vừa in.

Dữ liệu vào

Dòng đầu chứa $n$. Dòng thứ hai chứa dãy. Dòng thứ ba chứa $q$. Mỗi trong $q$ dòng sau chứa ba số mã hóa $x,y,z$.

Kết quả

In đáp án từng truy vấn theo đúng thứ tự; mỗi đáp án trở thành last cho truy vấn kế tiếp.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 3000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n\le30000$
• $1\le q\le200000$
• $1\le a_i\le10^9$

Ví dụ

Input

6
8 9 3 5 1 9
5
2 3 5
3 3 7
0 0 11
0 0 2
3 7 4

Output

1
1
0
0
2

Giải thích

Do mỗi dòng sau phụ thuộc đáp án trước, các truy vấn không thể sắp xếp lại. Với mẫu, năm đáp án lần lượt là 1,1,0,0,2.