100道cf2100分-526互联

考虑这些被释放的，值一定相同，并且等于区间gcd
于是用st表询问区间gcd，map套二分实现区间里某个数字出现次数

int n,a[100010];
int f[100010][20],lgn[100010];
map<int,vector<int>>pos;
int ask(int l,int r)
{
    int s=lgn[r-l+1];
    return __gcd(f[l][s],f[r-(1<<s)+1][s]);
}
int main() 
{
    // freopen("1.in","r",stdin);
    n=read();
    for(int i=1;i<=n;i++){
        f[i][0]=a[i]=read();
        pos[a[i]].push_back(i);
    }
    lgn[1]=0;
    for(int i=2;i<=n;i++)
        lgn[i]=lgn[i/2]+1;
    int logn=lgn[n];
    for(int j=1;j<=logn;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=__gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for(int m=read();m;m--)
    {
        int l=read(),r=read();
        int gcd=ask(l,r);
        if(lower_bound(pos[gcd].begin(),pos[gcd].end(),l)==pos[gcd].end())
            cout<<r-l+1<<"\n";
        else
            cout<<r-l+1-(upper_bound(pos[gcd].begin(),pos[gcd].end(),r)-lower_bound(pos[gcd].begin(),pos[gcd].end(),l))<<'\n';
    }
}

474F

注意到确定一个起点后，这棵树的答案就是固定的了，是Σd[i]，其中d[x]表示到起点的路径上的点的数量
用换根dp维护之
具体地，第一遍dfs得到初始的d数组和f数组，f[i]表示令1为根，以i为根的子树的Σd[x]
第二遍dfs维护上面的点距离x的距离之和与上面的点的数量，往下走的时候修改一下即可

int n;
vector<int>e[200010];
ll f[200010],ans,d[200010],cnt[200010];
void dfs(int x)
{
    f[x]=d[x];
    cnt[x]=1;
    for(auto y:e[x]){
        if(d[y])
            continue;
        d[y]=d[x]+1;
        dfs(y);
        f[x]=f[x]+f[y];
        cnt[x]+=cnt[y];
    }
}
void dfs1(int x,ll sum,int num)
{
    ans=max(ans,f[x]-(d[x]-1)*cnt[x]+sum);
    for(auto y:e[x])
    {
        if(d[y]<d[x])
            continue;
        int numm=cnt[x]-cnt[y];//子树里除了y的子树还剩几个点
        dfs1(y,sum+num+f[x]-f[y]-(d[x]-2)*numm,num+numm);
    }
}
int main() 
{
    // freopen("1.in","r",stdin);
    n=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    d[1]=1;
    dfs(1);
    dfs1(1,0,0);
    cout<<ans;
}

1187E

考虑二分答案
对于mid，考虑枚举ai，则需要检查[k*a[i]+x,k*a[i]+a[i]-1]这个区间里有没有数字
复杂度nlog^2
不二分答案也行，考虑枚举ai，查找[k*a[i],(k+1)*a[i])区间里最后一个出现的数字，更新答案，复杂度仍然是nlog^2
int n,a[200010],c[1000010];
int check(int x)
{
    for(int i=1;i<=n;i++)
        for(int r=min(1000000,a[i]*2-1),l=a[i]+x;l<=r;l+=a[i],r=min(1000000,r+a[i]))
            if(c[r]-c[l-1])
                return 1;
    return 0;
}
int main()
{
    // freopen("1.in","r",stdin);
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+1+n);
    n=unique(a+1,a+1+n)-a-1;
    for(int i=1;i<=n;i++)
        c[a[i]]=1;
    for(int i=1;i<=1000000;i++)
        c[i]+=c[i-1];
    int l=1,r=1000000,mid;
    while(l+1<r)
    {
        mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    if(check(r))
        cout<<r;
    else if(check(l))
        cout<<l;
    else
        cout<<0;
}

484B

点分治板子
考虑1 2 3 4 5 6 7这个链应该怎么做
可以发现是4最高，26次之，1357最低
于是点分治的过程中给分治的那个点赋值即可

int vis[100010],siz[100010],wt[100010];
int n,Root,Tsiz,now='A'-1;
char ans[100010];
vector<int>e[100010];
void getroot(int x,int f)
{
    siz[x]=1;
    wt[x]=0;
    for(auto y:e[x])
    {
        if(y==f||vis[y])
            continue;
        getroot(y,x);
        siz[x]+=siz[y];
        wt[x]=max(wt[x],siz[y]);
    }
    wt[x]=max(wt[x],Tsiz-siz[x]);
    if(wt[Root]>wt[x])
        Root=x;
}
void DFS(int x)
{
    now++;
    ans[x]=now;
    vis[x]=1;
    for(auto y:e[x])
    {
        if(vis[y])
            continue;
        Root=0;
        Tsiz=siz[y];
        getroot(y,0);
        DFS(Root);
    }
    now--;
}
int main()
{
    // freopen("1.in","r",stdin);
    n=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    wt[Root=0]=0x3f3f3f3f;
    Tsiz=n;
    getroot(1,0);
    ans[Root]=now;
    DFS(Root);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
}

321C

introductory econometrics 2100 5900