NJUST 1746 Similar Number(南京邀请赛 J题) - c++编程基础

没想法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
#include
#include
#include
#include
#include
#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];
mapmymap;
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;