题面

2019-05-04 13:06:11


序列 $(sequence.cpp/c/pas)$

题目背景

$dogcdt$ 虽然很喜欢做序列题,但她是一个不爱打麻将的女孩子。然而,因为所有国家队选手都需要精通雀魂,所以她必须去学习如何打麻将。
这天,她找到了在魂天神社的好朋友一姬、二阶堂美树和三上千织爽哥,让她来教 $dogcdt$ 如何打牌。
一姬给了 $dogcdt$ 一副改造之后的麻将,大概是这样的:
这副麻将有若干类牌,每类牌有 $1-9$ 的编号(参考正常麻将的万、索、筒),没有风牌、红宝牌。某一类中,每个编号的牌最多只有四张(参考正常麻将的万、索、筒)。
她们四人准备打一个半庄,但在东 $1$ 局的时候 $dogcdt$ 点了三个役满然后被飞了。
$dogcdt$ 感到很伤心,于是向一姬请教如何防守。
一姬指着她的牌河说:“你的切牌方式有问题的喵!”

题目描述

现在在 $dogcdt$ 面前有一棵 $n$ 个结点树,每个结点都有一张牌。一姬告诉她,这是魂天神社的守护神树,树上的某些链就代表了一种可能的优秀切牌方案。
为了简化任务,我们假定根节点是 $1$ 号结点,并且这是一个二人麻将。
一姬为了考验 $dogcdt$ 的防守能力,她要进行两种操作:
$0.$ 让她切牌。一姬会从神树里随便选一个结点,询问 $dogcdt$ 包含这个结点的所有安全的切牌序列的数量。除此之外,这个结点必须满足它是这个切牌序列所有点中深度最小的点
$1.$ 自己听牌立直一发门清自摸。一姬会选择一张牌(而不是一个结点),如果这张牌是安全的,那么它现在会变成危险的。否则则相反。一开始所有牌都是安全的
定义一个切牌序列是安全的,当且仅当这个长度为 $len$ 的序列满足:
$1.$ 这个序列在树上形成了一条链;
$2.$ 对于这个序列的第 $1$ 张牌和第 $len$ 张牌,需要满足第 $1$ 张牌的牌大小(具体见样例)小于第 $len$ 张牌,且第 $1$ 张牌的 $dfs$ 序也小于第 $len$ 张牌,同时他们必须是安全的
一姬告诉她,由于这棵树的绝好调,加上她要忙着吃饼干,所以 $dfs$ 序随便怎么指定都可以找到优秀的切牌序列。然后她就真的随机给定了一个 $dfs$ 序
现在一姬给出了 $q$ 个操作,需要 $dogcdt$ 与她进行一场试炼。但由于她给定的 $dfs$ 序是随机的,因此当她进行第零个操作时, $dogcdt$ 需要回答期望的安全切牌序列数
但 $dogcdt$ 觉得这是个沙雕题,于是她让你来解决这个问题,自己去看神社里的其它神仙雀士直播打牌放铳去了。

输入格式

第一行四个正整数,表示 $n,q$ 。
接下来 $n-1$ 行,每一行两个数字 $x,fa$ ,分别是这个结点上的牌和它的父亲。
接下来 $q$ 行,每行两个数 $opt,x$ 。对应的含义详见题目描述。

输出格式

对于每个询问一个数字,表示安全的切牌序列个数。

子任务

部分分:现实牌谱、暴力(含 $n=1$ )、 $h=1,q=1,opt=0,opt=1,O(n\sqrt n)$ 、筋牌随机、把种类分解成每个数字的正解被卡常、正解。
对于 $100\%$ 的数据, $n\le 10^5,q\le 10^5$ 。

后记

$dogcdt$ 通过练习,已经完全掌握了筋牌防守技巧。然后她点了一个四暗刻单骑,又双叒叕被飞了。
unkown:信筋的都是sazi

提示

注意,本题中提到的麻将相关术语不一定与现实中含义相同。因此即使你打过日麻,也请读清本题的题意
$dogcdt$ 博客:
$teafrogsf$ 博客:
雀魂官网:

尝试扩展

完全相同的两张牌给定相同筋牌的话,由于 $n$ 大小限制,可以将矩阵出得更大了。
然后这样读入过大的问题可以通过给定加密序列生成原牌河,就可以套莫队之类的算法解题。

题解

$opt=0$

考虑只有 $36$ 个 $LCA$ ,可以直接暴力枚举。
现在我们知道链的某一端点,需要求另一端点的方案数。
这个东西等价于第 $k$ 个点的子树中 $\ge$ 端点种类编号的点的个数,减去端点 $\to$ 这个点这条链倒数第二个点的子树中满足该条件的个数。直接套个数据结构维护即可。
至于列相同,直接离线暴力重新维护即可。

$opt=1$

把询问挂在对应的点上,可以在线段树合并时考虑种类编号 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。
然后边合并边计算,可以不重不漏地得到答案。
注意是不大于,所以要考虑自身对自身的贡献。






序列 $(sequence.cpp/c/pas)$

题目背景

$dogcdt$ 虽然很喜欢做序列题,但她是一个不爱打麻将的女孩子。然而,因为所有国家队选手都需要精通雀魂,所以她必须去学习如何打麻将。
这天,她找到了在魂天神社的好朋友一姬、二阶堂美树和三上千织爽哥,让她来教 $dogcdt$ 如何打牌。
一姬给了 $dogcdt$ 一副改造之后的麻将,大概是这样的:
这副麻将有 $n$ 类牌,每类牌有 $1-9$ 的编号(参考正常麻将的万、索、筒),没有风牌、红宝牌。某一类中,每个编号的牌最多只有四张(参考正常麻将的万、索、筒)。
她们四人准备打一个半庄,但在东 $1$ 局的时候 $dogcdt$ 点了三个役满然后被飞了。
$dogcdt$ 感到很伤心,于是向一姬请教如何防守。
一姬指着她的牌河说:“你的切牌方式有问题的喵!”

题目描述

现在在 $dogcdt$ 面前有一个 $w\times h$ 的牌河,每个位置都有一张牌。定义第 $1$ 行第 $1$ 列的这张牌坐标是 $(1,1)$ ,往下横坐标增大,往右纵坐标增大
为了简化任务,我们假定只有对家听牌了,其她两家都在摸鱼。一姬告诉她,在低分段局中信筋是很有必要的一种防止放铳的好手段,所以她给除了 $(1,1)$ 这个位置的牌之外的每张牌都指定了一张筋牌(注意这里给定的是坐标)。一姬告诉 $dogcdt$ ,由于她的绝好调魔法麻将,所以不存在一张牌的筋牌的筋牌 $\cdots\cdots$ 的筋牌是它本身(此处省略若干张筋牌)
由于一姬忙着吃饼干而疏忽,位置不同,但完全相同的两张牌给定的筋牌是可能不同的
定义一个切牌序列是安全的,当且仅当这个长度为 $len$ 的序列满足:
$1.$ 第 $i+1$ 张牌是第 $i$ 张牌的筋牌( $i<k$ 且 $i$ 为正整数),第 $j$ 张牌是第 $j+1$ 张牌的筋牌( $k\le j<len$ 且 $j$ 为正整数);
$2.$ 若对家立直,则第 $k$ 张牌与第 $1$ 张牌是同类型的牌,否则没有这个要求。注意 $k\in[1,len]$ ;
$3.$ 第 $len$ 张牌与第 $1$ 张牌在牌河的同一列,并且该牌不小于第 $1$ 张牌。此处大小的定义是种类编号的大小,而与牌编号的大小无关
现在一姬对牌河提出了 $q$ 个询问,每个询问给定 $dogcdt$ 一张绝对安全的牌(详见样例),同时给定对家的听牌情况,然后询问她在这样的限制之下,合法的切牌序列有多少种。
$dogcdt$ 觉得这是个沙雕题,于是她让你来解决这个问题,自己去看神社里的其它神仙雀士直播打牌放铳去了。

输入格式

第一行四个正整数,表示 $w,h,n,q$ 。
接下来一个 $w\times h$ 的矩阵,表示 $dogcdt$ 的牌河。为了方便,我们用数字表示每一张牌。其中 $1-9$ 表示第 $1$ 类牌, $10-18$ 表示第 $2$ 类牌,以此类推。保证数字最大值 $\le 9n$ 。
接下来一个 $w\times h$ 的矩阵,表示 $dogcdt$ 牌河中每张牌的筋牌。为了方便,我们用数字表示一个坐标。例如一个 $4\times 2$ 的矩阵中, $1$ 表示 $(1,1)$ , $7$ 表示 $(2,3)$ 。
接下来 $q$ 行,每行两个数 $opt,x,y$ 。
$opt=0$ 表示对家立直,一姬给 $dogcdt$ 第 $1$ 张牌,这张牌的坐标是 $(x,y)$ 。
$opt=1$ 表示对家默听(即不立直听牌),一姬给 $dogcdt$ 第 $k$ 张牌,这张牌的坐标是 $(x,y)$ 。

输出格式

一共 $q$ 行,每行一个数字,表示对于该询问,安全的切牌序列个数。

子任务

部分分:现实牌谱、暴力(含 $n=1$ )、 $h=1,q=1,opt=0,opt=1,O(n\sqrt n)$ 、筋牌随机、把种类分解成每个数字的正解被卡常、正解。 对于 $100\%$ 的数据, $h\le 50,w\times h\le 2\times 10^5,n\le 10^5,q\le 10^5$ 。

后记

$dogcdt$ 通过练习,已经完全掌握了筋牌防守技巧。然后她点了一个四暗刻单骑,又双叒叕被飞了。
unkown:信筋的都是sazi

提示

注意,本题中提到的麻将相关术语不一定与现实中含义相同。因此即使你打过日麻,也请读清本题的题意
$dogcdt$ 博客:
$teafrogsf$ 博客:
雀魂官网:

尝试扩展

完全相同的两张牌给定相同筋牌的话,由于 $n$ 大小限制,可以将矩阵出得更大了。
然后这样读入过大的问题可以通过给定加密序列生成原牌河,就可以套莫队之类的算法解题。

题解

$opt=0$

考虑只有 $36$ 个 $LCA$ ,可以直接暴力枚举。
现在我们知道链的某一端点,需要求另一端点的方案数。
这个东西等价于第 $k$ 个点的子树中 $\ge$ 端点种类编号的点的个数,减去端点 $\to$ 这个点这条链倒数第二个点的子树中满足该条件的个数。直接套个数据结构维护即可。
至于列相同,直接离线暴力重新维护即可。

$opt=1$

把询问挂在对应的点上,可以在线段树合并时考虑种类编号 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。
然后边合并边计算,可以不重不漏地得到答案。
注意是不大于,所以要考虑自身对自身的贡献。