题解 P7323 【[WC2021] 括号路径】

· · 题解

我们考虑合法的括号路径是怎样的形式？

对于一个合法的 初始空串，以两种形式来扩展得到一个合法括号序列：

以下，我们用三个参数 (x,y,z) 表示一条从 x 指向 y，代表种类为 z 的左括号的有向边。

用 p_{x,y} 表示 两点之间存在合法路径 这个命题的真假。

首先，很好证明，p_{x,y}\Rightarrow p_{y,x}。

然后根据第一种扩展，我们可以得到：p_{x,y},p_{y,z}\Rightarrow p_{x,z}。

根据这两个推导式，我们可以得知：当 p_{x,y} 为真时，我们可以将 x,y 合并为一个点，因为对于任意点 z，都有 p_{x,z}=p_{y,z}。

然后考虑我们如何得知一些关系为真。

这个时候就需要用到第二种扩展，考虑在一个合法串左右加上一个括号，实际在图上代表什么：

中间既然是一个合法串 \operatorname A，那么 \operatorname A 所代表的路径 z\to \cdots \to j，z,j 必定已经缩成了一个点。

假设 z,j 缩成的点编号为 y。

那么左右括号代表的边，分别就是 (x,y,\beta) 和 (z,y,\beta)。

此时就会增加一条合法路径 x\to \cdots \to z。

那么分析到这里，做法就已经出来了：对于边 (x,y,z)，我们可以把所有 y 相同且 z 相同的边，将它们的 x 合并成一个点，然后重新编号，继续判断。

简单的说，就是：

加边，加边，加边，然后并查集查询。

注意需要把重复的边删除，同时当某个 z 只有一条边的时候也可以删掉。

只要重复这个过程一直到不能继续合并为止，就好了。

至于答案的计算，只要拿每个联通块内部的大小计算两两点对数目即可。

安利一下自己的 WC 游记

然后附上我的考场代码，虽然能过，但是我分析不来它的复杂度。

但是只想打暴力就跑路，结果打了满分。不过我是场外选手

#include <stdio.h>
#include <algorithm>
#define LL long long
using namespace std;
inline LL rin()
{
    LL s=0;
    bool bj=false;
    char c=getchar();
    for(;(c>'9'||c<'0')&&c!='-';c=getchar());
    if(c=='-')bj=true,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^'0');
    if(bj)return -s;
    return s;
}

const int N=3e5+3;

int n,m,k;
int cuts;
struct zjj
{
    int f[N];
    inline void init(int n){for(int i=1;i<=n;i++)f[i]=i;return;}
    inline int find(int x){return f[x]==x?x:(f[x]=find(f[x]));}
    inline void add(int x,int y){f[find(x)]=find(y);return;}
    inline bool check(int x,int y){return find(x)==find(y);}
    inline void connect(int x,int y){if(!check(x,y))cuts++,add(x,y);return;}
}Alpha;

struct gyq
{
    int x,y,z;
    inline void Read(){x=rin();y=rin();z=rin();return;}
    inline void f5(){x=Alpha.find(x);y=Alpha.find(y);return;}
}a[N<<1];

gyq d[N<<1];
inline bool myru_a(gyq x,gyq y){return x.z==y.z?x.y<y.y:x.z<y.z;}

int cutt[N];
int main()
{
    // freopen("bracke.in","r",stdin);
    // freopen("bracket.out","w",stdout);
    n=rin();m=rin();k=rin();
    Alpha.init(n);
    for(int i=1;i<=m;i++)a[i].Read();
    sort(a+1,a+m+1,myru_a);
    for(;m;)
    {
        int nam=0,tail=0;
        cuts=0;
        for(int i=1,j;i<=m;i=j)
        {
            if(a[i].z!=a[i-1].z){if(tail>1)for(;tail;tail--)a[++nam]=d[tail];tail=0;}
            for(j=i+1;j<=m&&a[j].z==a[i].z&&a[j].y==a[i].y;j++)Alpha.connect(a[j-1].x,a[j].x);
            d[++tail]=a[i];
        }
        if(!cuts)break;
        if(tail>1)for(;tail;tail--)a[++nam]=d[tail];
        for(int i=1;i<=nam;i++)a[i].f5();
        for(int i=1,j;i<=nam;i=j)
        {
            for(j=i+1;j<=nam&&a[j].z==a[i].z;j++);
            sort(a+i,a+j,myru_a);
        }
        m=nam;
    }
    for(int i=1;i<=n;i++)cutt[Alpha.find(i)]++;

    LL ans=0;
    for(int i=1;i<=n;i++)ans+=1LL*(cutt[i]-1)*cutt[i]>>1;
    printf("%lld\n",ans);
    return 0;
}