hehe
2024 北京市大学生程序设计竞赛 - Dashboard - Contest - QOJ.ac
E
呵呵这题，其实是多项式乘法前缀和过后要求一个内积，但是求内积的那个向量，也就是\(b\)，其实是固定的，所以把\(b\)翻转过后也乘进去，就可以把内积转化成求单点，就可以每个询问\(O(m)\)回答。
F
先求一个数组\(b\)，\(b_i=\max_{j,l_j\le i\le r_j}v_j\)，也就是每个位置的最小值，如果没限制这个位置就不用管，跟答案无关。每个\(a_i\)至少要有\(b_i\)，如果\(a_i<b_i\)那直接先花一些次数让\(a_i=b_i\)再继续，这之后每个位置都\(a_i\ge b_i\)了。注意到如果打算改变一个要让\(a_i\)改变，一定是把他变小为\(b_i\)，否则没有起任何作用。因此，对于\(b_i\)的每个值\(v\)限制是独立的，直接拆开解决。拆开之后的每个独立问题形如：有一些限制\((l_i,r_i)\)，表示\(l_i\)到\(r_i\)之间至少选一个；有一些选择\((p,val_p)\)，表示选择\(p\)这个位置代价是\(val_p\)。这个可以去除覆盖区间之后单调队列dp解决。
然后判断无解，如果数组\(b\)都不能满足所有限制就无解。
G
放到trie树上考虑，一个位为1的作用是交换改层所有左右儿子，如果某一层没有点有2个儿子，那一位显然不影响，如果某个点有2个儿子l,r，考虑取出l中当前最大的值询问，如果询问得到的点在r内则说明该位为0。有2种枚举方式，从高位到低位与从低位到高位，注意到从高位到低位不能找出l中的最大值，所以需要从低位到高位枚举。
主要是放到trie树上，在trie树上考虑影响，不要直接对着数字考虑。