題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的數(shù)列，需要回答 $m$ 次詢問，每次詢問給出一段區(qū)間 $[l,r]$，輸出至少需要將這段區(qū)間拆成的最少段數(shù)，使得每段區(qū)間中，假設(shè)區(qū)間長度為 $x$，那么出現(xiàn)次數(shù)最多的數(shù)字不能超過 $?\frac{x}{2}?$ 次

題目分析：對于某一段區(qū)間來說，假設(shè)區(qū)間長度為 $x$ ，出現(xiàn)次數(shù)最多的數(shù)字 $t$ 的出現(xiàn)次數(shù)為 $f$，滿足 $f>?\frac{x}{2}?$ ，那么此時不等于 $t$ 的數(shù)字有 $x?f$ 個，貪心去分配的話，第一段可以放置：$x?f$ 個非 $t$ 的數(shù)字和 $x?f+1$ 個數(shù)字 $t$，剩下的每個數(shù)字 $t$ 獨成一段，這樣答案就是 $1+(f?(x?f+1))=2?f?x$

所以現(xiàn)在問題就轉(zhuǎn)換為了快速求詢問區(qū)間中的 $f$ 了，也就是區(qū)間眾數(shù)，因為允許離線，所以理論上是可以直接用莫隊去 $O(n\sqrt{n})$ 實現(xiàn)的，應(yīng)該也可以用值域分塊在線去寫，時間復(fù)雜度是相同的，我直接寫了一發(fā) $O(n\sqrt{n?logn})$ 的，果不其然 T 掉了。。

不過本題其實并不需要求眾數(shù)，只需要求出出現(xiàn)次數(shù)大于 $?\frac{x}{2}?$ 次的數(shù)字，對于沒有達到這個閾值的，我們并不關(guān)心

這樣就可以直接用線段樹去實現(xiàn)了，因為如果滿足大于了區(qū)間長度的一半的話，在 $pushup$ 的過程中一定是可以正確更新到的，結(jié)合二分找區(qū)間中某個數(shù)字的個數(shù)，時間復(fù)雜度為 $O(n?lo{g}^{2}n)$

還有一個比較玄學(xué)的解法，就是在區(qū)間中隨機抓 $k$ 個數(shù)字，嘗試令每個數(shù)字為區(qū)間的 $f$，不滿足的概率為 $O(2^k)$，這里可以讓 $k$ 取到 $40$，因為還是需要結(jié)合二分去查找區(qū)間數(shù)字的個數(shù)，所以時間復(fù)雜度為 $O(n?logn?k)$

代碼：

線段樹

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=3e5+100; int a[N]; vector<int>pos[N]; struct Node {int l,r,val; }tree[N<<2]; int get_num(int l,int r,int val) {return upper_bound(pos[val].begin(),pos[val].end(),r)-lower_bound(pos[val].begin(),pos[val].end(),l); } void pushup(int k) {int l=tree[k].l,r=tree[k].r;if(get_num(l,r,tree[k<<1].val)>get_num(l,r,tree[k<<1|1].val)) {tree[k].val=tree[k<<1].val;} else {tree[k].val=tree[k<<1|1].val;} } void build(int k,int l,int r) {tree[k]={l,r};if(l==r) {tree[k].val=a[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); } int query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return 0;}if(tree[k].l>=l&&tree[k].r<=r) {return get_num(l,r,tree[k].val);}return max(query(k<<1,l,r),query(k<<1|1,l,r)); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);for(int i=1;i<=n;i++) {read(a[i]);pos[a[i]].push_back(i);}build(1,1,n);while(m--) {int l,r;read(l),read(r);printf("%d\n",max(1,query(1,l,r)*2-(r-l+1)));}return 0; }

隨機數(shù)

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=3e5+100; int a[N]; vector<int>pos[N]; mt19937_64 eng(time(NULL)); int get_num(int l,int r,int val) {return upper_bound(pos[val].begin(),pos[val].end(),r)-lower_bound(pos[val].begin(),pos[val].end(),l); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);for(int i=1;i<=n;i++) {read(a[i]);pos[a[i]].push_back(i);}while(m--) {int l,r,ans=0;read(l),read(r);for(int i=1;i<=40;i++) {ans=max(ans,get_num(l,r,a[uniform_int_distribution<int>(l,r)(eng)]));}printf("%d\n",max(1,2*ans-(r-l+1)));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1514D Cut and Stick(线段树/随机数)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。