A

B

C

有两种思路：

第一种思路：离线处理，利用多项式，构造函数f(x)=ax²+bx+c，只用保存a,b,c三个值，然后我们只要维护a,b,c三个系数，就能知道f(i)的值，碰到修改操作的时候只要修改a,b,c的值即可。

第二种思路：还是先离线，这次利用前缀和与差分数组的关系。我们知道区间加常数c可以先做差分，此时操作变为单点修改，然后使用前缀和还原。

区间加一次函数bx+c呢，则可以做二阶差分操作（先差分一次，再对差分数组做一次差分）这时区间加一次函数bx+c就变为了单点修改，然后做二阶前缀和（前缀和的前缀和）还原，然后这个题就做完了。

说点题外话，这个操作是可以扩展的。

k次多项式的k+1阶差分可以用k+1个常数来表示，并且这k+1个常数的和总是等于最高项系数乘以k的阶乘。这个性质我在之前的牛客练习赛中有出过题目：https://ac.nowcoder.com/acm/contest/308/F

（顺带一提这个题的1e9是毒瘤时津风多加的0）

D

E

有两种思路：

第一种是开两个multiset一个维护行坐标，一个维护列坐标。每次查询的时候开一个优先队列，暴力模拟到前k大即可。

第二种解法就是可持久化可并堆的板子题，因为这个板子比较冷门所以介绍一下。

可持久化可并堆支持的操作：

1、插入一个指定元素(时空复杂度：O(logn))

2、删除一个指定迭代器（时空复杂度：O(logn)）

3、查询堆顶元素（时空复杂度：O(1)）

4、合并两个堆,并且支持自己合并自己（时空复杂度：O(logn)）

5、将一个堆中的所有元素都加上或者减去一个数（时空复杂度：O(1)）

6、为一个堆新建一个副本，拷贝一个新堆（时空复杂度：O(1)）

7、回退到某个历史版本（时空复杂度：O(1)）

预处理：首先对a数组和b数组各做一个前缀堆操作，就是suma[1]所示的堆保存了a[1]一个元素，suma[2]所示堆中保存了a[1]、a[2]两个元素。

假设我们现在在x,y这个位置，那么我们向下走1步，会多哪些元素呢？我们需要把a[x+1]+b[1],a[x+1]+b[2],a[x+1]+b[3]….a[x+1]+b[y]这y个元素全部放入now这个堆中。有了堆合并，堆拷贝，堆中所有元素加数这三个操作，这个问题迎刃而解。

我们拿出之前预处理的b的前缀堆，也就是sumb[y]。sumb[y]中所储存的元素恰好就是b[1],b[2],b[3]…b[y]，然后拷贝这个堆做一个副本，再给它整体加上一个a[x+1]就得到了我们想要的堆，然后把做好的这个堆合并进now堆中即可。

向右走同理，这里就不再多废话了。

查询的时候先保存一下根节点信息，然后pop结束以后直接还原根节点信息就行，反正可持久化结构都支持的操作…不用我多说了吧。

F

先说不带修改操作，给你一堆数小于1000，求互质集数目。

首先是能注意到sqrt(1000)=31。对于一个小于1000的自然数，我们可以把它的质因子分成两类，第一类是大于31的大质因子，第二类是小于等于31的小质因子。

我们发现小于等于31的质数不多，一共有11个。所以我们把一个自然数的小质因子做一个状压。接下来按照大质因子分组做分组背包。背包的体积就是小质因子的状压状态。

这样由于我们把状压值作为了背包的体积使用，保证了小质因子互不相同。又由于大质因子作为分组背包分组的依据，同组之间没有转移。大小质因子全部互斥，就保证了放入的每个物品（数字）都是互质的。

然后修改其实没有什么花的，只涉及到了背包的逆操作。我们只要把分组背包的泛化物品整个取出来，修改这个泛化物品再放回去就好。

为了避免有人不清楚逆背包的操作，我在下面科普一下这个操作。

背包问题求方案数可用生成函数f(x) 表示，f(x)是一个关于x的多项式。

对于其中的某一项，w表示背包的体积，A表示方案数。

生成函数是一种计数原理，比如远古时代的结绳计数。那时候的人在绳子上打结来统计数目。这个生成函数中的x，它就是绳子上的结。它不代表任何含义，就是用来计数的工具。

比如说现在有个背包的生成函数为：f(x)=3x²+4x+1

这就表示构成体积为2的背包有3种不同的方案，构成体积为1的背包有4种不同的方案，构成体积为0的背包有1种方案。x有什么意义呢？x没意义，所谓“结绳计数”懂了吧。

这样做的好处在于，如果我的背包要放多个物品，我只要把这些物品所表示的多项式乘起来，就得到了最终背包的生成函数。

若要去掉某个物品的影响，就需要构造一个背包使得该背包的生成函数，则f(x)*g(x)=1，也就是可以消除01背包产生的影响。

体积为w，贡献（系数）为负的完全背包，其生成函数为

由于生成函数中多项式x的幂代表背包的体积，所以我们并不关心这一项到底代表什么，因为背包的体积是有限的，无限的项并不能影响有限。所以该项并不对答案提供任何贡献。

所以在该问题中等价。

所以对于统计方案数的背包，正贡献01背包和负贡献完全背包互为逆操作。正贡献完全背包和负贡献的01背包也互为逆操作。

其实对于各种各样的背包问题，你想找到它的逆背包，都可以使用，也就是对于一个背包问题，如果它可以用生成函数f(x)表示，如果你能找到一个多项式g(x)，使得g(x)*f(x)=1，则g(x)所表示的背包操作和原操作互逆。