牛牛的凑数游戏

牛牛的凑数游戏

原博客食用效果更佳

其实蛮简单的一道题

很容易发现对于一个区间，我们将其排序后，如果前i个数之和+1小于第i+1个数，那么前i个数之和+1是一定无法构造出来的，于是，我们就要找到第一个前缀和+1不存在的数。

很明显，如果用暴力的话，是明显会T掉的，只能拿30pts。

考虑如果当前前缀和为sum时，所有的小于sum的数都可以用来更新前缀和，因为比他们小的数必定可以构造出来。而如果这样加小于sum的数的话，由于每次翻的再下一次不会再产生贡献，而前缀和不断扩大，总的次数不会超过log n。

每次我们相当于要查询l到r之间的小于sum的数的和，如果只用查询小于sum的数的话，线段树，trie树等都可以用来操作，由于我们还要维护区间，可以用可持久化trie来进行维护，将一个数二进制分解后加入。

总的时间复杂度。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define MAXN 100005
typedef long long LL;
const int INF=0x7f7f7f7f;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
    _T f=1;x=0;char s=getchar();
    while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
    x*=f;
}
int n,m,tot,root[MAXN];
LL a[MAXN],bin[40];
struct ming{
    LL sum;int lson,rson;
}tr[35*MAXN];
void fj(LL x){if(x>1000000000LL)x=1000000001LL;for(int i=30;i>=0;i--)bin[i]=(x>>i)&1LL;}
void insert(int &now,int las,int id,LL w){
    tr[now=++tot]=tr[las];if(id<0){tr[now].sum+=w;return ;}
    if(!bin[id])insert(tr[now].lson,tr[las].lson,id-1,w);
    else insert(tr[now].rson,tr[las].rson,id-1,w);
    tr[now].sum=tr[tr[now].lson].sum+tr[tr[now].rson].sum;
    //printf("%lld %d %d %lld\n",w,id,now,tr[now].sum);
}
LL query(int rt,int id){
    if(id<0||!rt)return tr[rt].sum;LL res=0;
    if(!bin[id])res=query(tr[rt].lson,id-1);
    else res=tr[tr[rt].lson].sum+query(tr[rt].rson,id-1);
    return res;
}
signed main(){
    read(n);read(m);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<=n;i++)fj(a[i]),insert(root[i],root[i-1],30,a[i]);
    for(int i=1;i<=m;i++){
        int l,r;read(l);read(r);
        LL sum=1,las=0;
        while(1){
            fj(sum);
            LL tmp=query(root[r],30)-query(root[l-1],30);
            if(tmp==las){printf("%lld\n",sum);break;}
            else las=tmp,sum=tmp+1LL;//printf("now:%lld\n",tmp);
        }
    }
    return 0;
}