T3牛牛的凑数游戏

题面

更好的阅读体验

代码参考了Deep_Kevin神的

做的时候还在想，这东西我似乎连暴力都不会，想想如果要枚举区间内所有可能出现的和那不是光枚举就得 了，无力 (

赛后：我是***。

首先，我们必须解决如何在多项式时间内找到这个数的问题，其他的再说。

为了让数据更好处理我们肯定会选择sort一下（升序）。然后就要利用一个类似数学归纳的思想。

• 有序序列长度 时，答案显然，不是1就是2。

• 假设有序序列长度 时，假设这 个数的总和为 ，且对于 ~ 答案为 （即1~都可以表示）。

  当 时，有以下结论：

  • ① 如果对于前 个数，存在一个前缀和大于等于 ，那么1~都是可以表示的（如果不理解就思考一下我为什么说和数归很像）
  • ② 如果对于前 个数，不存在一个前缀和大于等于 ，即 那么答案就是

当然，只有这些还不能得到答案。有了这些结论，答案的处理应该是这样的：

• 对于升序序列，从小往大枚举，直到出现上文结论中的②或者全部扫完
• 如果是前者，那答案就是 ，如果是后者，答案就是整个

但是显然我们不能不停的sort，所以我们需要数据结构。

我这里使用的是用主席树，以数值为下标，在树上维护前缀和（本质上维护的是每一个数值出现的次数），类似于桶的思想，版本维护的是区间内的前缀和。维护区间内信息可以通过两棵树上的信息相互做差实现。

add函数实现将数***去并且做前缀和

inline void add(int las,int x){
    int now = ++tot;
    sum[now] = sum[las] + x;
    per(i,29,0){
        if(x & (1<<i)) ls[now] = ls[las] , rs[now] = ++tot , now = rs[now] , las = rs[las];
        else rs[now] = rs[las] , ls[now] = ++tot , now = ls[now] , las = ls[las];
        sum[now] = sum[las] + x;
    }
}

query实现查询 ~ 之间所有小于等于 数的和

（如果没有 ，则如果加出来的东西小于 那必定做不到 ，所以答案就只能是 ，如果有 ，那出来的必定大于等于 ，而前面的所有数都已经保证可以得到(见上文的推理) ）

Code

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define per(i,a,b) for(int i = (a);i >= (b);--i) 
#define mkp std::make_pair
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
inline bool cmp(int x,int y){return x < y;}
/-fsanitize=undefined*/
const int N = 1e7+9;
const int inf = 1e9+9;
const double eps = 1e-7;
int _,n,m,p,l,r,tot;
ll sum[2*N];
int ls[2*N],root[2*N],rs[2*N];

inline void add(int las,int x){
    int now = ++tot;
    sum[now] = sum[las] + x;
    per(i,29,0){
        if(x & (1<<i)) ls[now] = ls[las] , rs[now] = ++tot , now = rs[now] , las = rs[las];
        else rs[now] = rs[las] , ls[now] = ++tot , now = ls[now] , las = ls[las];
        sum[now] = sum[las] + x;
    }
    return;
}

inline ll query(int u,int v,int x){
    if(x >= sum[v] - sum[u] + 1) return sum[v] - sum[u];
    ll ans = 0;
    per(i,29,0){
        if(x & (1<<i)) ans += sum[ ls[v] ] - sum[ ls[u] ] , v = rs[v] , u = rs[u];
        else v = ls[v] , u = ls[u];
    }
    ans += sum[v] - sum[u];
    return ans;
}

inline int min(ll x,ll y){if(x<y) return x;else return y;}

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL //use "g++ xxx.cpp -DLOCAL"
        freopen("in.in", "r", stdin);
    #endif
    cin >> n >> m;
    rep(i,1,n){
        cin >> p;
        root[i] = tot+1;
        add(root[i-1],p);
    }
    ll tmp,las;
    while(m--){
        cin >> l >> r; --l;
        tmp = 0 , las = -1;
        while(tmp != las) las = tmp , tmp = query(root[l],root[r],min(tmp+1,inf));
        cout << tmp+1 << "\n";
    }
    return 0;
}