Portal Description 给出一个\(1..n(n\leq5\times10^4)\)的排列\(\{a_n\}\)和数列\(\{w_n\}(w_i\leq10^5)\)，进行\(m(m\leq5\times10^4)\)次操作： 交换\(a_{p_1},a_{p_2}\)，并求\(\sum_{i=1}^n \sum_{j=i+1}^n [a_i>a_j](w_{a_i}+w_{a_j

Portal Description 给出一张\(n(n\leq30)\)个点\(m(m\leq100)\)条边的无向图。初始时有一个可乐机器人在点\(1\)，这个机器人每秒会做出以下三种行为之一：原地不动，走向相邻点，自爆（自爆后就不能动了）。求经过\(t(t\leq10^6)\)秒后可乐机器人的行动方案数。 Solution 矩阵乘法优化DP。 首先改一下原图：每个点向自己连一条自环；建立一

再也不作死写FhqTreap作内层树了，卡的不如暴力呜呜呜……  题意翻译：给一个序列，每个下标包含两个属性$a$和$v$，求第一个属性与下标形成的所有逆序对的第二个属性和，给出$m$个交换两个下标的操作，每次操作之后查询。 考虑一下交换之后会发生什么： 假设这次要交换$x$和$y$，使$x \leq y$。 发现交换之后$x, y$和$x$的左边的数和$y$右边的数构成的逆序对产生的贡献不变