[DS记录]P4587 [FJOI2016]神秘数

**题意** ： 对于可重整数集 $S$ ，定义 ${\rm nsum}(S)$ 为最小的不能被 $S$ 的一个子集的和表示出来的正整数。 给定序列 $A_{1\sim n}$ ，每次询问 ${\rm nsum}\big(\{A_{l\sim r}\}\big)$。 $n,m\leq 10^5,\sum A_{1\sim n}\leq 10^9$ ，时限$\texttt{1s}$。 ------------ 考虑如何回答单组询问。 将 $S$ 从小到大排序为 $S_{1\sim m}$。 不难发现，找到第一个 $S_i>\sum S_{1\sim i-1}+1$ ，则 ${\rm nsum}(S)=\sum S_{1\sim i-1}+1$。 回到原问题。 用主席树差分得到区间内的值域线段树。 设当前的候选答案为 $ans$ （初始时为 $1$），求 $\leq ans$ 的数的和 $S$ ，若 $ans\geq S+1$ ，则答案为 $S+1$。 若 $S+1>ans$ ，则令 $ans=S+1$ ，继续操作。 记连续某两次的 $ans$ 为 $x,y$ ，若不停止，则 $y$ 的查询中 $(x,y]$ 必然要有数，下一步至少变为 $x+y+1$。故操作次数是 $O(\log)$ 的。 复杂度为 $O\big(n\log n\log(\sum A)\big)$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 100500 using namespace std; const int lim=1000000000; struct Node{int l,r,s;}a[MaxN<<5]; int tn,rt[MaxN],to,wfr,ret; void add(int l,int r,int &u,int v) { a[u=++tn]=a[v];a[u].s+=to; if (l==r)return ; int mid=(l+r)>>1; if (to<=mid)add(l,mid,a[u].l,a[v].l); else add(mid+1,r,a[u].r,a[v].r); } void qry(int l,int r,int u) { if (r<=wfr){ret+=a[u].s;return ;} int mid=(l+r)>>1; qry(l,mid,a[u].l); if (mid<wfr)qry(mid+1,r,a[u].r); } ll n;int m; int main() { scanf("%d",&n); for (int i=1,x;i<=n;i++){ scanf("%d",&x); to=x;add(1,lim,rt[i],rt[i-1]); } scanf("%d",&m); for (int i=1,l,r;i<=m;i++){ scanf("%d%d",&l,&r); int ans=1; while(1){ ret=0;wfr=ans; qry(1,lim,rt[l-1]);ret=-ret; qry(1,lim,rt[r]); if (ans>=ret+1)break; else ans=ret+1; }printf("%d\n",ret+1); }return 0; } ``` ## 加强 ：[U164888 五重原题](https://www.luogu.com.cn/problem/U164888?contestId=45705) 在上一题的基础上增加单点修改操作。 $n\leq 5\times 10^5,q\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 可以用树套树来维护“区间内 $\leq x$ 的数的和”，复杂度高达 $\log^3$ ，无法通过。 将值域按照 $[2^i,2^{i+1})$ 分块。每次操作，（由于开始时是 $2^i$）要么跳过一整块，要么停止在中间。 于是对于每一块，维护 $\min,sum$ ，判一下 $\min$ 会不会停止即可。 时间复杂度为 $O(n\log n\log a)$ ，空间复杂度为 $O(n\log a)$。 底层按 $\log a$ 分块可以将空间复杂度改进为 $O(n)$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 530000 using namespace std; const int BS=32,INF=2000000000; struct Node{ ll s[31];int x[31]; void clear() {for (int i=0;i<30;i++){s[i]=0;x[i]=INF;}} }a[(MaxN/BS)<<1],R; Node operator + (const Node &A,const Node &B){ Node C; for (int i=0;i<30;i++)C.s[i]=A.s[i]+B.s[i]; for (int i=0;i<30;i++)C.x[i]=min(A.x[i],B.x[i]); return C; } inline int log2(int x){ int cnt=0; while((x>>5)>=1){x>>=5;cnt+=5;} while(x>1){x>>=1;cnt++;} return cnt; } int x[MaxN]; void _build(int l,int r,Node &A) { A.clear(); for (int i=l;i<=r;i++){ int p=log2(x[i]); A.x[p]=min(A.x[p],x[i]); A.s[p]+=x[i]; } } inline void up(int u){a[u]=a[u<<1]+a[u<<1|1];} void build(int l,int r,int u) { if (r-l+1<=BS){_build(l,r,a[u]);return ;} int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); up(u); } int to; void upd(int l,int r,int u) { if (r-l+1<=BS){_build(l,r,a[u]);return ;} int mid=(l+r)>>1; if (to<=mid)upd(l,mid,u<<1); else upd(mid+1,r,u<<1|1); up(u); } int wfl,wfr; void qry(int l,int r,int u) { if (r-l+1<=BS){ Node now; _build(max(wfl,l),min(wfr,r),now); R=R+now;return ; } if (wfl<=l&&r<=wfr){R=R+a[u];return ;} int mid=(l+r)>>1; if (wfl<=mid)qry(l,mid,u<<1); if (mid<wfr)qry(mid+1,r,u<<1|1); } int n,m; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++)scanf("%d",&x[i]); build(1,n,1); for (int i=1,op,l,r;i<=m;i++){ scanf("%d%d%d",&op,&l,&r); if (op==1){x[to=l]=r;upd(1,n,1);} else { R.clear();wfl=l;wfr=r;qry(1,n,1); ll sum=0; for (int i=0;i<30;i++) if (sum+1>=R.x[i]) sum+=R.s[i]; printf("%lld\n",sum+1); } }return 0; } ```