P3157 [CQOI2011]动态逆序对
考虑一个逆序对在什么时候会对答案造成影响。
假设我们想要找到第 \(i\) 个结点被删除时所减少的逆序对个数。
记 \(a_i\) 表示第 \(i\) 个点的权值，\(t_i\) 表示第 \(i\) 个点的删除时间。那么满足条件的逆序对满足如下两个条件之一：
- \(t_i > t_j , i>j , a_i<a_j\)。
- \(t_i > t_j , i<j , a_i>a_j\)。
这是一个显然的三维偏序，跑两次 \(\texttt{cdq}\) 分治即可。
时间复杂度 \(O(n\log^2 n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lowbit(x) x&-x
using namespace std;
const int N=2e5+10;
struct node{
int pos,t,a,ans;
}a[N];
ll ans;
int n,m,T,b[N],d[N],k,pos[N];
inline int read(){
int s=0,f=0;
char ch=getchar();
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return f?-s:s;
}
inline void add(int x,int c){for(;x<=n;x+=lowbit(x)) d[x]+=c;}
inline int query(int x,int res=0){for(;x;x-=lowbit(x)) res+=d[x];return res;}
inline bool cmp1(node a,node b){
return a.t>b.t;
}
inline bool cmp2(node a,node b){
return a.pos<b.pos;
}
inline bool cmp3(node a,node b){
return a.pos>b.pos;
}
inline bool cmp4(node a,node b){
return a.t<b.t;
}
inline void solve(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
solve(l,mid),solve(mid+1,r);
sort(a+l,a+mid+1,cmp2),sort(a+mid+1,a+r+1,cmp2);
int maxn=l;
for(register int i=mid+1;i<=r;++i){
while(a[maxn].pos<a[i].pos&&maxn<=mid){
add(a[maxn].a,1);
++maxn;
}
a[i].ans+=query(n)-query(a[i].a);
}
for(register int i=l;i<maxn;++i) add(a[i].a,-1);
}
inline void solve2(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
solve2(l,mid),solve2(mid+1,r);
sort(a+l,a+mid+1,cmp3),sort(a+mid+1,a+r+1,cmp3);
int maxn=l;
for(register int i=mid+1;i<=r;++i){
while(a[maxn].pos>a[i].pos&&maxn<=mid){
add(a[maxn].a,1);
++maxn;
}
a[i].ans+=query(a[i].a);
}
for(register int i=l;i<maxn;++i) add(a[i].a,-1);
}
int main(){
n=read(),m=read();
for(register int i=1;i<=n;++i){
int x=read();
a[i].pos=i;
a[i].a=x;
pos[x]=i;
b[i]=x;
}
for(register int i=1;i<=m;++i){
int x=read();
a[pos[x]].t=i;
}
for(register int i=1;i<=n;++i) if(a[i].t==0) a[i].t=m+1;
for(register int i=n;i>=1;--i) ans+=query(b[i]),add(b[i],1);
for(register int i=1;i<=n;++i) d[i]=0;
sort(a+1,a+n+1,cmp1);
solve(1,n);
sort(a+1,a+n+1,cmp1);
for(register int i=1;i<=n;++i) d[i]=0;
solve2(1,n);
sort(a+1,a+n+1,cmp4);
for(register int i=1;i<=m;++i) printf("%lld\n",ans),ans-=a[i].ans;
return 0;
}
P3935 Calculating
发现 \(f_i\) 即为 \(i\) 的因子个数。
式子可以变为
\[\sum\limits_{i=l}^r \sum_{d | i} 1 \]套路的，将 \(d\) 拉到前面去。
\[\sum\limits_{d=1}^n \sum\limits_{i=1}^{\large \lfloor \frac{n}{d}\rfloor} 1 \]明显可以把后面那个 \(\sum\) 搞掉。
那么就是
\[\sum\limits_{d=1}^n \lfloor \frac{n}{d} \rfloor \]整除分块即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lowbit(x) x&-x
using namespace std;
const int mod=998244353;
ll ans;
int n,m,T;
inline int read(){
int s=0,f=0;
char ch=getchar();
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return f?-s:s;
}
inline int calc(int n){
int res=0;
for(register int l=1,r;l<=n;l=r+1){
r=n/(n/l);
res=(res+(r-l+1)%mod*(n/l)%mod)%mod;
}
return res;
}
signed main(){
n=read(),m=read();
printf("%lld\n",(calc(m)-calc(n-1)+mod)%mod);
return 0;
}
P1829 [国家集训队]Crash的数字表格 / JZPTAB
莫反练手题。
先推一推式子。
\[\begin{equation} \begin{aligned} &\sum\limits_{i=1}^n \sum\limits_{j=1}^m lcm(i,j)\\ =&\sum\limits_{i=1}^n \sum\limits_{j=1}^m \frac{i\times j}{\gcd(i,j)}\\ =&\sum\limits_{d=1}^n d \sum\limits_{i=1}^{\large \lfloor \frac{n}{d} \rfloor} \sum\limits_{j=1}^{\large \lfloor \frac{m}{d} \rfloor} i \times j \times [\gcd(i,j) = 1] \end{aligned} \end{equation} \]考虑单独计算后面的部分。
我们记 \(f(n,m) = \sum\limits_{i=1}^n \sum\limits_{j=1}^m i \times j \times [\gcd(i,j)=1]\)。
考虑使用莫反将它化简。
\[\begin{equation} \begin{aligned} &\sum\limits_{i=1}^n \sum\limits_{j=1}^m \sum\limits_{d|\gcd(i,j)} \mu(d) \times i \times j\\ =&\sum\limits_{d=1}^n \mu(d) \sum\limits_{i=1}^{\large \lfloor \frac{n}{d} \rfloor} \sum\limits_{j=1}^{\large \lfloor \frac{m}{d} \rfloor} i \times d \times j \times d\\ =&\sum\limits_{d=1}^n \mu(d) \times d^2 \sum\limits_{i=1}^{\large \lfloor \frac{n}{d} \rfloor} \sum\limits_{j=1}^{\large \lfloor \frac{m}{d} \rfloor} i \times j \end{aligned} \end{equation} \]这样就看起来非常可做了对吧。
前面的一部分可以线性筛 \(+\) 前缀和预处理，后面一部分 \(O(1)\) 算法显然，化简一下即可，这里不赘述。
带回原式，式子变成了 \(\sum\limits_{d=1}^n d \times f(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)\)。
对于后面的部分整除分块即可。
总复杂度就是 \(O(\sqrt{n} \times \sqrt{n}) = O(n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lowbit(x) x&-x
using namespace std;
const int N=1e7+10;
const int mod=20101009;
const int inv=10050505;
ll ans;
bool vist[N];
int n,m,T,prime[N],tot,mo[N],s[N];
inline int read(){
int s=0,f=0;
char ch=getchar();
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return f?-s:s;
}
inline void init(){
mo[1]=1;
for(register int i=2;i<=n;++i){
if(!vist[i]) prime[++tot]=i,mo[i]=-1;
for(register int j=1;j<=tot&&1ll*prime[j]*i<=n;++j){
vist[i*prime[j]]=1;
if(i%prime[j]==0){
mo[i*prime[j]]=0;
break;
}
mo[i*prime[j]]=-mo[i];
}
}
}
inline int g(int n,int m){
return n*(n+1)%mod*inv%mod*m%mod*(m+1)%mod*inv%mod;
}
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
inline int calc(int n,int m){
int res=0;
for(register int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
res=(res+g(n/l,m/l)*((s[r]-s[l-1]+mod)%mod)%mod)%mod;
}
return res;
}
inline int work(int n,int m){
int res=0;
for(register int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
res=(res+calc(n/l,m/l)*((r+l)%mod*(r-l+1)%mod*inv%mod)%mod)%mod;
}
return res;
}
signed main(){
n=read(),m=read();
if(n>m) swap(n,m);
init();
for(register int i=1;i<=n;++i) s[i]=(1ll*s[i-1]+1ll*i*i%mod*mo[i]%mod)%mod;
printf("%lld\n",work(n,m));
return 0;
}