-
树形数据结构专场
也就是我的大型 GG 专场
T1.P4587 [FJOI2016]神秘数
-
主席树/可持久化线段树；
-
考试的时候怕调不出来，不是很敢写，然后还有性质分析得不是很清楚……
于是 GG 了，还炫没了许多时间。结果 \(AC\) 代码意外的短。 -
前置性质
设当前数字集合 \(S\) 已经可以表示 \([1,pos]\) 里的所有数，\(pos+1\) 就是第一个不能被表示的数。当前有一些 \(a_i\) 需要插入其中。- 当 \(a_i> pos+1\) 时，显然，即使把 \(a_i\) 插入 \(S\)，\(pos+1\) 这个数仍然不能被凑出来，所以 \(a_i\) 不会对 \(pos\) 产生贡献；
- 当 \(a_i\le pos+1\) 时，插入 \(a_i\) 后就能表示 \([1,pos+a_i]\) 里的所有数；
-
因此，问题转化为，从小到大向 \(S\) 里插入序列 \([l,r]\) 区间里的数，然后下一次可以插入的数范围在当前集合对应 \([1,pos+1]\) 中，也就是说，需要对区间求和。
由于要求区间，考虑主席树。 -
在值域建树，用主席树维护区间和。
对于每次询问，从值域 \([1,1]\) 开始求解。
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=1e5+10;
struct memr{
int ls,rs;
int sum;
}tr[N<<5];
int n,m,cnt=0;
int rt[N];
#define mid ((l+r)>>1)
void update(int &now,int p,int l,int r,int x){
now=++cnt;
tr[now].ls=tr[p].ls,tr[now].rs=tr[p].rs;
tr[now].sum=tr[p].sum+x;
if(l==r) return ;
if(x<=mid) update(tr[now].ls,tr[p].ls,l,mid,x);
else update(tr[now].rs,tr[p].rs,mid+1,r,x);
return ;
}
int ask(int a,int b,int l,int r,int ql,int qr){
if(tr[a].sum==tr[b].sum) return 0;
if(ql<=l && r<=qr) return tr[b].sum-tr[a].sum;
int ans=0;
if(ql<=mid) ans+=ask(tr[a].ls,tr[b].ls,l,mid,ql,qr);
if(mid<qr) ans+=ask(tr[a].rs,tr[b].rs,mid+1,r,ql,qr);
return ans;
}
int main(){
n=read();
int a;
for(int i=1;i<=n;++i){
a=read();
update(rt[i],rt[i-1],1,1e9,a);
}
m=read();
int l,r;
while(m--){
l=read(),r=read();
int mx=0,pos=0;
for(;;){
int ans=ask(rt[l-1],rt[r],1,1e9,mx+1,pos+1);
if(!ans) break;
mx=pos+1;
pos+=ans;
}
printf("%d\n",pos+1);
}
return 0;
}
T2.P2497 [SDOI2012]基站建设
凭什么 n≤1e5 O(n²) 的暴力只给 10 pts？凭什么？？