题目翻译:给定 nnn 次操作,每次操作会给定三个正整数 Pi,Ai,BiP_i,A_i,B_iPi ,Ai ,Bi ,假设将要操作的数为 xxx,则:
* 如果 x≤Pix\le P_ix≤Pi ,则将 xxx 的值加上 AiA_iAi 。
* 如果 x>Pix\gt P_ix>Pi ,则将 xxx 的值减去 BiB_iBi 。
给定 qqq 次询问,每次询问给定一个正整数 XiX_iXi ,问经过这些操作后 XiX_iXi 的值为多少。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注意到 Pi,Ai,BiP_i,A_i,B_iPi ,Ai ,Bi 都很小,所以考虑从这里下手。
根据题意发现较大的 XiX_iXi 会一直执行减 BiB_iBi 的操作,所以考虑二分求出第一个使 Xi<500X_i\lt 500Xi <500 的操作的位置和经过这些操作后 XiX_iXi 的值。
然后我们枚举每个数在经过后面的若干次操作后最终变成什么,然后将 XiX_iXi 一个一个带入即可。注意经过操作后的数可能到达 100010001000,所以应该枚举到 100010001000。
时间复杂度:O(nV+qlogq)O(nV+q\log q)O(nV+qlogq),其中 V=1000V=1000V=1000。