「USACO24DEC G」Cowdepenence 題解
「USACO24DEC G」Cowdepenence 題解
知識點
根號分治。
分析
\(O(n\sqrt{n}\log_2{n})\)
我們考慮先將每種顏色分開，然后對于每種顏色分別處理。
可以類比數論分塊，我們會發現當距離范圍 \(x\) 處于某個區間 \([l,r]\) 時，友誼小組的最小數量 \(cnt\) 的值是相同的，而且根據數論分塊的結論，本質不同的 \(cnt\) 數量不會超過 \(\sqrt{n}\)。
顯然 \(x,cnt\) 的關系滿足單調性，所以我們可以直接暴力二分 \(x\) 的闕值，進行檢驗，并且對每次重復檢驗的 \(x\) 進行記憶化，然后差分統計答案。
unordered_map<int,int> rec;
void Solve(const Vi &vec) {
for(int L(1),R(1),c(Check(vec,1)); L<=n; c=Check(vec,L=++R)) {
for(int l(L+1),r(n),mid((l+r)>>1); l<=r; mid=(l+r)>>1)
Check(vec,mid)>=c?R=mid,l=mid+1:r=mid-1;
ans[L]+=c,ans[R+1]-=c;
}
rec.clear();
}
假設我們現在處理的顏色有 \(k\) 個，那么我們有兩種檢驗方法：
-
\(O(k)\)：
直接一遍掃過去。
int Check1(const Vi &vec,const int &lim) { int cnt(0),sta(0); for(const int &x:vec)if(!sta||x-sta>lim)++cnt,sta=x; return cnt; } -
\(O(\frac{n}{x}\log_2{k})\)：
我們中間不斷二分下一個點。
int Check2(const Vi &vec,const int &lim) { int cnt(0),sta(vec.front()); while(true) { ++cnt; int it(upper_bound(vec.begin(),vec.end(),sta+lim)-vec.begin()); if(it==(int)vec.size())break; sta=vec[it]; } return cnt; }
我們每次取其中復雜度小的一個。
int Check(const Vi &vec,const int &lim) {
if(rec.count(lim))return rec[lim];
auto cal=[&]() -> ll { return (ll)rec.size()*lim/n; };
return rec[lim]=(cal()<20&&(1<<cal())<(int)rec.size()?Check1(vec,lim):Check2(vec,lim));
}
時間復雜度 \(O(n\sqrt{n}\log_2{n})\)。
int n;
int a[N],b[N],ans[N];
Vi vec[N];
int Check1(const Vi &vec,const int &lim) {
int cnt(0),sta(0);
for(const int &x:vec)if(!sta||x-sta>lim)++cnt,sta=x;
return cnt;
}
int Check2(const Vi &vec,const int &lim) {
int cnt(0),sta(vec.front());
while(true) {
++cnt;
int it(upper_bound(vec.begin(),vec.end(),sta+lim)-vec.begin());
if(it==(int)vec.size())break;
sta=vec[it];
}
return cnt;
}
unordered_map<int,int> rec;
int Check(const Vi &vec,const int &lim) {
if(rec.count(lim))return rec[lim];
auto cal=[&]() -> ll { return (ll)vec.size()*lim/n; };
return rec[lim]=(cal()<20&&(1<<cal())<(int)vec.size()?Check1(vec,lim):Check2(vec,lim));
}
void Solve_Min(const Vi &vec) {
for(int L(1),R(1),c(Check(vec,1)); L<=n; c=Check(vec,L=++R)) {
for(int l(L+1),r(n),mid((l+r)>>1); l<=r; mid=(l+r)>>1)
Check(vec,mid)>=c?R=mid,l=mid+1:r=mid-1;
ans[L]+=c,ans[R+1]-=c;
}
rec.clear();
}
signed main() {
#ifdef Plus_Cat
freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
I(n);
FOR(i,1,n)I(a[i]),b[i]=a[i];
sort(b+1,b+n+1),b[0]=unique(b+1,b+n+1)-b-1;
FOR(i,1,n)a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
FOR(i,1,n)vec[a[i]].push_back(i);
FOR(i,1,b[0])Solve_Min(vec[i]);
FOR(i,1,n)O(ans[i]+=ans[i-1],'\n');
return 0;
}
\(O(n\sqrt{n\log_2{n}})\)
發現其實相同顏色中 \(x\le \sqrt{n}\) 的部分，直接暴力求解反而更快，這部分復雜度變成了 \(O(n\sqrt{n})\)。
進一步調整塊長，發現如果 \(x\le \sqrt{n\log_2{n}}\) 的部分都暴力求解，復雜度就變成了 \(O(n\sqrt{n\log_2{n}})\)。
void Solve(const Vi &vec) {
FOR(i,1,Bl) {
int tmp(Check1(vec,i));
ans[i]+=tmp,ans[i+1]-=tmp;
}
for(int L(Bl+1),R(Bl+1),c(Check(vec,Bl+1)); L<=n; c=Check(vec,L=++R)) {
for(int l(L+1),r(n),mid((l+r)>>1); l<=r; mid=(l+r)>>1)
Check(vec,mid)>=c?R=mid,l=mid+1:r=mid-1;
ans[L]+=c,ans[R+1]-=c;
}
rec.clear();
}
signed main() {
#ifdef Plus_Cat
freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
I(n),Bl=ceil(sqrt(n*log2(n)));
FOR(i,1,n)I(a[i]),b[i]=a[i];
sort(b+1,b+n+1),b[0]=unique(b+1,b+n+1)-b-1;
FOR(i,1,n)a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
FOR(i,1,n)vec[a[i]].push_back(i);
FOR(i,1,b[0])Solve(vec[i]);
FOR(i,1,n)O(ans[i]+=ans[i-1],'\n');
return 0;
}
\(O(n\sqrt{n})\)
要求一個整數序列 \((a_1,a_2,\ldots,a_n)\)。已知：
- 它是非遞增的，即 \(a_k \ge a_{k+1}\)。
- \(0 \le a_k \le \frac{n}{k}\)。
可以在 \(O(C)\) 時間內得到 \(a_k\) 的一個值，則可以在 \(O(n+\sqrt{n}C)\) 的復雜度內求出整個序列。
我們仿照上面那篇博文分析一下復雜度：
令 \(a_0=n+1,a_{n+1}=0\)，然后開始分治：
假設現在分治區間為 \([l,r]\)，則：
- 如果 \(a_{l-1}=a_{r+1}\)，則全部賦為同值。
- 否則求出 \(a_{mid}\)，然后遞歸 \([l,mid),(mid,r]\)。
那么對于深度為 \(d\) 的一層，求值操作數量是 \(O(2^{\fracw0obha2h00{2}})\) 級別的。
所以總復雜度為：
\[\sum_{d=0}^{\lceil \log_2{n} \rceil} 2^{\fracw0obha2h00{2}} \\
\]
即 \(O(\sqrt{n})\)。那么我們也這么干就可以了。
//#define Plus_Cat ""
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define Vi vector<int>
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(1e5+10);
namespace IOEcat {
//...
} using namespace IOEcat;
int n,Bl;
int a[N],b[N],ans[N];
Vi vec[N];
int Check1(const Vi &vec,const int &lim) {
int cnt(0),sta(0);
for(const int &x:vec)if(!sta||x-sta>lim)++cnt,sta=x;
return cnt;
}
int Check2(const Vi &vec,const int &lim) {
int cnt(0),sta(vec.front());
while(true) {
++cnt;
int it(upper_bound(vec.begin(),vec.end(),sta+lim)-vec.begin());
if(it==(int)vec.size())break;
sta=vec[it];
}
return cnt;
}
int Check(const Vi &vec,const int &lim) {
auto cal=[&]() -> ll { return (ll)vec.size()*lim/n; };
return cal()<20&&(1<<cal())<(int)vec.size()?Check1(vec,lim):Check2(vec,lim);
}
void Sep(int l,int r,int vl,int vr,const Vi &vec) {
#define mid ((l+r)>>1)
if(l>r)return;
if(vl==vr)return ans[l]+=vl,ans[r+1]-=vr,void();
int vm(Check(vec,mid));
ans[mid]+=vm,ans[mid+1]-=vm,Sep(l,mid-1,vl,vm,vec),Sep(mid+1,r,vm,vr,vec);
#undef mid
}
signed main() {
#ifdef Plus_Cat
freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
I(n),Bl=ceil(sqrt(n*log2(n)));
FOR(i,1,n)I(a[i]),b[i]=a[i];
sort(b+1,b+n+1),b[0]=unique(b+1,b+n+1)-b-1;
FOR(i,1,n)a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
FOR(i,1,n)vec[a[i]].push_back(i);
FOR(i,1,b[0])Sep(1,n,n,1,vec[i]);
FOR(i,1,n)O(ans[i]+=ans[i-1],'\n');
return 0;
}
浙公網安備 33010602011771號