BZOJ4299: Codechef FRBSUM(主席树)
2018-09-18 06:24:38来源:博客园 阅读 ()
题意
题目链接
数集S的ForbiddenSum定义为无法用S的某个子集(可以为空)的和表示的最小的非负整数。例如,S={1,1,3,7},则它的子集和中包含0(S’=∅),1(S’={1}),2(S’={1,1}),3(S’={3}),4(S’={1,3}),5(S' = {1, 1, 3}),但是它无法得到6。因此S的ForbiddenSum为6。给定一个序列A,你的任务是回答该数列的一些子区间所形成的数集的ForbiddenSum是多少。
Sol
若序列已经被从小到大排序
考虑当前位置为$i$,且$[1, s_i]$内的数都可以被拼成
那么若$a[i + 1] > s_i + 1$,那么$a[i + 1]$不能被拼成
于是我们可以这样去做
首先在集合内找比$s = 1$小的数的和(也就相当于上面的前缀和),若比$1$少,则答案为$1$
若询问得到的结果是$1$,则$s = 1 + 1 = 2$,此时我们去找比$2$小的和
若$< 2$,则答案为$2$,不断做下去,直到不符合条件为止。
不符合条件,实际上也就是$a[i + 1] > s_i + 1$
每次在一段区间内询问小于等于某一个数的和,可以用主席树维护,
时间复杂度:若一直是符合条件的,我们每次询问会至少让si翻一倍,因此单次询问的复杂度为log sn,
加上主席树的复杂度,总复杂度为$O(Q logn log sn)$
#include<iostream> #include<cstdio> using namespace std; const int MAXN = 3 * 1e6 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, a[MAXN], lim; int ls[MAXN], rs[MAXN], sum[MAXN], tot, root[MAXN]; void insert(int &k, int p, int l, int r, int pos) { k = ++ tot; ls[k] = ls[p]; rs[k] = rs[p]; sum[k] = sum[p] + pos; if(l == r) return ; int mid = l + r >> 1; if(pos <= mid) insert(ls[k], ls[p], l, mid, pos); else insert(rs[k], rs[p], mid + 1, r, pos); } int Query(int k, int p, int l, int r, int val) { if(l > val) return 0; if(r <= val) return sum[k] - sum[p]; int mid = l + r >> 1; int suml = sum[ls[k]] - sum[ls[p]]; if(val > mid) return suml + Query(rs[k], rs[p], mid + 1, r, val); else return Query(ls[k], ls[p], l, mid, val); } int solve(int l, int r) { int nxt = 0; for(int i = 1; ; i = nxt + 1) { nxt = Query(root[r], root[l - 1], 1, lim, i);//询问区间内<=i的数的和 if(nxt < i) return i; } } int main() { N = read(); for(int i = 1; i <= N; i++) a[i] = read(), lim = max(a[i], lim); for(int i = 1; i <= N; i++) insert(root[i], root[i - 1], 1, lim, a[i]); int Q = read(); while(Q--) { int l = read(), r = read(); printf("%d\n", solve(l, r)); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- codechef Table Game(博弈) 2018-09-18
- codechef September Challenge 2018 Division 2 A-F 2018-09-18
- codechef Count Relations(组合数 二项式定理) 2018-09-10
- Codechef Chef and Easy Problem(智商) 2018-07-11
- codechef April Challenge 2018 Div2(1-4) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash