[BZOJ4408][Fjoi 2016]神秘数（可持久化线段树）

2019-11-06 07:37:02

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

首先考虑O(mnlogn) $O(mnlogn)$ 的做法将询问的一段区间由小到大排序，假设现在已经用前k个数组合出了[1..x]中的所有整数，那么现在考虑加入第k+1个数若k<=x+1，那么我们一定可以组合出[1..x+k]的所有整数，不会出现断层若k>x+1，那么x+1这个整数是无论如何都无法组合的，就可以确定答案了

那么如果不排序有没有办法做呢？同样假设当前已经组合好了[1..x]，设ans=x+1；显然初始时x=0,ans=1 我们在区间[l,r]内统计一下权值<=ans的点的权值和，设为y。如果ans<=y，说明除了组合出[1..x]中的数，一定存在一个数满足<=x+1，这个时候[1..y]都可以组合出来，将ans移动到y+1；如果ans>y，说明除了组合出[1..x]的数，其余所有的数均>x+1，这样当前的ans就是答案了统计一个区间内<=k的数的和可以用可持久化线段树来是实现这样看起来很暴力，但其实ans每一次扩大至少扩大一倍，所以总时间复杂度为O(mlognlog∑ai) $O(mlognlog/sum a_i)$

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 100005int n,m,l,r,LSH,sz,ans;int a[N],lsh[N],root[N],sum[N*20],ls[N*20],rs[N*20];int find(int x){ int l=1,r=LSH,mid,ans; while (l<=r) { mid=(l+r)>>1; if (lsh[mid]<=x) ans=mid,l=mid+1; else r=mid-1; } return ans;}void insert(int &now,int l,int r,int x,int val){ int mid=(l+r)>>1; sum[++sz]=sum[now]+val;ls[sz]=ls[now];rs[sz]=rs[now];now=sz; if (l==r) return; if (x<=mid) insert(ls[now],l,mid,x,val); else insert(rs[now],mid+1,r,x,val);}int query(int L,int R,int l,int r,int lr,int rr){ int mid=(l+r)>>1; int ans=0; if (lr<=l&&r<=rr) return sum[R]-sum[L]; if (lr<=mid) ans+=query(ls[L],ls[R],l,mid,lr,rr); if (mid+1<=rr) ans+=query(rs[L],rs[R],mid+1,r,lr,rr); return ans;}int main(){ scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]),lsh[++LSH]=a[i]; sort(lsh+1,lsh+LSH+1);LSH=unique(lsh+1,lsh+LSH+1)-lsh-1; for (int i=1;i<=n;++i) { int t=find(a[i]); root[i]=root[i-1]; insert(root[i],1,LSH,t,a[i]); } scanf("%d",&m); for (int i=1;i<=m;++i) { scanf("%d%d",&l,&r); ans=1; while (1) { int t=find(ans); int sum=query(root[l-1],root[r],1,LSH,1,t); if (sum>=ans) ans=sum+1; else break; } PRintf("%d/n",ans); }}