Similar Number
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 108 Accepted Submission(s): 9
Problem Description
We can call two numbers “similar” if their lengths are equal and we can make a number ‘’similar’’ through swapping some digits of itself. For instance, 123 is similar to 321 but 12 is not similar to 120.
A sequence can be called “similar sequence” if this sequence has only one pair of ‘’similar’’ numbers.
Now, Zero writes a series of integers and he needs you to answer his queries online. For each query, he gives you two integers l and r, which represent the two endpoints of a segment. He wants to know how many successive subsequences are “similar sequences”.
A sequence can be called “similar sequence” if this sequence has only one pair of ‘’similar’’ numbers.
Now, Zero writes a series of integers and he needs you to answer his queries online. For each query, he gives you two integers l and r, which represent the two endpoints of a segment. He wants to know how many successive subsequences are “similar sequences”.
Input
There are multiple test cases.
In the first line of every test case there are two integers n (0<n<=100000) and m (0<=m<=100000), meaning that the sequence contains n integers and m queries.
The next line contains n integers a[i] (1<=i<=n, a[i] <= 109), which represent the integers in the sequence.
After that, there are m lines, each line containing two integers l and r.
Zero thinks that it is too simple for him to solve this problem, so he sets a variable k. In the beginning of each test case, k = 0. For each query, he sets l = l + k and r = r - k, Zero guarantees that 0<l<=r<=n, then make k the answer of this query.
The input ends with EOF.
In the first line of every test case there are two integers n (0<n<=100000) and m (0<=m<=100000), meaning that the sequence contains n integers and m queries.
The next line contains n integers a[i] (1<=i<=n, a[i] <= 109), which represent the integers in the sequence.
After that, there are m lines, each line containing two integers l and r.
Zero thinks that it is too simple for him to solve this problem, so he sets a variable k. In the beginning of each test case, k = 0. For each query, he sets l = l + k and r = r - k, Zero guarantees that 0<l<=r<=n, then make k the answer of this query.
The input ends with EOF.
Output
For each query, output an integer, and there is no blank line after each test.
Sample Input
5 5 2 2 2 2 2 1 4 1 8 1 4 1 6 -1 5
Sample Output
3 1 1 3 0