沒想法J題竟然這麼水。。。。。
強制在線之後以為是一個神奇的數據結構題。。。
不過自己肯定是想不到。。。。感謝戴神的指導。。。
首先預處理出對於每一個數，右邊最靠近的相似的數，用r[i]表示
將降序排列後，map搞定。。。
接下來戴神給了神奇的做法，大概是求出 >=1的區間數 減去 >=2的區間數
然後我還是不會。。。。
對於每一個點，求出右邊最近的包括一個相似對的位置，one[i]
表示的是[i,one[i]] …… [i,n] 所有的區間都至少有一個相似對。
而且[i,one[i]-1]不包括相似對。。。。
然後同理處理出two[i],表示區間內至少有兩個相似對。。。
對於one[i]=min(one[i-1],r[i]) 表示i當前這個位置形成一對，或者i-1之後形成一對。
對於two[i]=min(two[i-1], r[r[i]], max(r[i],one[i-1])) 表示i-1之後形成了兩對，i當前這個位置形成兩對，或者i-1之後形成一對，當前位置形成一對。。。。。
明顯one,two具有非遞增性質。。。
至於查詢，暴力情況
for(int i=l;i<=r;i++) if(one[i]<=r) sum+=r-one[i]+1;
for(int i=l;i<=r;i++) if(two[i]<=r) sum-=r-two[i]+1;
由於非遞增，那麼就能二分，然後搞一下區間和。。。。
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#define LL long long
using namespace std;
const int N = 100005;
int n,m,a[N],r[N];
int one[N],two[N];
LL sum_one[N],sum_two[N];
char str[10];
map<string,int>mymap;
bool cmp(char a,char b){
return a>b;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
mymap.clear();
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n;i>=1;i--){
string s="";
int t=a[i];
while(t){
s+=(char)(t%10+'0');
t/=10;
}
sort(s.begin(),s.end(),cmp);
if(mymap.find(s)==mymap.end())
r[i]=n+1;
else r[i]=mymap[s];
mymap[s]=i;
}
r[n+1]=n+1;
one[n+1]=two[n+1]=n+1;
for(int i=n;i>=1;i--){
one[i]=min(one[i+1],r[i]);
two[i]=min(two[i+1],r[r[i]]);
two[i]=min(two[i+1],max(r[i],one[i+1]));
}
for(int i=1;i<=n;i++){
sum_one[i]=sum_one[i-1]+one[i];
sum_two[i]=sum_two[i-1]+two[i];
}
LL ans=0;
while(m--){
LL l,r;int pos;
scanf("%lld%lld",&l,&r);
l+=ans;r-=ans;
pos=upper_bound(one+l,one+r,r)-one-1;
ans=(pos-l+1)*r-(sum_one[pos]-sum_one[l-1])+(pos-l+1);
pos=upper_bound(two+l,two+r,r)-two-1;
ans-=(pos-l+1)*r-(sum_two[pos]-sum_two[l-1])+(pos-l+1);
printf("%lld\n",ans);
}
}
return 0;
