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

题目描述

传送门

题解

首先考虑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)

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 100005 int 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); } }

总结

这题作为胡策的c题竟然是最良心的一道 然而当时并没有a掉。。。

感觉上午的状态非常奇怪 简单的难的都想不出来 想出来的暴力不想打 硬gang代码题没gang出来

是该好好想想了。。。