25/10/03
T1
给你一个数 \(n\)，你想知道对于 \(m(1≤m≤n)\)，有多少个满足 \(\frac{n}{m}\) 是整数或者可以被表示成 \(a+\frac{1}{b}(a≥1,b≥2,a,b∈N)\) 的形式。
由于这个问题太简单了，请对 \([L,R]\) 之间的所有整数回答。由于答案很大，记 \(f(n)\) 表示 \(n\) 的答案，输出 \(\sum_{n=L}^R(f(n)⊕n)\) 的结果。
Solution
\(\frac{n}{m}=a+\frac{1}{b}=\frac{ab+1}{b}\)，设 \(n=(ab+1)c\)。
整数的情况可以视为 \(b=1\) 的情况，还要加上 \(n=m\) 的情况。
我们考虑类似根号分治的东西，令 \(T=R^{\frac{1}{3}}\)：
- 对于 \(c\le T\) 的，枚举 \(c\) 和 \(a,b\) 中最小的那一个，复杂度 \(O(R^{\frac{2}{3}})\)。
- 对于 \(c>T\) 的，我们选择枚举 \(ab(<\frac{R}{T})\)，复杂度 \(O(R^{\frac{2}{3}})\)。
因为还要枚举另一项更新答案，复杂度还要加上 \(O(\sum_{n=L}^Rf(n))\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5,V=7e7+5;
ll L,R,T,ans[N],res;
ll pr[V],f[V],tot;
bool vis[V];
void Init() {
f[1]=1;
int mx=R/(T+1);
for(int i=2;i<=mx;i++) {
if(!vis[i]) {
pr[++tot]=i;
f[i]=2;
}
for(int j=1;j<=tot&&i*pr[j]<=mx;j++) {
vis[i*pr[j]]=1;
if(!(i%pr[j])) {
f[i*pr[j]]=f[i]*f[pr[j]]-f[i/pr[j]];
break;
}
f[i*pr[j]]=f[i]*f[pr[j]];
}
}
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>L>>R;
T=min(R,(ll)pow(R,0.33));
for(ll c=1;c<=T;c++) {
for(ll a=1;(a*a+1)*c<=R;a++) {
for(ll b=max(a,(L-c+a*c-1)/(a*c));(a*b+1)*c<=R;b++) {
++ans[(a*b+1)*c-L];
if(a!=b) ++ans[(a*b+1)*c-L];
}
}
}
/*预处理 $1\sim n/T$ 的约数个数或直接枚举
for(ll a=1;(a*a+1)*(T+1)<=R;a++) {
for(ll b=a;(a*b+1)*(T+1)<=R;b++) {
for(ll c=max((L+a*b)/(a*b+1),T+1);(a*b+1)*c<=R;c++) {
++ans[(a*b+1)*c-L];
if(a!=b) ++ans[(a*b+1)*c-L];
}
}
}*/
Init();
for(ll ab=1;(ab+1)*(T+1)<=R;ab++) {
for(ll c=max((L+ab)/(ab+1),T+1);(ab+1)*c<=R;c++) {
ans[(ab+1)*c-L]+=f[ab];
}
}
for(ll i=L;i<=R;i++) res+=i^(ans[i-L]+1);
cout<<res;
return 0;
}
T2 P9292 [ROI 2018] Robomarathon
Subtask 1
对于每个人直接在它的位置上放喇叭就行。
答案即为左边 \(a_j-j<a_i-i\) 的 \(j\) 个数，加上右边 \(a_j+j<a_i+i\) 的 \(j\) 个数。
Subtask 2
对于 \(i\) 的答案，我们如果在一个位置放喇叭，距离 \(i\) 大于等于这个位置的也会贪心地放上喇叭。
假设 \(i\le\frac{n}{2}\)，发现在第一个位置与第一个位置关于 \(i\) 对称的及后面的位置都放上喇叭（情况一），或者只在最后一个位置放上喇叭（情况二），会让选手发挥最差。
\(i>\frac{n}{2}\) 同理。
下面计算情况一，令 \(len=\min(i-1,n-i)\)，分类讨论每个 \(j\) 的贡献：
- \(i-len\le j <i\)，贡献为 \([a_j+j<a_i+i]\)。
- \(i<j\le i+len\)，贡献为 \([a_j-j<a_i-i]\)。
- \(j<i-len\)，贡献为 \([a_j<a_i+len]\)。
- \(j>i+len\)，贡献为 \([a_j<a_i+len]\)。
就是一个简单二维数点。
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=4e5+5;
int n,typ,a[N],qt;
int ans[N];
struct BIT {
int S[N];
void Update(int x,int v) {
for(;x<=n;x+=x&-x) S[x]+=v;
}
int Query(int x) {
int res=0;
for(;x;x-=x&-x) res+=S[x];
return res;
}
int Query(int x,int y) {
return Query(y)-Query(x-1);
}
}B1;
struct QRY {
int l,r,v,id;
}Q[N*3];
vector<pair<int,int> > qry1[N],qry2[N],qry3[N];
void Add(int l,int r,int v,int id) {
Q[++qt]={l,r,v,id};
}
void Calc1() {
for(int i=1;i<=n;i++) B1.S[i]=0;
sort(Q+1,Q+qt+1,[](const QRY &x,const QRY &y) {
return x.v==y.v?x.id<y.id:x.v<y.v;
});
for(int i=1;i<=qt;i++)
if(Q[i].id) ans[Q[i].id]+=B1.Query(Q[i].l,Q[i].r);
else B1.Update(Q[i].l,1);
}
void Calc2() {
sort(Q+1,Q+n+1,[](const QRY &x,const QRY &y) {
return x.v<y.v;
});
for(int l=1,r=1;l<=n;l=r+1,++r) {
while(r<n&&Q[l].v==Q[r+1].v) ++r;
for(int i=l;i<=r;i++) ans[Q[i].id]=max(ans[Q[i].id],l-1);
}
}
void Solve1() {
for(int i=1;i<=n;i++) {
Add(1,i-1,a[i]-i-1,i);
Add(i,i,a[i]-i,0);
}
Calc1();
qt=0;
for(int i=1;i<=n;i++) {
Add(i+1,n,a[i]+i-1,i);
Add(i,i,a[i]+i,0);
}
Calc1();
}
void Solve2() {
for(int i=1;i<=n;i++) {
int len=min(i-1,n-i),pl=i-len,pr=i+len;
Add(1,pl-1,(a[i]+n-i)-1,i);
Add(pr+1,n,(a[i]+i-1)-1,i);
Add(i,i,a[i],0);
}
Calc1();
qt=0;
for(int i=1;i<=n;i++) {
int len=min(i-1,n-i),pl=i-len,pr=i+len;
Add(pl,i-1,(a[i]+i)-1,i);
Add(i,i,a[i]+i,0);
}
Calc1();
qt=0;
for(int i=1;i<=n;i++) {
int len=min(i-1,n-i),pl=i-len,pr=i+len;
Add(i+1,pr,(a[i]-i)-1,i);
Add(i,i,a[i]-i,0);
}
Calc1();
for(int i=1;i<=n;i++) Q[i]={0,0,a[i]-i,i};
Calc2();
for(int i=1;i<=n;i++) Q[i]={0,0,a[i]+i,i};
Calc2();
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>typ;
for(int i=1;i<=n;i++) cin>>a[i];
if(typ==1) Solve1();
else Solve2();
for(int i=1;i<=n;i++) cout<<ans[i]+1<<"\n";
return 0;
}