2021icpc上海m

kruskal重构树套st表

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int st[200005][20],mx[200005][20],t;
int val[200005];
int fa[200005];
int n,m,q;
struct edge{
    int u,v,w;
    bool operator < (const edge &A) const{return w < A.w;}    
}e[100005];
const bool cmp (const edge &a,const edge &b)
{
    return a.w<b.w;
}
int get_f (int u)
{
    if (fa[u]!=u) fa[u]=get_f(fa[u]);
    return fa[u];
}
int qry (int ci,int cv)
{
    for (int i=19;i>=0;i--)
        if (st[ci][i] && cv>=mx[ci][i])
            ci=st[ci][i];        
    return cv+val[ci];
}
void ins (int u,int v,int w)
{
    if (u==v) return;
    t++;
    fa[u]=fa[v]=t;
    val[t]=val[u]+val[v];
    mx[u][0]=w-val[u];
    mx[v][0]=w-val[v];
    st[u][0]=st[v][0]=t;
}
void build_st()
{
    for (int i=1;i<20;i++)
        for (int j=1;j<t;j++)
            if (st[j][i-1])
            {
                st[j][i]=st[st[j][i-1]][i-1];
                mx[j][i]=max(mx[j][i-1],mx[st[j][i-1]][i-1]);                
            }        
}
int main()
{
    scanf("%d %d %d",&n,&m,&q);
    for (int i=1;i<=n;i++) scanf("%d",&val[i]);
    for (int i=1;i<=(n<<1);i++) fa[i]=i;
    for (int i=1;i<=m;i++) scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+m+1);
    t=n;
    for (int i=1;i<=m && t<(n<<1)-1;i++)
        ins(get_f(e[i].u),get_f(e[i].v),e[i].w);    
        
    build_st();
    
    while (q--)
    {
        int x,k;
        scanf("%d %d",&x,&k);
        printf("%d\n",qry(x,k));
    }
    return 0;
}

一开始还MLE了

研究半天发现

fa[++t]=t;

这种写法不是很合法

C/C++语言标准没有规定运算符的操作数的计算顺序，编译器可以按任意顺序来计算操作数的值，因此如果一个变量在同一个运算符的两个操作数分别被修改或一个修改一个读取，其结果在不同的编译器上可能不一样的。以后不要写这种代码，讨论也没有意义。

From https://en.cppreference.com/w/c/language/eval_order

下次不乱玩++了

错误示范：

#include<cstdio>
#include<algorithm>
using namespace std;
int st[200005][20],mx[200005][20],t;
int val[200005];
int fa[200005];
int n,m,q;
struct edge{
    int u,v,w;
}e[100005];
bool cmp (const edge &a,const edge &b)
{
    return a.w<b.w;
}
int get_f (int u)
{
    if (fa[u]!=u) fa[u]=get_f(fa[u]);
    return fa[u];
}
int qry (int ci,int cv)
{
    for (int i=19;i>=0;i--)
        if (st[ci][i] && cv>=mx[ci][i])
            ci=st[ci][i];        
    return cv+val[ci];
}
void ins (int u,int v,int w)
{
    if (u==v) return;
    fa[++t]=t;
    fa[u]=fa[v]=t;
    val[t]=val[u]+val[v];
    mx[u][0]=w-val[u];
    mx[v][0]=w-val[v];
    st[u][0]=st[v][0]=t;
}
void build_st()
{
    for (int i=1;i<20;i++)
        for (int j=1;j<t;j++)
            if (st[j][i-1])
            {
                st[j][i]=st[st[j][i-1]][i-1];
                mx[j][i]=max(mx[j][i-1],mx[st[j][i-1]][i-1]);                
            }
}
int main()
{
    scanf("%d %d %d",&n,&m,&q);
    for (int i=1;i<=n;i++) scanf("%d",&val[i]),fa[i]=i;
    for (int i=1;i<=m;i++) scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+n,cmp);
    t=n;
    for (int i=1;i<=m;i++)
        ins(get_f(e[i].u),get_f(e[i].v),e[i].w);
    build_st();    
    while (q--)
    {
        int x,k;
        scanf("%d %d",&x,&k);
        printf("%d\n",qry(x,k));
    }
    return 0;
}