题目描述给定一个长度为NNNN≤105N \le 10^5N≤105的整数序列每个整数都在[0,216−1][0, 2^{16} - 1][0,216−1]范围内。接下来有若干操作操作分为两类修改操作C delta将序列中的每一个数都增加delta\textit{delta}deltadelta≥0\textit{delta} \ge 0delta≥0若结果超过216−12^{16} - 1216−1则对2162^{16}216取模等价于只保留低161616位。查询操作Q i0≤i≤150 \le i \le 150≤i≤15询问当前序列中有多少个数的二进制第iii位为111即该数与2i2^i2i按位与的结果大于000。你需要输出所有查询答案的总和保证总和小于10,000,000,00010,000,000,00010,000,000,000。每组测试数据以一行单独的E结束之后跟随一个空行。输入以N−1N -1N−1结束。保证每组数据的操作总数不超过200,000200,000200,000。输入格式多组测试数据。每组数据第一行为整数NNN。接下来NNN行每行一个整数PPP0≤P≤216−10 \le P \le 2^{16} - 10≤P≤216−1表示序列的初始值。之后每行是以下两种格式之一C deltadelta≥0\textit{delta} \ge 0delta≥0修改操作Q i0≤i≤150 \le i \le 150≤i≤15查询操作。每组数据以一行E结束。N−1N -1N−1表示输入结束。输出格式对于每组数据输出一行Case X: Y其中XXX是测试用例编号从111开始YYY是所有查询答案的总和。样例输入3 1 2 4 Q 1 Q 2 C 1 Q 1 Q 2 E输出Case 1: 5题目分析本题的序列长度可达10510^5105操作总数可达2×1052 \times 10^52×105。如果每次查询都遍历整个序列时间复杂度为O(N⋅Q)O(N \cdot Q)O(N⋅Q)最坏情况下会达到2×10102 \times 10^{10}2×1010显然不可接受。注意到数值范围很小161616位即0∼655350 \sim 655350∼65535且所有修改操作都是对全体数统一增加同一个值取模2162^{16}216。因此我们可以利用全局偏移量来表示所有数的统一变化而不需要真的去修改每个数。对于每个查询位iii我们只需要知道在当前全局偏移量下有多少个数满足其第iii位为111。由于偏移量是全局统一的我们可以预先对每个位iii计算出所有可能的偏移量对应的答案查询时直接查表即可。解题思路值域与偏移设初始序列中数值vvv的出现次数为cnt[v]\textit{cnt}[v]cnt[v]。定义一个全局偏移量offset\textit{offset}offset则任意数的当前值可以表示为(初始值offset) mod 65536(\textit{初始值} \textit{offset}) \bmod 65536(初始值offset)mod65536。对于查询位iii一个数xxx的第iii位为111当且仅当x mod 2i1∈[2i,2i1−1]x \bmod 2^{i1} \in [2^i, 2^{i1} - 1]xmod2i1∈[2i,2i1−1]即在该模数下的后半段。因此对于固定的位iii设M2i1M 2^{i1}M2i1我们可以构造一个长度为MMM的数组A[r]A[r]A[r]表示初始序列中满足v mod Mrv \bmod M rvmodMr的数的个数。当全局偏移量为offset\textit{offset}offset时每个数的当前模MMM余数为(roffset) mod M(r \textit{offset}) \bmod M(roffset)modM。那么第iii位为111的数的数量就是ansi(shift)∑r0M−1A[r]⋅[(rshift) mod M∈[2i,M−1]] \text{ans}_i(\textit{shift}) \sum_{r 0}^{M-1} A[r] \cdot [ (r \textit{shift}) \bmod M \in [2^i, M-1] ]ansi​(shift)r0∑M−1​A[r]⋅[(rshift)modM∈[2i,M−1]]其中shiftoffset mod M\textit{shift} \textit{offset} \bmod MshiftoffsetmodM。上式等价于将数组AAA循环右移shift\textit{shift}shift位后区间[2i,M−1][2^i, M-1][2i,M−1]上的元素和。预处理因为iii只有161616个取值0∼150 \sim 150∼15且M2i1≤65536M 2^{i1} \le 65536M2i1≤65536我们可以对每个iii预处理出所有shift∈[0,M−1]\textit{shift} \in [0, M-1]shift∈[0,M−1]对应的答案存放到表ansTable[i][shift]\textit{ansTable}[i][\textit{shift}]ansTable[i][shift]中。预处理方法对每个iii构造数组AAA长度MMM然后计算循环前缀和对于每个shift\textit{shift}shift用前缀和快速求得区间[2i,M−1][2^i, M-1][2i,M−1]循环平移后的和。具体地将AAA复制一份接在后面得到长度为2M2M2M的序列然后计算前缀和则对于任意shift\textit{shift}shift区间起点为(2i−shift mod MM) mod M(2^i - \textit{shift} \bmod M M) \bmod M(2i−shiftmodMM)modM区间长度为2i2^i2i通过前缀和即可O(1)O(1)O(1)得到答案。预处理的总复杂度为∑i015O(2i1)O(217)≈1.3×105 \sum_{i0}^{15} O(2^{i1}) O(2^{17}) \approx 1.3 \times 10^5i0∑15​O(2i1)O(217)≈1.3×105这是完全可以接受的。处理操作维护一个全局变量offset\textit{offset}offset初始为000。遇到修改操作C deltaoffset(offsetdelta) mod 65536\textit{offset} (\textit{offset} \textit{delta}) \bmod 65536offset(offsetdelta)mod65536。遇到查询操作Q i令M2i1M 2^{i1}M2i1shiftoffset mod M\textit{shift} \textit{offset} \bmod MshiftoffsetmodM答案即为ansTable[i][shift]\textit{ansTable}[i][\textit{shift}]ansTable[i][shift]累加到总和中。复杂度分析预处理O(217N)O(2^{17} N)O(217N)统计cnt\textit{cnt}cnt需要O(N)O(N)O(N)。每个修改和查询操作O(1)O(1)O(1)。总时间复杂度O(N217操作数)O(N 2^{17} \text{操作数})O(N217操作数)空间复杂度O(16×65536)O(16 \times 65536)O(16×65536)。代码实现// A Sequence of Numbers// UVa ID: 1406// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.210s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN,caseNo1;while(cinNN!-1){vectorintcnt(65536,0);for(inti0;iN;i){intx;cinx;cnt[x];}// ansTable[T][shift] 表示当位为 T 且全局偏移为 shift模 2^(T1)时的答案vectorvectorlonglongansTable(16,vectorlonglong(65536,0));for(intT0;T16;T){intM1(T1);// 模数inthalf1T;// 区间长度后半段vectorlonglongA(M,0);for(intv0;v65536;v)if(cnt[v])A[v%M]cnt[v];// 循环前缀和复制一份vectorlonglongpref(2*M1,0);for(inti0;i2*M;i)pref[i1]pref[i]A[i%M];for(intshift0;shiftM;shift){// 起点 s (half - shift) mod M区间长度为 halfints(half-shift)%M;if(s0)sM;ansTable[T][shift]pref[shalf]-pref[s];}}longlongtotal0;intoffset0;// 全局累加偏移模 65536string op;while(cinop){if(opE)break;if(opC){intdelta;cindelta;offset(offsetdelta)%65536;}else{// QintT;cinT;intM1(T1);intshiftoffset%M;totalansTable[T][shift];}}coutCase caseNo: total\n;caseNo;}return0;}总结本题的关键在于利用值域小161616位和操作的全局性将问题转化为预处理所有可能偏移量下的查询答案从而将每次查询降为O(1)O(1)O(1)。这种思想也适用于其他“整体增减 分段统计”的问题。核心技巧使用全局偏移量避免逐元素修改对每个二进制位分别预处理循环位移后的区间和利用循环前缀和快速计算任意偏移下的答案。该解法时间复杂度与操作数无关预处理开销极小是处理此类问题的经典方法。