题解：P9986 [Ynoi2079] r2pspc

· · 题解

题意

给定序列 a，q 组询问给定 L,R，求 {\rm popcount}(\sum_{i=L}^{R}2^{a_i})。

其中 n \le 1 \times 10^5,q \le 1 \times 10^6。

思路

First

由 Ynoi 和没有强制在线，猜出是莫队不过分吧……

容易想到莫队，修改的时候暴力的查找大于它的位中是 0 的最小的。

按理说这做法拿不了几分的，但是 96 分。

本部分的代码如下：

const int N=1e6+5;
int n,m,t,a[N];
namespace Lisanhua
{
    unordered_map<int,int> Map;
    int A[N],cnt;
    int Get(int x)
    {
        return lower_bound(A+1,A+1+cnt,x)-A;
    }
    int solve()
    {
        int i,x;
        for(i=1;i<=n;i++)
        {
            x=a[i];
            while(Map[x])
            {
                Map[x]=0;
                x++;
            }
            Map[x]=1;
        }
        for(auto t:Map) A[++cnt]=t.fi;
        sort(A+1,A+1+cnt);
        cnt=unique(A+1,A+1+cnt)-A-1;
        for(i=1;i<=n;i++) a[i]=Get(a[i]);
        return cnt;
    }
}

struct Query{int L,R,id;}q[N*10];
bool comp(const Query &a,const Query &b)
{
    if(a.L/t!=b.L/t) return a.L<b.L;
    return (a.L/t)&1? a.R<b.R:a.R>b.R;
}
int ans[N],cnt[N],Answer;
void ADD(int x)
{
    while(cnt[x])
    {
        Answer--;
        cnt[x]--;
        x++;
    }
    Answer++;
    cnt[x]++;
}
void DEL(int x)
{
    while(!cnt[x])
    {
        Answer++;
        cnt[x]++;
        x++;
    }
    Answer--;
    cnt[x]--;
}
void Never_Give_up()
{
    int i,L,R;
    read(n,m); t=sqrt(n);
    for(i=1;i<=n;i++) a[i]=read();
    Lisanhua::solve();
    for(i=1;i<=m;i++) read(q[i].L,q[i].R),q[i].id=i;
    sort(q+1,q+1+m,comp);
    for(i=1,L=1,R=0;i<=m;i++)
    {
        while(L>q[i].L) ADD(a[--L]);
        while(R<q[i].R) ADD(a[++R]);
        while(L<q[i].L) DEL(a[L++]);
        while(R>q[i].R) DEL(a[R--]);
        ans[q[i].id]=Answer;
    }
    for(i=1;i<=m;i++) write(ans[i],'\n');
}

Second

考虑怎么在这个基础上优化。

每次暴力的找 0 实在是太慢了，怎么卡都过不去。考虑在这上面优化。

惊奇的发现：每个位置只有 0 和 1 两种取值。

感觉可以用 bitset 优化（其实这个优化更像是分块）！

Code

由于本题用 bitset 优化没有压位好写，代码用压位。

#define Count_Number(x) __builtin_popcountll(x)
const int N=1e5+5;
const int M=1e9/32+5;
int n,m,t,a[N],ans[10*N];
struct Query{int L,R,id;}q[10*N];
bool comp(const Query &a,const Query &b)
{
    if(a.L/t!=b.L/t) return a.L<b.L;
    return (a.L/t)&1? a.R<b.R:a.R>b.R;
}
long long cnt[M];
int Answer;
void ADD(int x)
{
    int A=x>>5,B=x&31;
    Answer-=Count_Number(cnt[A]);
    cnt[A]+=1ll<<B;
    while(cnt[A]>>32)
    {
        Answer-=Count_Number(cnt[A+1]);
        cnt[A+1]+=cnt[A]>>32;
        cnt[A]&=(1ll<<32)-1;
        Answer+=Count_Number(cnt[A++]);
    }
    Answer+=Count_Number(cnt[A]);
}
void DEL(int x)
{
    int A=x>>5,B=x&31;
    Answer-=Count_Number(cnt[A]);
    cnt[A]-=1ll<<B;
    while(cnt[A]<0)
    {
        Answer-=Count_Number(cnt[A+1]);
        cnt[A+1]--;
        cnt[A]+=(1ll<<32);
        Answer+=Count_Number(cnt[A++]); 
    }
    Answer+=Count_Number(cnt[A]);
}

void I_Love_her_Forever()
{
    int i,L,R;
    read(n,m); t=sqrt(n);
    for(i=1;i<=n;i++) a[i]=read();
    for(i=1;i<=m;i++) read(q[i].L,q[i].R),q[i].id=i;
    sort(q+1,q+1+m,comp);
    for(i=1,L=1,R=0;i<=m;i++)
    {
        while(L>q[i].L) ADD(a[--L]);
        while(R<q[i].R) ADD(a[++R]);
        while(L<q[i].L) DEL(a[L++]);
        while(R>q[i].R) DEL(a[R--]);
        ans[q[i].id]=Answer;
    }
    for(i=1;i<=m;i++) write(ans[i],'\n');
}