Wuyanru's blog
0%

[WC2021] 括号路径

发表于 分类于 ，

额，神奇题目，不会

题目链接

题意

有一张 个点和 条边的图，现在还有 种括号，这张图的每一条边都有一种括号的一部分（左括号或右括号）。

特别地，若边 有一个 类型的左括号，那么 就有一个 类型的右括号，反之亦然。

现在称一条路径合法，当且仅当这条路径上的括号连起来，是一个合法的括号序列。

求有多少对有序点对 满足存在一条从 到 的合法路径。

。

。

题解

首先我们可以发现一些性质：

  1. 若 合法， 合法，那么 也合法。

    显然，因为两个合法括号序列拼起来也合法

  2. 合法。

    显然，空串合法。

  3. 若 合法， 也合法。

    显然，倒着走回去就好了。

这些性质是很有用的。

先来看性质 ，这告诉我们，所有的合法点对一定形成了若干个团，所以可以考虑维护这些团。

如果维护团的话，我们需要考虑的括号序列，就只有形如 这种的了，因为 这种可以通过团得到。

考虑 这种合法的序列何时出现，我们只需要找到一条 的路径，满足 和 是同样的左右括号，且 在同一个团内，我们就可以将 所在的团合并起来。

考虑使用线段树维护，每一个团的所有种括号的入度（左括号那条边），一旦出现某种括号有大于等于两个入度，就可以将他们所在的团（使用线段树合并）合并起来。

这样合并出来的所有团一定都是合法的。

那么可不可能出现答案算少的情况呢？

其实是不会的，我们可以定义一个括号串的函数 。

若括号串 ，我们定义 。

否则括号串 ，我们定义 。

那么，只需要 的所有串被统计到了一个团里，那么他就能统计到 这样的括号串。

所有 且 的所有串统计好了，所有 且 的串自然就到了一个团里。

那么 的所有串就被统计了出来。

而一开始我们有 的所有串，我们就可以统计到所有的答案。

所以我们的答案既不会算多也不会算少。

时间复杂度是 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int num[12000001];
int ls[12000001];
int rs[12000001];
int root[300001];
int siz[300001];
int fa[300001];
queue<pi>que;
int n,m,k;
int cnt;
ll ans;
inline int find(int num)
{
    if(fa[num]==num) return num;
    return fa[num]=find(fa[num]);
}
void ins(int &p,int pl,int pr,int x,int y)
{
    if(!p) p=++cnt;
    if(pl==pr)
    {
        if(num[p]) que.push(pi(num[p],y));
        num[p]=y;return ;
    }
    int mid=(pl+pr)>>1;
    if(x<=mid) ins(ls[p],pl,mid,x,y);
    else ins(rs[p],mid+1,pr,x,y);
}
int merge(int u,int v,int pl,int pr)
{
    if(!u||!v) return u|v;
    if(pl==pr)
    {
        que.push(pi(num[u],num[v]));
        return u;
    }
    int mid=(pl+pr)>>1;
    ls[u]=merge(ls[u],ls[v],pl,mid);
    rs[u]=merge(rs[u],rs[v],mid+1,pr);
    return u;
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        ins(root[v],1,k,w,u);
    }
    while(!que.empty())
    {
        int u=que.front().first,v=que.front().second;
        que.pop(),u=find(u),v=find(v);
        if(u==v) continue;
        fa[v]=u,root[u]=merge(root[u],root[v],1,k);
    }
    for(int i=1;i<=n;i++)
    {
        int p=find(i);
        ans+=siz[p];
        siz[p]++;
    }
    printf("%lld\n",ans);
    return 0;
}

感谢观看！