E. Spanning Tree Queries
codeforces.com/contest/1633/problem/E
一道离大谱的题;
题意:1e7次询问,每次询问给定一个数x;求一张n<=50;m<=300;wi_present=abs(wi-x)的图的MST的边权和.
分析:1e7次询问,那么单次询问的解决的时间复杂度应该为O(1)或者O(log);首先求MST的两个常用算法里先想到了kruskal,即对边排序然后维护并查集实现;那么对个x实际上只要求出相应的排序即可通过kruskal求得MST.但是如果对每个值都求一遍肯定要t掉;考虑到在某一个区间里;排序其实并不变;所以实际上可以通过对一个一个区间的处理来降低复杂度;而怎么样的点为区分两个区间的点呢?对两个数字而言,即为[-inf,(m1+m2)/2],[(m1+m2)/2+1,inf];如此便可想到对m条边可先对(ma+mj)/2+1进行排序;然后再对每次询问的x在这个新数组上二分答案得到他应该被归类到的MST排序进而求出值(到这就倒了
而我们求的不是MST的排序,是MST的值!!!所以考虑在同一个区间,x+1;则ans=num1-num2(x左边的数都++;右边的数都--)而对于排好序后在同一个区间的x,我们只要处理的时候对ans进行如此+=(num1-num2)*(now_x-pre_x) (pre_x为同组第一个求到的x)即可;这时候又发现一个坑点;num1与num2的改变即使不改变排序但实际上也会对ans造成影响而num1与num2实为某一个数左边的数和右边的数;那么此时区分两个区间的点为原数组的每个mi;所以之前的对(ma+mj)/2+1进行排序时就应该同时也考虑每个mi;而最后的处理有挺多方式,顺着思路好想到的应该是二分答案找x所在的区间如此复杂度为O(m3logm+klogm)即可通过...