题解：P13819 「LDOI R3」玩玩数字

Acit · 2025-08-27 09:29:16 · 题解

思路

官方题解中已经给出了获胜条件，即 \sum_{j \in S} \frac{1}{2^{j}} \ge 1 。

这里给一个较为简单的实现方式。

首先明确一点：若某个 a_i \ge n ，则 a_i 不会对答案产生影响。

也就是说我们只需要维护一个 n 位的二进制数，并支持加减操作。

一个朴素的想法就是对序列分块，并做一个前缀和，而我们可以维护一个 2^w 进制数，这样进位会少很多，跑的较快。

Code

代码中取 w=50。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define forr(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
const int N=4e4+10;
int n,m,LEN;
int a[N];
#define bl(x) (((x)-1)/LEN+1)
int rr[N],ll[N];
int sum[305][1005];
int arr[1005];
const int VAL=(1ll<<50);
void add(int *b,int pl,int val){
    b[pl]+=val;
    if(b[pl]>=VAL){
        b[pl]-=VAL;
        do{
            pl--;
            b[pl]++;
            if(b[pl]<VAL)break;
            b[pl]-=VAL;
        }while(pl>=0);
    }
}
void get(int l,int r){
    roff(i,800,0)arr[i]=0;
    if(l>r)return ;
    roff(i,800,0){
        arr[i]+=sum[r][i]-sum[l-1][i];
        if(arr[i]<0)arr[i]+=VAL,arr[i-1]--;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n;
    LEN=200;
    forr(i,1,n)cin>>a[i];
    forr(i,1,n){
        rr[bl(i)]=i;
        ll[bl(i)]=(bl(i)-1)*LEN+1;
    }
    forr(i,1,bl(n)){
        forr(j,0,800)sum[i][j]=sum[i-1][j];
        forr(j,ll[i],rr[i])if(a[j]<=n)add(sum[i],(a[j]-1)/50+1,(1ll<<(50-(a[j]%50==0?50:a[j]%50))));
    }
    cin>>m;
    forr(i,1,m){
        int l,r;
        cin>>l>>r;
        if(bl(l)==bl(r)){
            forr(i,0,800)arr[i]=0;
            forr(j,l,r)if(a[j]<=n)add(arr,(a[j]-1)/50+1,(1ll<<(50-(a[j]%50==0?50:a[j]%50))));
        }else{
            get(bl(l)+1,bl(r)-1);
            forr(j,l,rr[bl(l)]){
                if(a[j]<=n)add(arr,(a[j]-1)/50+1,(1ll<<(50-(a[j]%50==0?50:a[j]%50))));
            }
            forr(j,ll[bl(r)],r){
                if(a[j]<=n)add(arr,(a[j]-1)/50+1,(1ll<<(50-(a[j]%50==0?50:a[j]%50))));
            }
        }
        if(arr[0]>=1){
            cout<<"Yes\n";
        }
        else cout<<"No\n";
    }
    return 0;
}
/*
time:
problem:
sample:

*/