2015
09-17

# Similar Number

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 260    Accepted Submission(s): 62

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”.

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.

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

AC代码如下：

#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
map<string,int> match;
char s[100010][20];
int n,m,point[100010],one[100010],two[100010],sum_one[100010],sum_two[100010];
bool cmp(char a,char b)
{
return a<b;
}
int main()
{
int i,j,k,a,b,len,c,pos;
ll l,r,ans;
while(~scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
scanf("%s",s[i]);
match.clear();
for(i=n;i>=1;i--)
{
len=strlen(s[i]);
sort(s[i],s[i]+len,cmp);
k=match[s[i]];
if(k==0)
point[i]=n+1;
else
point[i]=k;
match[s[i]]=i;
}
a=n+1;b=n+1;
for(i=n;i>=1;i--)
{
c=point[i];
if(c<a)
b=a,a=c;
else if(c<b)
b=c;
one[i]=a;
two[i]=b;
}
for(i=1;i<=n;i++)
{
sum_one[i]=sum_one[i-1]+(one[i]-1);
sum_two[i]=sum_two[i-1]+(two[i]-1);
}
ans=0;
while(m--)
{
scanf("%I64d%I64d",&l,&r);
l+=ans;
r-=ans;
ans=0;
pos=upper_bound(one+1,one+n,r)-one-1;
if(pos>=l)
ans+=r*(pos-l+1)-(sum_one[pos]-sum_one[l-1]);

pos=upper_bound(two+1,two+n,r)-two-1;
if(pos>=l)
ans-=r*(pos-l+1)-(sum_two[pos]-sum_two[l-1]);
printf("%I64d\n",ans);
}
}
}