萌新莫队92分求助

回复帖子

@愛蜜の守護者  2021-05-05 10:52 回复

Rt,挂了#2和#16两个点

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll p;
char s[200005];
int m;
ll n;

void Work1();

const int B=525;
#define check(x) ((x-1)/B+1)
struct zz{
    int id;
    int l,r;
}q[2000005];
int ans[2000005]={};
int tot[2000005]={};
int col[2000005]={};
bool cmp(zz x,zz y){
    if(check(x.l)==check(y.l))
        return x.r<y.r;
    return x.l<y.l;
}

ll a[2000005];
ll lsh[2000005];
ll now=0;

void Add(int x){
    now-=tot[x]*(tot[x]-1)/2;
    tot[x]++;
    now+=tot[x]*(tot[x]-1)/2;
}
void Del(int x){
    now-=tot[x]*(tot[x]-1)/2;
    tot[x]--;
    now+=tot[x]*(tot[x]-1)/2;
}

int main(){
    scanf("%lld",&p);
    cin>>s+1;
    n=strlen(s+1);
    if(p==2||p==5){
        Work1();
        return 0;
    }

    ll nownow=1;
    for(int i=n;i>=1;i--){
        a[i]=(ll)(nownow*(s[i]-'0')%p+a[i+1])%p;
        nownow*=10ll;
        nownow%=p;
        lsh[i]=a[i];
//      printf("QWQ nownow%d a[i]:%d\n",nownow,a[i]);
    }
    sort(lsh+1,lsh+n+1);
    int len=unique(lsh+1,lsh+n+2)-lsh-1;
    for(int i=1;i<=n+1;i++){
        a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
//      printf("%d %d %d\n",i,a[i],lsh[a[i]]);
    }

    cin>>m;
    for(int i=1;i<=m;i++){
        q[i].id=i;
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].r++;
    }
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
//      printf("l:%d r:%d q[%d]:l:%dr:%d ",l,r,i,q[i].l,q[i].r);
        while(q[i].l>l) Del(a[l++]);
//      printf("%d ",now);
        while(q[i].l<l) Add(a[--l]);
//      printf("%d ",now);
        while(q[i].r>r) Add(a[++r]);    
//          printf("Fuck:%d ",now);
//      printf("%d ",now);
        while(q[i].r<r) Del(a[r--]);
//      printf("%d \n",now);
        ans[q[i].id]=now;
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

void Work1(){
    bool f[15]={};
    ll sum[100005];
    ll pos[100005];
    if(p==5)
        f[0]=f[5]=1;
    else
        for(int i=0;i<=8;i+=2)  f[i]=1;
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+f[s[i]-'0'];
        pos[i]=pos[i-1]+f[s[i]-'0']*i;
    }
    cin>>m;
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%lld\n",pos[r]-pos[l-1]-(sum[r]-sum[l-1])*(l-1));
    }
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。