update:16.07.12

MMPROD

n 个数选择 k 个使得乘积最大

容易知道排序完乘积最大的方案肯定是某段前缀+某段后缀，然后转对数使得乘法变加法，多加一个变量来储存符号，枚举比较大小即可

FAIRPAIR

两组 n 个数，两两匹配，要使相同数匹配对数最小，并询问方案

暴力配对一发，然后对于一对相同数匹配，暴力枚举拆开其他哪对匹配能拆开来来合法交换

（或者变成匈牙利求最大匹配，然而总是 TLE）

LISLDS

构造长度为 n 的排列，使得其 LIS 和 LDS 为给定数值

构造题啊，那么我们可以将 n 分成 LDS 份，左边那份总比右边大，然后每份大小不超过 LIS，并且从小到大排序

MINSHIFT

给随机字符串，或者随机修改一个字符，或者将某个子串提出来询问最小表示法

随机字符串嘛，那我们算下，$26^4>10^5$，好极！我们就以 4 个字符为单位预处理，然后就区间询问最小值，再通过链表找到出发点，然后暴力比较大小，修改就维护上述信息

复杂度玄学（因为随机）

REGIONS

一棵树，问将每条边切断后剩余两棵树的直径

第一次 dfs 求出子树直径，第二次 dfs 求出边上子树的直径，然后维护下奇奇怪怪的信息，例如子树最深叶子、子树直径啊什么的

FURGRAPH

博弈游戏，双方轮流选点，最后得分为各自子图边权和，求最优策略下最后的分差；每次新加一条边并在线维护其最后分差

首先这类博弈游戏，我们可以将边权一分为二，分给点，然后点排序后分差就是奇偶位置的差，用Treap维护即可

SEAGCD2

给长度 n 和范围 [1,m]，问有多少不同的序列满足不同位的数互质，$M \le 100$

状压 (2,3,5,7) 的状态，然后直接枚举质因子计算即可

POLYEVAL

给多项式，求当 x=0..786432 的时候多项式模 786433 的值

观察模数，786433=2^18*3+1，NTT 可以求出 $x=g^3,g^6...$ 的值，然后用三进制 FFT 求出全部值

（这里只是用到了三进制 FFT 的蝴蝶操作合并而已）

TRAVTREE

弄棵树，每次往集合内加一条路径，每次加询问和集合内多少条路径相交

两种相交类型，就是新加路径的lca在多少条路径上，或者是有多少lca在新加的路径上，注意lca重合的路径会算两次

然后就链剖即可