[Ynoi2079] r2pspc题解

· · 题解

[Ynoi2079] r2pspc题解

题目传送门

（看能不能来个首发，求求管理员给个过吧）

看到题目，不要求强制在线，想到莫队算法。

数据范围比较大，但是发现其实很多数值并没有用到，所以要先进行离散化。

只需要把可能出现的数位丢进去离散化就可以了。

然后对于莫队的 add 和 del，给一种超时 96 分的写法：

void add(int x){
    int p=a[x];
    while(c[p]) c[p]=0,tmp--,p++;
    tmp++,c[p]=1;
}
void del(int x){
    int p=a[x];
    while(!c[p]) c[p]=1,tmp++,p++;
    tmp--,c[p]=0;
}

这样时间复杂度好像是 O(nm)，会超时 (但是数据好像比较水并且根本卡不满所以有 96 分)。

考虑优化这个过程，可以用高效的加法对上面的 c 数组进行压位，时间复杂度就可以通过此题。(但是复杂度好像是 \dfrac{nm}{64}，但是所有点都能在 0.5s 以内跑过），成功抢到最优解。

给出代码：

#include<bits/stdc++.h>
#define int long long
#define siz2 60
using namespace std;
int power[100];
int n,m,a[400005],ans[1000005],cnt=1,pos[400005],siz,len,tmp,b[5000005],l2[400005],r2[400005],pos2[400005],len2;
namespace ae86{
    const int bufl=1<<18;
    char buf[bufl],*s=buf,*t=buf;
    inline int fetch(){
        if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
        return*s++;
    }
    inline int read(){
        int a=0,c=fetch();
        while(!isdigit(c)) c=fetch();
        while(isdigit(c))a=a*10+c-48,c=fetch();
        return a;
    }
}
using ae86::read;
struct node{
    int l,r,d,id;
}tt[1000005];
bool cmp(node a,node b){
    if(pos[a.l]!=pos[b.l]) return a.l<b.l;
    if(pos[a.l]%2==1) return a.r<b.r;
    return a.r>b.r;
}
bool c[3000005];
unsigned int g[3000005];
inline void add(int x){
    int pos=pos2[x],l=l2[pos2[x]],r=r2[pos2[x]];
    tmp-=__builtin_popcountll(g[pos]);
    g[pos]+=power[x-l];
    if(g[pos]>=power[siz2]){
        g[pos]-=power[siz2];
        int q=pos+1;
        while(g[q]==power[siz2]-1) g[q]=0,q++,tmp-=siz2;
        tmp-=__builtin_popcountll(g[q]);
        g[q]++;
        tmp+=__builtin_popcountll(g[q]);
    }
    tmp+=__builtin_popcountll(g[pos]);
}
inline void del(int x){
    int pos=pos2[x],l=l2[pos2[x]],r=r2[pos2[x]];
    tmp-=__builtin_popcountll(g[pos]);
    if(g[pos]<power[x-l]){
        g[pos]+=power[siz2]-power[x-l];
        int q=pos+1;
        while(g[q]==0) g[q]=power[siz2]-1,q++,tmp+=siz2;
        tmp-=__builtin_popcountll(g[q]);
        g[q]--;
        tmp+=__builtin_popcountll(g[q]);
    }else g[pos]-=power[x-l];
    tmp+=__builtin_popcountll(g[pos]);
}
unordered_map<int,int> un;
inline void write(int x){
    if(x<=9) return putchar(x+'0'),void();
    write(x/10); putchar(x%10+'0');
}
signed main(){
    n=read(),m=read();
    power[0]=1;
    for(int i=1;i<=60;i++) power[i]=power[i-1]<<1ll;
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
    len2=n/siz2+(n%siz2==0?0:1);
    for(int i=1;i<=len2;i++){//对ull分块
        l2[i]=(i-1)*siz2+1,r2[i]=min(i*siz2,n);
        for(int j=l2[i];j<=r2[i];j++) pos2[j]=i; 
    }
    for(int i=1;i<=n;++i){//离散化，存下每一个可能出现的数位
        int v=a[i];
        while(un[v]){
            un[v]=0;
            ++v;
        }
        un[v]=1;
    }
    int tot=0;
    for(auto p:un) b[++tot]=p.first;
    sort(b+1,b+1+tot);
    for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
    siz=sqrt(n);
    len=n/siz+(n%siz==0?0:1);
    for(int i=1;i<=len;i++){
        for(int j=(i-1)*siz+1;j<=min(i*siz,n);j++) pos[j]=i;
    }
    for(int i=1;i<=m;i++) tt[i].l=read(),tt[i].r=read(),tt[i].id=i;
//  if(n<=2000||m<=2000) clac();
    sort(tt+1,tt+1+m,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){//莫队
        while(tt[i].l<l) add(a[--l]);
        while(tt[i].r>r) add(a[++r]);
        while(tt[i].l>l) del(a[l++]);
        while(tt[i].r<r) del(a[r--]);
        ans[tt[i].id]=tmp;
    }
    for(int i=1;i<=m;i++) write(ans[i]),putchar('\n');
}

做麻了直接刷屏了。。。。