題目描述

http://www.lydsy.com/JudgeOnline/problem.php?id=4408

題目大意：求最小不能被一段區間中某些數的和表示的數。（還是看題面吧）

---

思路

可持久化線段樹好題。話說為什么我打可持久總會看到可吃雞。。

首先設能表示的一段區間為[1,x]，則神秘數為x+1。當前加入一個數y，分為兩種情況：

①y<=x+1，則能表示的區間變成[1,x+y]，神秘數變成x+y+1。

②y>x+1，則x+1不能被表示，能表示的區間不變，神秘數不變。

于是我們維護區間的和。設神秘數為ans，一開始ans=1。找到一個區間中小于等于ans的數并求和，記為Get。如果Get>=ans， 則區間可以擴展變成[1,Get]，ans=Get+1。

如果Get < ans，代表此時ans不會改變，神秘數就是現在的ans。

該題神奇的地方就在y>x+1的y對神秘數不產生任何影響，喵處就是y<=x+1的y可以一次性更新答案。

而找一個區間中小于等于某數的和可以用可持久化線段樹來維護。即每個點開權值線段樹上的一條鏈，然后維護前綴和就行了。

由于每次詢問時間logN，而每次ans至少翻一番，所以總時間就是O(nlogN+mlogNlogN)。

---

代碼

#include <bits/stdc++.h> #define maxn 100010 #define Lg 32using namespace std;int a[maxn], n, m, cnt, ToT, ans, Get;struct Tnode{Tnode *lson, *rson;int sum; }tree[maxn*Lg], *Root[maxn];Tnode *NewTnode(){tree[cnt].lson = tree[cnt].rson = tree;tree[cnt].sum = 0;return tree+cnt++; }void Update(Tnode *root, int L, int R, int x){if(L == R){root->sum += x;return;}int mid = (L + R) >> 1;Tnode *p = NewTnode();if(x <= mid){*p = *(root->lson);root->lson = p;Update(p, L, mid, x);}else{*p = *(root->rson);root->rson = p;Update(p, mid+1, R, x);}root->sum = root->lson->sum + root->rson->sum; }int Query(Tnode *root1, Tnode *root2, int L, int R, int x){if(L == R) return root2->sum - root1->sum;int mid = (L + R) >> 1;if(x <= mid) return Query(root1->lson, root2->lson, L, mid, x);else return root2->lson->sum - root1->lson->sum + Query(root1->rson, root2->rson, mid+1, R, x); }int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]), ToT += a[i];Root[0] = NewTnode();for(int i = 1; i <= n; i++){Root[i] = NewTnode();*Root[i] = *Root[i-1];Update(Root[i], 1, ToT, a[i]);}scanf("%d", &m);int l, r;for(int i = 1; i <= m; i++){scanf("%d%d", &l, &r);ans = 1;for(;;){Get = Query(Root[l-1], Root[r], 1, ToT, ans);if(Get < ans) break;ans = Get + 1;}printf("%d\n", ans);}return 0; }

---

總結

以上是生活随笔為你收集整理的BZOJ 4408: [Fjoi 2016]神秘数（可持久化线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。