首先这题比较重要的一点是要往暴力去想，因为我们发现\(m\)的值很小，而且这个操作是没有合并性的，即不能通过是否存在某个操作来判断全部成员的生存情况
我们先考虑一个比较暴力的做法，暴力枚举对于每个点\(u\)如果在\(t\)时刻死亡会影响哪些操作，对于操作我们暂时先暴力的\(O(n)\)枚举，容易发现这个复杂度是\(O(n^2m)\)，貌似比暴力还要差
我们考虑怎么优化，对于某一个\(u\)点若最终会死亡，则必然存在血量\(=1\)和\(=0\)的情况（废话），我设\(u\)点血量\(=1\)的时间为\([l_i,r_i]\)，我们发现如果在范围\([1,l_i]\)内我们对\(u\)点进行攻击，则显然\(t=r_i\)；而如果我们在\([l_i,r_i]\)的范围内进行攻击，则\(t\)就是他的攻击时间，对于所有以\(x\)作为攻击者的所有操作时间位于区间\([t,r_i]\)不会被记为贡献
这么做看起来貌似没有优化做法，但我们发现对于所有以\(x\)作为攻击者的所有操作时间位于区间\([t,r_i]\)中所有有用的操作最多只有\(3m\)个，因为一个人血量最多\(3\)条，所以我们可以把复杂度优化到\(O(nm^2)\)，复杂度和暴力同级
我们发现对于每一个点\(u\)，当\(t \in [l_i,r_i]\)时，我们会重复计算\([t,r_i],[t-1,r_i],[t-2,r_i]...\)的情况，于是我们对于每一个攻击者\(u\)，按时间倒序考虑所有情况，每次把某一个操作在之间的基础上操作，之前的操作要保存信息，可以做到复杂度\(O(m^3)\)
我们发现枚举\(u\)点是不是很好优化掉的，暴力递推同理，于是我们考虑怎么尽量少的暴力递推。我们发现如果钦定某一次操作\((x,y)\)失效，换言之在这次操作前让\(x\)死亡，那我们只需要影响这一个操作即可暴力递推，只需要在遇到这次操作后把\(x\)的生命值改成\(0\)即可(这里是我一开始不理解正解的原因)，这样我们对于每一个有效的操作，把这个操作去掉后暴力记录答案，最终乘上\(DreamXD\)选择的方案即可
最终复杂度\(O(nm)\)，因为有效的操作个数只有\(O(m)\)个
标签：MCOI,暴力,05,复杂度,对于,攻击者,操作,我们,P7568 From： https://www.cnblogs.com/fox-konata/p/17680738.html