如果本题的$n$开大到$10^6$并且带点权，那又该如何做？

退役半年了，很多东西可能都搞得不是很清楚，欢迎各位大佬diss