[BZOJ4408][Fjoi 2016]神秘数
试题描述
一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1
8无法表示为集合S的子集的和，故集合S的神秘数为8。
现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间[l,r](l<=r)，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1
8无法表示为集合S的子集的和，故集合S的神秘数为8。
现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间[l,r](l<=r)，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。
输入
第一行一个整数n，表示数字个数。
第二行n个整数，从1编号。
第三行一个整数m，表示询问个数。
以下m行，每行一对整数l,r，表示一个询问。
第二行n个整数，从1编号。
第三行一个整数m，表示询问个数。
以下m行，每行一对整数l,r，表示一个询问。
输出
对于每个询问，输出一行对应的答案。
输入示例
输出示例
数据规模及约定
对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9
题解
一开始把神秘数 ans 设为 1，然后大小在 [0, ans] 范围中所有数显然都是可以用的，并且它们所能组成的最大数就是所有数之和 sum，于是 ans = sum + 1，重复以上动作。因为每次 ans 至少倍增，所以操作次数不超过 9·log10。
操作可以用线段树套 treap 实现，像这样：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
} #define maxn 100010
#define maxnode 4093490
#define LL long long
struct Node {
int v, r;
LL sum;
Node() {}
Node(int _, int __): v(_), r(__) {}
} ns[maxnode];
int ToT, fa[maxnode], ch[2][maxnode];
inline void maintain(int o) {
ns[o].sum = ns[o].v;
for(int i = 0; i < 2; i++) if(ch[i][o])
ns[o].sum += ns[ch[i][o]].sum;
return ;
}
inline void rotate(int u) {
int y = fa[u], z = fa[y], l = 0, r = 1;
if(z) ch[ch[1][z]==y][z] = u;
if(ch[1][y] == u) swap(l, r);
fa[u] = z; fa[y] = u; fa[ch[r][u]] = y;
ch[l][y] = ch[r][u]; ch[r][u] = y;
maintain(y); maintain(u);
return ;
}
inline void insert(int& o, int v) {
if(!o) {
ns[o = ++ToT] = Node(v, rand());
return maintain(o);
}
bool d = v > ns[o].v;
insert(ch[d][o], v); fa[ch[d][o]] = o;
if(ns[ch[d][o]].r > ns[o].r) {
int t = ch[d][o];
rotate(t); o = t;
}
return maintain(o);
}
inline LL que(int& o, LL v) {
if(!o) return 0;
LL ls = ch[0][o] ? ns[ch[0][o]].sum : 0;
if(v >= ns[o].v) return ls + ns[o].v + que(ch[1][o], v);
return que(ch[0][o], v);
} int rt[maxn<<2], ql, qr;
LL V;
inline void update(int L, int R, int o) {
insert(rt[o], V);
if(L == R) return ;
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
if(ql <= M) update(L, M, lc);
else update(M+1, R, rc);
return ;
}
inline LL query(int L, int R, int o) {
if(ql <= L && R <= qr) return que(rt[o], V);
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
LL ans = 0;
if(ql <= M) ans += query(L, M, lc);
if(qr > M) ans += query(M+1, R, rc);
return ans;
} int main() {
int n = read();
for(int i = 1; i <= n; i++) ql = i, V = read(), update(1, n, 1); int q = read();
while(q--) {
ql = read(); qr = read();
LL ans = 0; V = ans + 1;
while(1) {
LL tmp = query(1, n, 1);
if(tmp == ans) break;
ans = tmp; V = ans + 1;
}
printf("%lld\n", ans + 1);
} return 0;
}
然后 T 飞。T_T
当然正解是主席树，代码还倍儿短。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *tail;
inline char Getchar() {
if(Head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
} #define maxn 100010
#define maxnode 4000010
int n, m, A[maxn], sum; int ToT, root[maxn], lc[maxnode], rc[maxnode], sumv[maxnode];
void update(int& y, int x, int L, int R, int p) {
sumv[y = ++ToT] = sumv[x] + p;
if(L == R) return ;
int M = L + R >> 1; lc[y] = lc[x]; rc[y] = rc[x];
if(p <= M) update(lc[y], lc[x], L, M, p);
else update(rc[y], rc[x], M+1, R, p);
return ;
}
int query(int y, int x, int L, int R, int p) {
if(L == R) return sumv[y] - sumv[x];
int M = L + R >> 1;
if(p <= M) return query(lc[y], lc[x], L, M, p);
return sumv[lc[y]] - sumv[lc[x]] + query(rc[y], rc[x], M+1, R, p);
} int main() {
n = read();
for(int i = 1; i <= n; i++) A[i] = read(), sum += A[i];
for(int i = 1; i <= n; i++) update(root[i], root[i-1], 1, sum, A[i]);
m = read();
while(m--) {
int ql = read(), qr = read(), ans = 1;
int v = query(root[qr], root[ql-1], 1, sum, ans);
while(v >= ans) ans = v + 1, v = query(root[qr], root[ql-1], 1, sum, ans);
printf("%d\n", ans);
} return 0;
}