В данной задаче требовалось построить минимальное остовное дерево на графе специального вида: в нем может быть слишком большое количество неявно заданных ребер, однако эти ребра следуют определенным правилам из условия: из вершины $$$n + i$$$ ребра одинакового веса ведут в вершины с $$$l_i$$$ по $$$r_i$$$.
Поскольку на таком графе может быть порядка $$$nq$$$ ребер, просто построить этот граф в явном виде не получится. Но посмотрим, как будет вести себя алгоритм Краскала, если такой граф все же построить:
Поэтому сначала отсортируем все данные в условия описания ребер по возрастанию $$$c_i$$$. А затем будем выполнять шаги из алгоритма Краскала, но оптимизированным образом.
Более того, итоговый граф будет связен тогда и только тогда, когда для любого $$$j$$$ от $$$1$$$ до $$$n - 1$$$ вершины $$$j$$$ и $$$j + 1$$$ находятся в одной компоненте связности. Поэтому мы свели всю задачу к проверке связности соседних из первых $$$n$$$ вершин.
А для этого достаточно поддерживать множество всех несвязных соседних вершин, и при обработке всех требуемых ребер с помощью бинпоиска в этом множестве находить все несвязанные пары из отрезка $$$[l_i, r_i]$$$ и удалять их. В сумме такое решение работает за $$$\mathcal{O}((n + q) \log n)$$$.