生活随笔
收集整理的這篇文章主要介紹了
[FJOI 2016]bzoj 4408 神秘数 - 线段树
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目大意：給你一列數，多次詢問用一個區間的數字形成一個可重集合，最小的不能被表示為其一個子集的數字是多少。
題解：考慮給你一個可重集合你怎么算：從小到大排序，假設用前x個數字不能表示的最小都數字是ans，那么如果a[x+1]>ans，則ans就是答案，否則ans+=a[++x]。這個過程顯然可以線段樹每次區區間最小值，加上，然后把這個最小值設為INF，但是復雜度是不對的，例如全是1。但是發現這個過程顯然可以優化：若當前答案是ans，已經加入了a[1…x]，而a[(x+1)…y]<=ans，那么可以一口氣把a[(x+1)…y]加到ans上（此時ans=\sum_{i=1}^y a[i]）。這樣做好像復雜度還是不靠譜？其實是對的，考慮一個數字x，再第i輪（此時答案記做ans[i]）沒有被加入，而第i+1輪被加入了，意味著x>ans[i]，而從第i輪到第i+2輪，ans至少翻了一倍。因此用主席樹維護上述過程，復雜度兩個log。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define gc getchar()
#define N 100010
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std
;
inline int inn()
{int x
,ch
;while((ch
=gc
)<'0'||ch
>'9');x
=ch
^'0';while((ch
=gc
)>='0'&&ch
<='9')x
=(x
<<1)+(x
<<3)+(ch
^'0');return x
;
}
struct segment
{int s
;segment
*ch
[2];
}*T
[N
];int m
,a
[N
];vector
<int> v
;
inline int getid(int x
) { return lower_bound(v
.begin(),v
.end(),x
)-v
.begin()+1; }
int build(segment
* &rt
,int l
,int r
)
{rt
=new segment
,rt
->s
=0;if(l
==r
) return 0;int mid
=(l
+r
)>>1;return build(rt
->ch
[0],l
,mid
),build(rt
->ch
[1],mid
+1,r
),0;
}
int update(segment
* &x
,segment
* &y
,int l
,int r
,int p
,int v
)
{x
=new segment
,x
->s
=y
->s
+v
,x
->ch
[0]=y
->ch
[0],x
->ch
[1]=y
->ch
[1];if(l
==r
) return 0;int mid
=(l
+r
)>>1;if(p
<=mid
) update(x
->ch
[0],y
->ch
[0],l
,mid
,p
,v
);if(mid
<p
) update(x
->ch
[1],y
->ch
[1],mid
+1,r
,p
,v
);return 0;
}
int query(segment
* &rt
,int l
,int r
,int s
,int t
)
{if(s
<=l
&&r
<=t
) return rt
->s
;int mid
=(l
+r
)>>1,ans
=0;if(s
<=mid
) ans
+=query(rt
->ch
[0],l
,mid
,s
,t
);if(mid
<t
) ans
+=query(rt
->ch
[1],mid
+1,r
,s
,t
);return ans
;
}
int query(int l
,int r
,int p
)
{int t
=getid(p
);if(v
[t
-1]>p
) t
--;if(!t
) return 0;return query(T
[r
],1,m
,1,t
)-query(T
[l
-1],1,m
,1,t
);
}
int main()
{int n
=inn();for(int i
=1;i
<=n
;i
++) a
[i
]=inn(),v
.pb(a
[i
]);sort(v
.begin(),v
.end());v
.erase(unique(v
.begin(),v
.end()),v
.end());m
=(int)v
.size();build(T
[0],1,m
);for(int i
=1;i
<=n
;i
++)update(T
[i
],T
[i
-1],1,m
,getid(a
[i
]),a
[i
]);for(int q
=inn();q
;q
--){int l
=inn(),r
=inn(),ans
=0,t
;while(ans
<(t
=query(l
,r
,ans
+1))) ans
=t
;printf("%d\n",ans
+1);}return 0;
}
總結
以上是生活随笔為你收集整理的[FJOI 2016]bzoj 4408 神秘数 - 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
