題目：

我是超鏈接

題解：

如果[1,x]可以取到，我們加入一個(gè)數(shù)y，如果y<=x+1，那么我們有新的取數(shù)集合[1,x+y]；如果y>x+1，那么x+1還是取不到啊，這樣我們就有了一個(gè)暴力的思路

進(jìn)一步考慮，對(duì)于一個(gè)還未發(fā)展的數(shù)列，我們的取值范圍是[1,x]，x=0,ans=1，我們可以把權(quán)值<=ans的數(shù)字加起來，和設(shè)為y
如果這時(shí)ans<=y，就是說除了湊成[1,x]的數(shù)外，我們還能找出一個(gè)數(shù)<=ans，這樣取數(shù)集合是[1,y]；
如果這時(shí)ans>y，就是說除了湊成[1,x]的數(shù)外，我們找不出任何一個(gè)數(shù)字了，這樣取數(shù)集合是[1,x]，ans就取不到咯
我們可以依據(jù)這種方法求ans，建一棵權(quán)值線段樹，要維護(hù)區(qū)間和的話，用主席樹就好啦

代碼：

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int N=100005; int sz,root[N],b[N],a[N],p[N]; struct hh{int l,r,w,sum;}t[N*20]; void insert(int &now,int l,int r,int x,int v) {t[++sz]=t[now]; now=sz;t[now].w++; t[now].sum+=v;if (l==r) return;int mid=(l+r)>>1;if (x<=mid) insert(t[now].l,l,mid,x,v);else insert(t[now].r,mid+1,r,x,v); } int qurry(int x,int y,int l,int r,int lrange,int rrange) {if (rrange<lrange) return 0;if (lrange<=l && rrange>=r) return t[y].sum-t[x].sum;int mid=(l+r)>>1,ans=0;if (lrange<=mid) ans+=qurry(t[x].l,t[y].l,l,mid,lrange,rrange);if (rrange>mid) ans+=qurry(t[x].r,t[y].r,mid+1,r,lrange,rrange); return ans; } int main() {int s=0,n,maxx=0,m;scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]),maxx+=a[i],b[++s]=a[i];sort(b+1,b+s+1);s=unique(b+1,b+s+1)-b-1;for (int i=1;i<=n;i++) p[i]=lower_bound(b+1,b+s+1,a[i])-b;for (int i=1;i<=n;i++){root[i]=root[i-1];insert(root[i],1,s,p[i],b[p[i]]);}scanf("%d",&m);while (m--){int x,y,ans=1;scanf("%d%d",&x,&y);while (1){int t=qurry(root[x-1],root[y],1,s,1,upper_bound(b+1,b+s+1,ans)-b-1);if (t>=ans) ans=t+1;else break;}printf("%d\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的[BZOJ4408][FJOI2016]神秘数（主席树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。