[SHOI2006] 作业 Homework
根号分治的板题吧，当 \(x\leq B\) 的时候直接查询。
否则用 set 枚举 \(i\) 查询最小的 \(sum-x\times i\geq 0\) 的 \(sum\) 值取最小即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N=300005,B=548;
int n,x,d[N];char op;set<int> st;
void update(int x){st.insert(x);for(int i=1;i<=B;i++) d[i]=min(d[i],x%i);
}
int query(int x,int res=INF){if(x<=B) return d[x];for(int i=0;;i++){auto it=st.lower_bound(x*i);if(it==st.end()) return res;res=min(res,*it-x*i);}
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>n,fill(d,d+N,INF);for(int i=1;i<=n;i++){cin>>op>>x;if(op=='A') update(x);else cout<<query(x)<<"\n";}
}
CF1822G2 Magic Triples
Easy Version 时可以枚举中间数并 \(O(\sqrt{V})\) 枚举因数 \(b\) 计算答案。
Hard Version 中直接枚举中间数的做法当 \(a_i>10^6\) 时会 TLE，考虑基于此优化。
发现 \(\frac{10^9}{10^6}=10^3=\sqrt{10^6}\)，所以 \(a_i>10^6\) 时将枚举因数改为枚举倍数即可。
由于值域过大，使用 map 存储信息，注意这题使用 unordered_map 会神秘 TLE。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define int long long
int t,n,ans,a[N];map<int,int> mp;
int count(int x){return mp.count(x)?mp[x]:0;}
void solve(){cin>>n,ans=0,mp.clear();for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;for(auto [x,y]:mp){ans+=y*(y-1)*(y-2);if(x!=1) ans+=count(1)*count(x*x)*y;if(x<=1000000) for(int i=2;i*i<=x;i++){if(x%i!=0) continue;ans+=count(x/i)*count(x*i)*y;if(i*i==x) continue;ans+=count(i)*count(x*x/i)*y;}else for(int i=2;i*x<=1000000000;i++){if(x%i!=0) continue;ans+=count(x/i)*count(x*i)*y;}}return cout<<ans<<"\n",void();
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>t;while(t--) solve();
}
[Ynoi2013] 无力回天 NOI2017
把并集转交集，考虑对值的出现次数根号分治。
出现次数 \(>B\) 的 bitset 维护，修改 \(O(1)\)，查询 \(O(\frac{m}{Bw})\)。
出现次数 \(\leq B\) 的哈希表维护集合两两之间答案就行了，修改 \(O(B)\)，查询 \(O(1)\)。
这里取 \(B=\sqrt{\frac{m}{w}}\) 达到理论最优复杂度 \(O(m\sqrt{\frac{m}{w}})\)。
于是我们获得了初版代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int N=1000005,B=176;
vector<int> v[N];
bitset<(N+B-1)/B> bs[N];
gp_hash_table<int,int> mp[N];
int n,cnt,sum[N],op[N],x[N],y[N],num[N],app[N];
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>n,fill(num,num+n+1,-1);for(int i=1;i<=n;i++){cin>>op[i]>>x[i]>>y[i];if(op[i]==1) app[y[i]]++;if(op[i]==2&&x[i]>y[i]) swap(x[i],y[i]);}for(int i=1;i<=n;i++) if(app[i]>=B) num[i]=cnt++;for(int i=1;i<=n;i++){if(op[i]==1){if(num[y[i]]==-1){for(auto it:v[y[i]])mp[min(it,x[i])][max(it,x[i])]++;v[y[i]].push_back(x[i]),sum[x[i]]++;}else bs[x[i]][num[y[i]]]=1,sum[x[i]]++;}else{if(x[i]==y[i]){cout<<sum[x[i]]<<"\n";continue;}int res=sum[x[i]]+sum[y[i]]-mp[x[i]][y[i]];cout<<res-(bs[x[i]]&bs[y[i]]).count()<<"\n";}}
}
但是发现 MLE 死得很惨，考虑把哈希表和 bitset 都搞成指针，第一次插入的时候再分配内存。
于是我们获得了第二版代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define gp gp_hash_table
const int N=1000005,B=176;
vector<int> v[N];
bitset<(N+B-1)/B> *bs[N];
gp_hash_table<int,int> *mp[N];
int n,cnt,sum[N],op[N],x[N],y[N],num[N],app[N];
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>n,fill(num,num+n+1,-1);for(int i=1;i<=n;i++){cin>>op[i]>>x[i]>>y[i];if(op[i]==1) app[y[i]]++;if(op[i]==2&&x[i]>y[i]) swap(x[i],y[i]);}for(int i=1;i<=n;i++) if(app[i]>=B) num[i]=cnt++;for(int i=1;i<=n;i++){if(op[i]==1){if(num[y[i]]==-1){for(auto it:v[y[i]]){int tx=min(it,x[i]),ty=max(it,x[i]);if(!mp[tx]) mp[tx]=new gp<int,int>();(*mp[tx])[ty]++;}v[y[i]].push_back(x[i]),sum[x[i]]++;}else{if(!bs[x[i]]) bs[x[i]]=new bitset<(N+B-1)/B>();bs[x[i]]->set(num[y[i]]),sum[x[i]]++;}}else{if(x[i]==y[i]){cout<<sum[x[i]]<<"\n";continue;}int res=sum[x[i]]+sum[y[i]];if(mp[x[i]]) res-=(*mp[x[i]])[y[i]];if(bs[x[i]]&&bs[y[i]]) res-=(*bs[x[i]]&*bs[y[i]]).count();cout<<res<<"\n";}}
}
惊奇地发现现在又 TLE 了，注意到哈希表插入很慢，并且进行了很多无效插入。
所以先把所有询问放到哈希表里面，然后修改时判一下要不要改，这样就可以通过了。
于是我们获得了最终版代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int N=1000005,B=176;
vector<int> v[N];
bitset<(N+B-1)/B> *bs[N];
gp_hash_table<int,int> *mp[N];
int n,cnt,sum[N],op[N],x[N],y[N],num[N],app[N];
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);cin>>n,fill(num,num+n+1,-1);for(int i=1;i<=n;i++) cin>>op[i]>>x[i]>>y[i],app[y[i]]+=(op[i]==1);for(int i=1;i<=n;i++) if(app[i]>=B) num[i]=cnt++;for(int i=1;i<=n;i++){if(op[i]==1) continue;if(x[i]>y[i]) swap(x[i],y[i]);if(!mp[x[i]]) mp[x[i]]=new gp_hash_table<int,int>();(*mp[x[i]])[y[i]]=0;}for(int i=1;i<=n;i++){if(op[i]==1){if(num[y[i]]==-1){for(auto it:v[y[i]]){int tx=min(it,x[i]),ty=max(it,x[i]);if(mp[tx]&&mp[tx]->find(ty)!=mp[tx]->end()) (*mp[tx])[ty]++;}v[y[i]].push_back(x[i]),sum[x[i]]++;}else{if(!bs[x[i]]) bs[x[i]]=new bitset<(N+B-1)/B>();bs[x[i]]->set(num[y[i]]),sum[x[i]]++;}}else{if(x[i]==y[i]){cout<<sum[x[i]]<<"\n";continue;}int res=sum[x[i]]+sum[y[i]];if(bs[x[i]]&&bs[y[i]]) res-=(*bs[x[i]]&*bs[y[i]]).count();if(mp[x[i]]&&mp[x[i]]->find(y[i])!=mp[x[i]]->end()) res-=(*mp[x[i]])[y[i]];cout<<res<<"\n";}}
}