20190826口胡

· · 个人记录

随便写点东西

填一下很久以前的某个坑

考虑我有任意一个数列f和一个积性函数g，我要计算i\in[1,n]的f和g的狄利克雷卷积f\ast g(i)

设

h_{i,n}=\sum_{d\mid n,\text{d只含前i个质因子}}f(\frac{n}{d})g(d)

那么考虑第i个素数p_i并枚举n中有p_i的几次幂，有

h_{i,n}=\sum_{k\geq 0,dp_i^k\mid n,\text{d只含前i-1个质因子}}f(\frac{n}{dp_i^k})g(dp_i^k)=\sum_{k\geq 0,p_i^k\mid n}g(p_i^k)h_{i-1,n/(p_i^k)}

假设g(p_i^k)可以O(1)计算，那么使用这个式子转移，对第i个素数的复杂度是

O(\sum_{k\geq 1}\left\lfloor\frac{n}{p_i^k}\right\rfloor)=O(\frac{n}{p_i}\sum_{k\geq 0}p_i^{-k})=O(\frac{n}{p_i-1})

于是总的复杂度就是

O(\sum_{i=1}^{\pi(n)}\frac{n}{p_i-1})=O(n\log\log n)

不过常数很大的样子

一个还行的实现:

//假设f已经处理好
for(int i=1;i<=prime_cnt;i++)
{
    int pm=prime[i];
    if(1ll*pm*pm<=n)
    {
        for(int j=n/pm;j>=1;j--)
            for(int k=pm;k*j<=n;k*=pm)
                f[k*j]+=f[j]*g[k];
    }
    else
    {
        for(int j=n/pm;j>=1;j--)
            f[j*pm]+=f[j]*g[pm];
    }
}
//事实上可以手动算出prime[i]^2<=n的位置然后分开循环...卡常空间很大...

然后是块爷上午看错题引发的惨案

给一棵树，每个点有黑或白色，支持:

  1. 把某个点染成黑色，如果这个点原来不是黑色那么递归它的子树进行这个操作

  2. 把某个点的子树染成白色

  3. 询问某个点的颜色

块给了一个根号重构的做法我不会...所以这里只有树剖的两个\log做法

考虑给每个点加一个时间戳表示它最后变成当前颜色的时间，对于1操作我们可以只在操作点进行修改，于是对于查询有:

  1. 如果这个点是黑色那么它就是黑色.

  2. 如果这个点是白色，那么我们找到它的祖先中第一个黑色点，比较两个点的时间戳，如果黑点的时间戳大于当前点那么它是黑的，否则是白的.如果祖先中不存在一个黑点那么它也是白的.

这样子1操作就是一个单点修改，2操作就是子树赋值.不过要注意1操作要先查询修改点的颜色，如果是白的才进行修改.

对于询问，用线段树维护一段区间最靠右的黑点的时间戳以及区间内是否存在黑点(因为在一条重链上线段树是以深度递增的)，每次树剖往上跳即可.

O(n\log^2 n) 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6;
struct Node
{
    int c,t;
    Node operator +(const Node &a)const
    {
        return a.c?(Node){a.c,a.t}:(Node){c,t};
    }
}a[N];
int col[N],w[N],to[N],n,m,mm,fst[N],nxt[N],size[N],f[N],tp[N],dep[N],son[N],id[N],dfs_cnt,tag[N];
void ade(int u,int v){to[++mm]=v,nxt[mm]=fst[u],fst[u]=mm;}
void dfs1(int u,int fa)
{
    dep[u]=dep[fa]+1,f[u]=fa,size[u]=1;int mx=0;
    for(int i=fst[u];i;i=nxt[i])
    {
        int v=to[i];if(v==fa)continue;
        dfs1(v,u);size[u]+=size[v];
        if(size[v]>mx)mx=size[v],son[u]=v;
    }
}
void dfs2(int u,int top)
{
    tp[u]=top,id[u]=++dfs_cnt;w[dfs_cnt]=col[u];
    if(son[u])dfs2(son[u],top);
    for(int i=fst[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v!=f[u]&&v!=son[u])dfs2(v,v);
    }
}
void build(int rot,int lt,int rt)
{
    if(lt==rt){a[rot]=(Node){w[lt],0};return;}
    int mid=(lt+rt)>>1;
    build(rot<<1,lt,mid),build(rot<<1|1,mid+1,rt);
    a[rot]=a[rot<<1]+a[rot<<1|1];
}
void upd(int rot,int w){tag[rot]=w;a[rot]=(Node){0,w};}
void pushdown(int rot)
{
    if(tag[rot])
    {
        int t=tag[rot];tag[rot]=0;
        upd(rot<<1,t),upd(rot<<1|1,t);
    }
}
Node query(int rot,int lt,int rt,int lq,int rq)
{
    if(lt>=lq&&rt<=rq)return a[rot];
    int mid=(lt+rt)>>1;pushdown(rot);
    if(rq<=mid)return query(rot<<1,lt,mid,lq,rq);
    else if(lq>mid)return query(rot<<1|1,mid+1,rt,lq,rq);
    else return query(rot<<1,lt,mid,lq,mid)+query(rot<<1|1,mid+1,rt,mid+1,rq);
}
void update2(int rot,int lt,int rt,int lq,int rq,int w)
{
    if(lt>=lq&&rt<=rq){upd(rot,w);return;}
    int mid=(lt+rt)>>1;pushdown(rot);
    if(rq<=mid)update2(rot<<1,lt,mid,lq,rq,w);
    else if(lq>mid)update2(rot<<1|1,mid+1,rt,lq,rq,w);
    else update2(rot<<1,lt,mid,lq,mid,w),update2(rot<<1|1,mid+1,rt,mid+1,rq,w);
    a[rot]=a[rot<<1]+a[rot<<1|1];
}
void update1(int rot,int lt,int rt,int q,int w)
{
    if(lt==rt){a[rot]=(Node){1,w};return;}
    int mid=(lt+rt)>>1;pushdown(rot);
    if(q<=mid)update1(rot<<1,lt,mid,q,w);
    else update1(rot<<1|1,mid+1,rt,q,w);
    a[rot]=a[rot<<1]+a[rot<<1|1];
}
int query(int x)
{
    Node t=query(1,1,n,id[x],id[x]);
    if(t.c==1)return 1;int tm=t.t;
    while(x)
    {
        t=query(1,1,n,id[tp[x]],id[x]);
        if(t.c)
        {
            if(t.t>tm)return 1;
            else return 0;
        }
        x=f[tp[x]];
    }
    return 0;
}
void update2(int x,int w)
{
    update2(1,1,n,id[x],id[x]+size[x]-1,w);
}
void update1(int x,int w)
{
    if(query(x))return;
    update1(1,1,n,id[x],w);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",col+i);
    for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),ade(u,v),ade(v,u);
    dfs1(1,0),dfs2(1,1);build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        switch(opt)
        {
            case 1:update1(x,i);break;
            case 2:update2(x,i);break;
            case 3:printf("%d\n",query(x));break;
        }
    }
}

但是这个做法不适用于更多颜色的情况...以下是块的加强版:

一共有k+1种颜色，其中1种是白色，操作有三种:

  1. 把某个点染成颜色c且c不是白色，如果它原来不是这个颜色就递归子树进行该操作

  2. 把某个点的子树染成白色

  3. 询问某个点的颜色

根号分治依然适用但树剖就不行了...先咕咕咕着...