网站维护是什么样,做网站php和asp哪个好,泉州小程序开发科技公司,宜兴市做网站正题
题目链接:https://www.luogu.com.cn/problem/P4587 题目大意 nnn个数#xff0c;每次选择一个区间#xff0c;然后询问这个区间的子集和所不能表示的最小的正整数。 解题思路
假设我们从小到大加入数字#xff0c;我们发现如果这个数不是111显然这个区间内至少有一个…正题
题目链接:https://www.luogu.com.cn/problem/P4587 题目大意
nnn个数每次选择一个区间然后询问这个区间的子集和所不能表示的最小的正整数。 解题思路
假设我们从小到大加入数字我们发现如果这个数不是111显然这个区间内至少有一个111。
我们假设现在能表示的最小的数是mxmxmx加入一个数xxx时如果xmx1x mx1xmx1那么mx1mx1mx1就不能表现出来否则我们就可以表示出1∼mxx1\sim mxx1∼mxx的数即让mxmxxmxmxxmxmxx。
考虑如何优化如果我们之前能表现出1∼mx1\sim mx1∼mx加上某些数之后能表现出1∼mx′1\sim mx1∼mx′了那么我们显然可以寻找任何一个在mx1∼mx′1mx1\sim mx1mx1∼mx′1里的数字来扩充那么我们之间将这段区间的和取来不就好了吗。这个可以用主席树维护。
时间复杂度如何我们发现每次找到的区间和如果还能往下显然是大于mxmxmx的然后会让mx′mxmxmxmx′mx也就是每次至少可以让mx′mxmx′加上自己的一半这个时间复杂度是接近倍增也就是logloglog的。
所以时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610,M5e610,inf1e9;
ll n,m,cnt,rt[N];
ll ls[M],rs[M],sum[M];
ll Change(ll x,ll L,ll R,ll val){ll ycnt;rs[y]rs[x];ls[y]ls[x];ll mid(LR)1;sum[y]sum[x]val;if(LR)return y;if(valmid)ls[y]Change(ls[x],L,mid,val);else if(valmid)rs[y]Change(rs[x],mid1,R,val);return y;
}
ll Ask(ll x,ll y,ll L,ll R,ll l,ll r){if(!(sum[x]-sum[y]))return 0;if(lLrR)return sum[x]-sum[y];ll mid(LR)1;if(rmid)return Ask(ls[x],ls[y],L,mid,l,r);if(lmid)return Ask(rs[x],rs[y],mid1,R,l,r);return Ask(ls[x],ls[y],L,mid,l,mid)Ask(rs[x],rs[y],mid1,R,mid1,r);
}
int main()
{scanf(%lld,n);for(ll i1;in;i){ll x;scanf(%lld,x);rt[i]Change(rt[i-1],1,inf,x);}scanf(%lld,m);for(ll i1;im;i){ll l,r,lim0,at0;scanf(%lld%lld,l,r);while(1){ll wAsk(rt[r],rt[l-1],1,inf,lim1,at1);if(!w)break;limat1;atw;}printf(%lld\n,at1);}return 0;
}
