「CF369E」Valera and Queries-线段树

有 $n$ 条线段,分别为 $[l_i,r_i]$ 。

有 $m$ 个询问,分别为 $cnt_i,p_1,p_2,…,p_{cnt_i}$

对于每个询问,输出有多少线段至少覆盖这 $cnt_i$ ​个点中的一个。($\sum cnt_i \le 3 \cdot 10^5$)

「NOI2012」魔幻棋盘-差分+树套树

将要读二年级的小 $Q$ 买了一款新型益智玩具——魔幻棋盘,它是一个 $N$ 行 $M$ 列的网格棋盘,每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列(行与列均从 $1$ 开始编号)并且始终不会移动。棋盘守护者会进行两种操作:

  1. 询问:他会以自己所在位置为基础,向四周随机扩展出一块大小不定的矩形区域,向你询问这一区域内所有数的最大公约数是多少。

  2. 修改:他会随意挑选棋盘上的一块矩形区域,将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友,当你连续答对 $19930324$ 次询问后会得到一个惊喜噢!”。小 $Q$ 十分想得到这个惊喜,于是每天都在玩这个玩具。但由于他粗心大意,经常算错数,难以达到这个目标。于是他来向你寻求帮助,希望你帮他写一个程序来回答棋盘守护者的询问,并保证 $100\%$ 的正确率。

为了简化问题,你的程序只需要完成棋盘守护者的 $T$ 次操作,并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62} - 1$ 的正整数。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×