P3792 Yuno, the Great Mother Archetype, and Idolatry

 Yuno recently had nothing to do and went to study "light patting" studies. It is an anime called Flip Flappers.  During her research, she came across something called the Great Mother archetype. The Great Mother is not only the tribal protector deity but also a mark for mutual recognition between tribes (later generalized into various graphic symbols, attire, and ritual practices). After tribal alliances emerged, the deity of a tribe with leadership rose to become the common deity of the entire alliance, and then the common deity of chiefdoms and kingdoms.  Basically, it says this figure is an idol from matriarchal society, symbolizing that the mother can create life and also destroy life, embodied as the Good Mother and the Terrible Mother—she nurtures all and also devours all. In myths we are familiar with, there are Great Mother figures; for example, Nüwa is essentially a Great Mother.  In the era of primitive tribes, the Great Mother not only had the ability to give birth and nurse but also possessed divine power to protect the tribe and bring abundant harvests. By the mythic age, the Great Mother further differentiated into a variety of goddesses, each symbolizing different aspects of feminine energy: goddess of birth, earth goddess, goddess of love and beauty, protective goddess, war goddess, harvest goddess, wisdom goddess, goddess of fate, and so on. These are the Good Mother aspects.  Things in the world are always dual: all life is born from the earth and ultimately returns to the earth; what creates also inherently has the power to destroy. The Great Mother likewise has a side of pain, terror, devouring, and danger. For example, the witch in fairy tales is actually an embodiment of the other side of the Great Mother, namely the Terrible Mother. The story of the gingerbread house tells of Hansel and Gretel being driven from home by their stepmother because there was no food, then entering the forest and finding a gingerbread house with a witch inside who eats children. However, if we think carefully about this story, we will find it is not so simple. For instance, does the witch really eat children? What if the witch is a kind old woman who freely rescues children trapped in the forest? And when Hansel and Gretel kill the witch and return home, they find that their stepmother has also died. Does that imply they actually killed their stepmother? So the essence of this story is that they killed their mother—defeating the Great Mother. Many myths include episodes of defeating the Great Mother.

 You may already think Yuno is not mentally normal by this point. However, Yuno has not been normal ever since she accidentally ## her own ##. Yuno studied the Great Mother archetype for a long time but is still completely confused. So she went off to make a data structure problem to farm points. Yuno: I give you a sequence; each query asks whether a subarray is a contiguous segment on the value range. zzy: Explain the problem statement in more detail. Yuno: It means there cannot be duplicate numbers. For example, 1 2 2 3 is not okay, but 4 2 3 1 is okay. yql: sb block decomposition. ddd: sb bitset. Yuno: Wow, you all love tree chains. I... I’ll support modifications. zzq: ####### sb problem. Yuno: I’m going to publish the original problem as is.  You are given a sequence $a$ of length $n$. There are two types of operations: 1. Update the value at position $x$ to $y$. 2. Query whether the subarray $[l, r]$ can be rearranged into a consecutive range of values. 

The first line contains two integers $n$ and $m$. The second line contains $n$ integers representing $a_i$. Each of the next $m$ lines contains three integers: either $opt$ $x$ $y$, or $opt$ $l$ $r$, representing an operation.

If it is possible, output "damushen". Otherwise, output "yuanxing".

- For $30\%$ of the testdata, $n, m \le 500$. - For $60\%$ of the testdata, $n, m \le 100000$. - For $100\%$ of the testdata, $n, m \le 500000$. The initial values have value range less than $2.5 \times 10^7$. In update operations, $y \le n$. At any time, all $a_i$ are guaranteed to be positive integers. Time limit: 2 s. Translated by ChatGPT 5