主题

主题

 
   

D. Serega and Fun

原题:http://codeforces.com/problemset/problem/455/D

Serega loves fun. However, everyone has fun in the unique manner. Serega has fun by solving query problems. One day Fedor came up with such a problem.

You are given an array a consisting of n positive integers and queries to it. The queries can be of two types:

Make a unit cyclic shift to the right on the segment from l to r (both borders inclusive). That is rearrange elements of the array in the following manner:

a[l], a[l + 1], ..., a[r - 1], a[r] → a[r], a[l], a[l + 1], ..., a[r - 1].

Count how many numbers equal to k are on the segment from l to r (both borders inclusive).

Fedor hurried to see Serega enjoy the problem and Serega solved it really quickly. Let's see, can you solve it?

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of elements of the array. The second line contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).

The third line contains a single integer q (1 ≤ q ≤ 105) — the number of queries. The next q lines contain the queries.

As you need to respond to the queries online, the queries will be encoded. A query of the first type will be given in format: 1 l'i r'i. A query of the second type will be given in format: 2 l'i r'i k'i. All the number in input are integer. They satisfy the constraints: 1 ≤ l'i, r'i, k'i ≤ n.

To decode the queries from the data given in input, you need to perform the following transformations:

li = ((l'i + lastans - 1) mod n) + 1; ri = ((r'i + lastans - 1) mod n) + 1; ki = ((k'i + lastans - 1) mod n) + 1.

Where lastans is the last reply to the query of the 2-nd type (initially, lastans = 0). If after transformation li is greater than ri, you must swap these values.

Output

For each query of the 2-nd type print the answer on a single line.

Examples

input

7

6 6 2 7 4 2 5

7

1 3 6

2 2 4 2

2 2 4 7

2 2 2 5

1 2 6

1 1 4

2 1 7 3

output

2

1

0

0

input

8

8 4 2 2 7 7 8 8

8

1 8 8

2 8 1 7

1 8 1

1 7 3

2 8 8 3

1 1 4

1 2 7

1 4 5

output

2

0


题目大意:

给出一个长度为n的序列,要求支持:

  1. 将一个区间的尾元素放到这个区间之首。

  2. 查询区间有多少个数字等于k。

强制在线。


个人解法:

很简单的块状链表。(据说有很优美的Splay与树套树的做法)

自认为写了一份还看得的块状链表。对于修改,我们删除一次插入一次即可。对于查询,我们分块维护桶即可。

看到网上有人说,块要开到O(sqrt(nlogn)),我认为不科学。按照理论的分析,时间复杂度应该是Threshold=Num的时候最优,即块的大小为O(sqrt(n))。大概只是因为数组开小了导致的TLE罢了……

但是这样空间难以接受,因为要分块维护桶,我们考虑使用牺牲时间换取空间的做法。因为我们需要减少块的个数,所以把块的大小开大,块的数量减少。

我最终开的是O(n*10)的块。


代码如下:

http://codeforces.com/contest/455/submission/25661818

 
 
评论