题面

## 序列$(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]$的贡献。 然后边合并边计算，可以不重不漏地得到答案。 注意是不大于，所以要考虑自身对自身的贡献。