Description

Link.

起床困难综合症 上树。

Solution

线段树维护，树剖上树。

具体题解有空再写，我要去睡觉了。

#include<bits/stdc++.h>
typedef unsigned long long ULL;
struct node {
    ULL one,zero;
    node(ULL A=0,ULL B=0) {
        one=A;
        zero=B;
    }
}nodes[400010],exnodes[400010],res,exres;
ULL poi[100010],opz;
int k,dep[100010],son[100010],hb[100010],fa[100010],dfn[100010],sjc,op[100010],n,m,rev[100010],siz[100010];
int head[100010],nxt[200010],to[200010],cntot,opt,opx,opy;
bool flag,exflag;
void addEdge(int one,int ano) {
    to[++cntot]=ano;
    nxt[cntot]=head[one];
    head[one]=cntot;
}
node merge(node one,node ano) {
    node res(~0ull);
    ULL tmp=one.one,extmp=~tmp;
    res.one=(tmp&ano.one)|(extmp&ano.zero);
    tmp=one.zero;
    extmp=~tmp;
    res.zero=(tmp&ano.one)|(extmp&ano.zero);
    return res;
}
void adj(ULL &x,ULL y,int id) {
    if(id==1) {
        x&=y;
    } else if(id==2) {
        x|=y;
    } else {
        x^=y;
    }
}
void build(int l,int r,int x) {
    if(l^r) {
        int mid=(l+r)>>1;
        build(l,mid,x<<1);
        build(mid+1,r,x<<1|1);
        nodes[x]=merge(nodes[x<<1],nodes[x<<1|1]);
        exnodes[x]=merge(exnodes[x<<1|1],exnodes[x<<1]);
    } else {
        nodes[x]=exnodes[x]=node(~0ull);
        adj(nodes[x].one,poi[rev[l]],op[rev[l]]);
        adj(nodes[x].zero,poi[rev[l]],op[rev[l]]);
        adj(exnodes[x].one,poi[rev[l]],op[rev[l]]);
        adj(exnodes[x].zero,poi[rev[l]],op[rev[l]]);
    }
}
void ins(int l,int r,int x,int pos,int aj,ULL val) {
    if(l^r) {
        int mid=(l+r)>>1;
        if(mid>=pos) {
            ins(l,mid,x<<1,pos,aj,val);
        } else {
            ins(mid+1,r,x<<1|1,pos,aj,val);
        }
        nodes[x]=merge(nodes[x<<1],nodes[x<<1|1]);
        exnodes[x]=merge(exnodes[x<<1|1],exnodes[x<<1]);
    } else {
        op[rev[l]]=aj;
        poi[rev[l]]=val;
        nodes[x]=exnodes[x]=node(~0ull);
        adj(nodes[x].one,poi[rev[l]],op[rev[l]]);
        adj(nodes[x].zero,poi[rev[l]],op[rev[l]]);
        adj(exnodes[x].one,poi[rev[l]],op[rev[l]]);
        adj(exnodes[x].zero,poi[rev[l]],op[rev[l]]);
    }
}
void find(int l,int r,int x,int fr,int ba) {
    if(l>ba || r<fr) {
        return;
    } else {
        if(l>=fr && r<=ba) {
            if(!flag) {
                res=nodes[x];
                flag=true;
            } else {
                res=merge(nodes[x],res);
            }
        } else {
            int mid=(l+r)>>1;
            find(mid+1,r,x<<1|1,fr,ba);
            find(l,mid,x<<1,fr,ba);
        }
    }
}
void exfind(int l,int r,int x,int fr,int ba) {
    if(l>ba || r<fr) {
        return;
    } else {
        if(l>=fr && r<=ba) {
            if(!exflag) {
                exres=exnodes[x];
                exflag=true;
            } else {
                exres=merge(exres,exnodes[x]);
            }
        } else {
            int mid=(l+r)>>1;
            exfind(mid+1,r,x<<1|1,fr,ba);
            exfind(l,mid,x<<1,fr,ba);
        }
    }
}
node LCA(int x,int y) {
    flag=exflag=false;
    res=exres=node(~0ull);
    while(hb[x]^hb[y]) {
        if(dep[hb[x]]>dep[hb[y]]) {
            exfind(1,n,1,dfn[hb[x]],dfn[x]);
            x=fa[hb[x]];
        } else {
            find(1,n,1,dfn[hb[y]],dfn[y]);
            y=fa[hb[y]];
        }
    }
    if(dep[x]<dep[y]) {
        find(1,n,1,dfn[x],dfn[y]);
    } else {
        exfind(1,n,1,dfn[y],dfn[x]);
    }
    return merge(exres,res);
}
void dfs1(int x,int las) {
    dep[x]=dep[las]+1;
    fa[x]=las;
    siz[x]=1;
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if(y^las) {
            dfs1(y,x);
            siz[x]+=siz[y];
            if(siz[son[x]]<siz[y]) {
                son[x]=y;
            }
        }
    }
}
void dfs2(int x,int t) {
    hb[x]=t;
    dfn[x]=++sjc;
    rev[sjc]=x;
    if(son[x]) {
        dfs2(son[x],t);
        for(int i=head[x];i;i=nxt[i]) {
            int y=to[i];
            if((y^fa[x]) && (y^son[x])) {
                dfs2(y,y);
            }
        }
    }
}
ULL solve(node now,ULL lim) {
    ULL res=0,run=0;
    for(int i=k-1;~i;--i) {
        if(now.zero&(1ull<<i)) {
            res+=(1ull<<i);
        } else if((now.one&(1ull<<i)) && run+(1ull<<i)<=lim) {
            run+=(1ull<<i);
            res+=(1ull<<i);
        }
    } 
    return res;
}
char fgc() {
    static char buf[1<<21],*p=buf,*q=buf;
    return p==q && (q=buf+fread(p=buf,1,1<<21,stdin),p==q)?EOF:*p++;
}
template<typename T>
void read(T &hhh) {
    T x=0;
    int f=0;
    char c=fgc();
    while(c<'0' || c>'9') {
        if(c=='-') {
            f=1;
        }
        c=fgc();
    }
    while(c>='0' && c<='9') {
        x=(x<<3)+(x<<1)+(c^'0');
        c=fgc();
    }
    if(f) {
        hhh=-x;
    } else {
        hhh=x;
    }
}
int wrstk[100];
template<typename T>
void write(T x,char las='\n') {
    int top=0,f=0;
    if(x<0) {
        x=-x;
        f=1;
    }
    do {
        wrstk[++top]=x%10;
        x/=10;
    } while(x);
    if(f) {
        putchar('-');
    }
    while(top) {
        putchar(wrstk[top--]^'0');
    }
    putchar(las);
}
int main() {
    read(n);
    read(m);
    read(k);
    for(int i=1;i<=n;++i) {
        read(op[i]);
        read(poi[i]);
    }
    for(int i=1,x,y;i<n;++i) {
        read(x);
        read(y);
        addEdge(x,y);
        addEdge(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);
    while(m-->0) {
        read(opt);
        read(opx);
        read(opy);
        read(opz);
        if(opt==1) {
            if(k) {
                write(solve(LCA(opx,opy),opz));
            } else {
                write(0);
            }
        } else {
            ins(1,n,1,dfn[opx],opy,opz);
        }
    }
    return 0;
}

本文差不多算是翻译了一遍 CF blog?id=45223 就是抄了一遍，看不懂可以去原文。

当然我的翻译并不是完全遵从原文的。

Part. 1 Introduction

平时我们怎么求高维前缀和？容斥对吧，复杂度多少？$\mathcal{O}(n^{d}\times2^{d})$（$n$ 每维元素个数，默认同阶，$d$ 维度）。

这好吗？这不好。

Part. 2 Ying Wen

For 个 example，二维，容斥这么写对吧？

for(int i=1;i<=n;i++)
{
  for(int j=1;j<=n;j++)  f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
}

事实上我们还可以分维来前缀和：

for(int i=1;i<=n;i++)
{
  for(int j=1;j<=n;j++)  f[i][j]=f[i-1][j]+a[i][j];
}
for(int i=1;i<=n;i++)
{
  for(int j=1;j<=n;++j)  f[i][j]=f[i][j-1]+a[i][j];;
}

复杂度多少？$\mathcal{O}(n^{d}\times d)$，厉害吧。

对应到 SOS DP（sum over subsets），我们把每一维整到集合上去来求子集和。

形式化地定义子集和，即给定一个有 $2^{n}$ 个元素的数组 $A$，定义函数：

$$ \text{sub-sum}(mask)=\sum_{i\subseteq mask}A_{i} $$

写成位运算的形式：

$$ \text{sub-sum}(mask)=\sum_{mask\text{ & }i=i}A_{i} $$

学过 FWT 的巨佬可能发现了什么，可是这和我没关系。

看不懂？没关系，我们有严谨的代码定义：

for(int mask = 0;mask < (1<<N); ++mask){
    for(int i = 0;i < (1<<N); ++i){
        if((mask&i) == i){
            F[mask] += A[i];
        }
    }
}

这是什么垃圾复杂度，用高维前缀和可得以下代码：

for (int j = 0; j < n; ++j) {
  for (int i = 0; i < (1 << n); ++i) {
    if((i >> j) & 1)  f[i] += f[i ^ (1 << j)];
  }
}

Description

Link.

给出一个带权无向图，边权为 $2^{a}\cdot3^{b}$ 形式。

给出 $q$ 组形如 $u,v,a,b$ 的询问，问 $u,v$ 中是否存在一条路径使得其边权之 $\text{lcm}$ 为 $2^{a}\cdot3^{b}$。

Solution

考虑 $\text{lcm}$ 的本质，对 $n$ 个数 $\prod_{i=1}^{k_{1}}p_{1,i}^{c_{1,i}},\prod_{i=1}^{k_{2}}p_{2,i}^{c_{2,i}},\dots,\prod_{i=1}^{k_{n}}p_{n,i}^{c_{n,i}}$ 取 $\text{lcm}$ 就是 $\prod_{i=1}^{\max\{k\}}p_{i}^{\max\{c\}}$（在一个数中存在的 $p$ 且在另一个中不存在的置为 $1$），对于这题即 $2^{\max\{a\}}\cdot 3^{\max\{b\}}$，让两个 $\max$ 分别等于题目给出的 $a,b$。

现在转化一下题意，在 $u,v$ 中选出一条可非简单路径使得 $\max\{a\},\max\{b\}$ 分别等于给出的 $a,b$。

有一个 naive 的想法是缩点后 LCT 维护结果发现不太行。（好像是我不行）

既然想到了用 LCT 维护连通性那么同样可以想到用 DSU 来维护，把所有满足条件的边放入一个 DSU 然后看 $u,v$ 是否能被这些边联通。

有两个关键字欸，我们离线询问排序吧。

把所有边按照 $a$ 排序，把询问按 $b$ 排序。

然后对边的标号分块，这样块内边 $a$ 有序。

然后把每个询问放在满足前面块的 $a$ 都小于等于这个询问的 $a$ 的块里，并且把块内询问 $b$ 排序，然后就可以做了。

代码狼 BH 今天又口胡题解没代码了。

Oops, something went wrong.

Description

Link.

一年一度的综艺节目《中国新代码》又开始了。Zayid 从小就梦想成为一名程序员，他觉得这是一个展示自己的舞台，于是他毫不犹豫地报名了。

轻车熟路的 Zayid 顺利地通过了海选，接下来的环节是导师盲选，这一阶段的规则是这样的：
总共 $n$ 名参赛选手（编号从 $1$ 至 $n$）每人写出一份代码并介绍自己的梦想。接着由所有导师对这些选手进行排名。为了避免后续的麻烦，规定不存在排名并列的情况。

同时，每名选手都将独立地填写一份志愿表，来对总共 $m$ 位导师（编号从 $1$ 至 $m$）作出评价。志愿表上包含了共 $m$ 档志愿。对于每一档志愿，选手被允许填写最多 $C$ 位导师，每位导师最多被每位选手填写一次（放弃某些导师也是被允许的）。

在双方的工作都完成后，进行录取工作。每位导师都有自己战队的人数上限，这意味着可能有部分选手的较高志愿、甚至是全部志愿无法得到满足。

节目组对 ‘‘前 $i$ 名的录取结果最优’’ 作出如下定义：

• 前 $1$ 名的录取结果最优，当且仅当第 $1$ 名被其最高非空志愿录取（特别地，如果第 $1$ 名没有填写志愿表，那么该选手出局）。
• 前 $i$ 名的录取结果最优，当且仅当在前 $i − 1$ 名的录取结果最优的情况下：第 $i$ 名被其理论可能的最高志愿录取（特别地，如果第 $i$ 名没有填写志愿表、或其所有志愿中的导师战队均已员，那么该选手出局）。

如果一种方案满足 ‘‘前 $n$ 名的录取结果最优’’，那么我们可以简称这种方案是最优的。

举例而言，$2$ 位导师 T 老师、F 老师的战队人数上限分别都是 $1$ 人；$2$ 位选手 Zayid、DuckD 分列第 $1$、$2$ 名。那么下面 $3$ 种志愿表及其对应的最优录取结果如表中所示：

可以证明，对于上面的志愿表，对应的方案都是唯一的最优录取结果。
每个人都有一个自己的理想值 $s_i$，表示第 $i$ 位同学希望自己被第 $s_i$ 或更高的志愿录
取，如果没有，那么他就会非常沮丧。
现在，所有选手的志愿表和排名都已公示。巧合的是，每位选手的排名都恰好与它
们的编号相同。
对于每一位选手，Zayid 都想知道下面两个问题的答案：

• 在最优的录取方案中，他会被第几志愿录取。
• 在其他选手相对排名不变的情况下，至少上升多少名才能使得他不沮丧。
  作为《中国新代码》的实力派代码手，Zayid 当然轻松地解决了这个问题。不过他
  还是想请你再算一遍，来检验自己计算的正确性。

你可能注意到了根本没有概括因为太 tm 长了妈妈我不想概括

Solution

这份题面真难读。

对于第一问，网络流;

我们把学生和导师分别放到左右两列弄成一个二分图.

源点连容量为 $1$ 的学生边，然后让第一个学生连第一志愿，容量为 $1$，如果能流量有增就下一个，否则删除这条边下一个；

导师往汇点连人数限制的边。

对于第二问，同样网络流。

每个学生二分其最终排名，若学生 $x$ 的最终排名为 $k$，就用第一问的条件把 $x-k-1$ 名学生的边连上看是否满流。

#include<bits/stdc++.h>
const int INF=1e9;
std::queue<int> q;
std::vector<int> a[210][210];
int n,m,head[90010],nxt[180010],to[180010],cap[180010],Cur[900010],dep[900010],src,snk,cntot=1,up[210],s[210],ans[210];
void addEdge(int one,int ano,int val)
{
    to[++cntot]=ano;
    cap[cntot]=val;
    nxt[cntot]=head[one];
    head[one]=cntot;
    
    to[++cntot]=one;
    cap[cntot]=0;
    nxt[cntot]=head[ano];
    head[ano]=cntot;
}
bool MF_bfs()
{
    for(int i=1;i<=n+m+2;++i)
    {
        Cur[i]=head[i];
        dep[i]=INF;
    }
    q.push(src);
    dep[src]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=nxt[i])
        {
            int y=to[i];
            if(cap[i] && dep[y]==INF)
            {
                dep[y]=dep[now]+1;
                q.push(y);
            }
        }
    }
    return dep[snk]^INF;
}
int MF_dfs(int x,int in)
{
    if(x==snk)    return in;
    else
    {
        int out=0;
        for(int &i=Cur[x];i;i=nxt[i])
        {
            int y=to[i];
            if(cap[i] && dep[y]==dep[x]+1)
            {
                int tmp=MF_dfs(y,std::min(in,cap[i]));
                cap[i]-=tmp;
                cap[i^1]+=tmp;
                in-=tmp;
                out+=tmp;
                if(!in)    break;
            }
        }
        if(!out)    dep[x]=INF;
        return out;
    }
}
int Dinic()
{
    int res=0;
    while(MF_bfs())    res+=MF_dfs(src,INF);
    return res;
}
bool check(int x,int all)
{
    cntot=1;
    for(int i=1;i<=n+m+2;++i)    head[i]=0;
    addEdge(src,x,1);
    for(int i=1;i<=m;++i)    addEdge(n+i,snk,up[i]);
    int low=0;
    for(int i=1;i<all;++i)
    {
        addEdge(src,i,1);
        if(ans[i])
        {
            for(int now:a[i][ans[i]])    addEdge(i,n+now,1);
        }
        else    ++low;
    }
    for(int i=1;i<=s[x];++i)
    {
        for(int now:a[x][i])    addEdge(x,now+n,1);
    }
    return low+Dinic()==all;
}
int search(int l,int r)
{
    int res=r+1,ID=r+1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(ID,ID-mid))
        {
            res=mid;
            r=mid-1;
        }
        else    l=mid+1;
    }
    return res;
}
void Go()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)    scanf("%d",&up[i]);
    for(int i=1;i<=n;++i)
    {
        for(int j=1,x;j<=m;++j)
        {
            scanf("%d",&x);
            if(x)    a[i][x].emplace_back(j);
        }
    }
    for(int i=1;i<=n;++i)    scanf("%d",&s[i]);
    
    src=n+m+1;
    snk=n+m+2;
    for(int i=1;i<=m;++i)    addEdge(n+i,snk,up[i]);
    for(int i=1;i<=n;++i)
    {
        addEdge(src,i,1);
        for(int j=1;j<=m;++j)
        {
            if(!a[i][j].empty())
            {
                for(int now:a[i][j])    addEdge(i,now+n,1);
                if(MF_bfs())
                {
                    int waste=MF_dfs(src,INF);
                    ans[i]=j;
                    break;
                }
                else
                {
                    int cur=cntot;
                    for(int k=1;k<=int(a[i][j].size());++k)
                    {
                        cap[cur]=cap[cur^1]=0;
                        cur-=2;
                    }
                }
            }
        }
    }
    
    for(int i=1;i<=n;++i)
    {
        if(ans[i])    printf("%d ",ans[i]);
        else    printf("%d ",m+1);
    }
    printf("\n");
    
    for(int i=1;i<=n;++i)
    {
        if(ans[i] && ans[i]<=s[i])    printf("0 ");
        else    printf("%d ",search(1,i-1));
    }
    printf("\n");
    
    for(int i=1;i<=n+m+2;++i)    head[i]=0;
    for(int i=1;i<=n;++i)    ans[i]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)    a[i][j].clear();
    }
    cntot=1;
}
int main()
{
    int T,waste;
    scanf("%d %d",&T,&waste);
    while(T-->0)    Go();
    return 0;
}

Description

Link.

给定一个升序序列，问是否存在一种方法使得这个升序序列构成一棵 BST 并使一边相连的两点点权互质。

Solution

根据 BST 的性质可知对于一棵以 $u$ 为根的子树 $\text{subtree}(u)$ 对应原序列中的一段区间，于是对于一个区间 $[l,r]$，如果我们选取 $k$ 作为根，那么 $\text{subtree}(u)$ 的形态就固定下来了。

设 $f(i,j,k)$ 为区间 $[i,j]$ 中以 $k$ 为根是否能够构成一棵 BST。

这不好，这很差，考虑怎么优化。

观察发现 $[l,r]$ 的父亲结点一定是 $l-1$ 或 $r+1$，于是重新设 $f(i,j,0\text{ or }1)$ 表示区间 $[i,j-1]$ 的父结点为 $j$ 是否合法 / 区间 $[i+1,j]$ 的父结点为 $i$ 是否合法。

转移即：

$$ f(i-1,j,1)=f(i-1,j,1)\vee f(i,k,0)\wedge f(k,j,1)\wedge(\gcd(a_{i-1},a_{k})\neq1) \\ f(i,j+1,0)=f(i,j+1,0)\vee f(i,k,0)\wedge f(k,j,1)\wedge(\gcd(a_{j+1},a_{k})\neq1) $$

$k$ 是区间 DP 的中间点。于是就可以做了，边界与答案显然。

#include<bits/stdc++.h>
#define f(i,j,k) (f[i][j][k])
int n,a[710];
bool f[710][710][2],flag[710][710];
int GCD(int one,int ano)
{
    if(ano==0)    return one;
    else    return GCD(ano,one%ano);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)    scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)    f(i,i,1)=f(i,i,0)=1;
    for(int i=1;i<=n;++i)
    {
        flag[i][0]=1;
        for(int j=i;j<=n;++j)
        {
            flag[i][j]=flag[j][i]=(GCD(a[i],a[j])!=1);
            flag[0][j]=1;
        }
    }
    for(int i=n;i;--i)
    {
        for(int j=i;j<=n;++j)
        {
            for(int k=i;k<=j;++k)
            {
                f(i-1,j,1)|=(f(i,k,0)&f(k,j,1)&flag[i-1][k]);
                f(i,j+1,0)|=(f(i,k,0)&f(k,j,1)&flag[j+1][k]);
            }
        }
    }
    printf((f(1,n,0)|f(1,n,1))?"Yes\n":"No\n");
    return 0;
}