Кесіндіге қосу
Сізге \(n\) бос жиын \(S_1, S_2, \dots, S_n\) берілген. Екі түрлі сұрауды өңдеу қажет:
Сұрау түрі 1 l r x:
\(l\)-ден \(r\)-ге дейінгі (қоса алғанда) барлық жиындарға элемент \(x\)-ті қосу керек.
Басқаша айтқанда, әрбір \(i\) үшін \(l\)-ден \(r\)-ге дейін: \[S_i \leftarrow S_i \cup \{x\}.\]
Сұрау түрі 2 l r:
\([l, r]\) кесіндісіндегі барлық жиындардың қиылысу мөлшерін есептеу қажет: \[\left|\bigcap_{i=l}^{r} S_i\right|.\]
\([l, r]\) кесіндісіндегі барлық жиындардың бірігу мөлшерін есептеу қажет: \[\left|\bigcup_{i=l}^{r} S_i\right|.\]
Осылайша, екінші түрдегі әрбір сұрау үшін екі санды шығару қажет: \[\left|\bigcap_{i=l}^{r} S_i\right| \quad \text{және} \quad \left|\bigcup_{i=l}^{r} S_i\right|.\]
Енгізу
Бірінші жолда екі бүтін сан \(n\) және \(q\) (\(1 \le n, q \le 100\,000\)) берілген — жиындардың саны және сұраулардың саны сәйкесінше. Келесі \(q\) жолында сұраулар сипатталған. Әрбір сұрау бір бүтін саннан \(t\) басталады:
Егер \(t = 1\), онда одан кейін үш бүтін сан \(l\), \(r\), \(x\) беріледі, мұнда \(1 \le l \le r \le n\) және \(1 \le x \le n\).
Егер \(t = 2\), онда одан кейін екі бүтін сан \(l\), \(r\) беріледі, мұнда \(1 \le l \le r \le n\).
Шығару
Әрбір сұрау үшін екі санды шығарыңыз — қиылысу мөлшері және кесіндідегі барлық жиындардың бірігу мөлшері.
Мысалдар
Енгізу 1
3 6
1 1 2 1
1 2 3 2
2 1 3
2 1 2
1 1 3 3
2 1 3
Жауап 1
0 2
1 2
1 3
Пікірлер