题解：P8569 [JRKSJ R6] 第七学区

koukou · 2026-01-31 09:27:58 · 题解

按位考虑，对于每个二进制位 j（0 \le j < 64）独立计算贡献。

设 last_j 表示第 j 位上一次出现 1 的位置。

对于当前位置 i 的数值 a_i：

如果 a_i 的第 j 位为 1：所有以 i 结尾的区间，该位都为 1，贡献为 i \times 2^j，然后更新 last_j = i。
如果 a_i 的第 j 位为 0：只有那些包含位置 last_j 的区间，该位才为 1，贡献为 last_j \times 2^j。

总答案即为所有位在所有位置上的贡献之和：

\text{ans} = \sum_{j=0}^{63} \sum_{i=1}^n 2^j \times \text{贡献值}

其中贡献值 =

\begin{cases} i & \text{如果 } a_i \text{ 的第 } j \text{ 位为 1} \\ last_j & \text{如果 } a_i \text{ 的第 } j \text{ 位为 0} \end{cases}

显然这个做法会超时，但是我太菜了想不到更厉害的做法了，所以这里并没有用正经的优化。

考虑先求出所有 last 的值，在一次性更新答案，这样就是好优化的。

对于计算值的部分，由于可能会有很多 1 导致这一部分变得很慢，所以可以直接在循环内多执行几遍操作。

:::success[代码]

while(bits) 
{
    int j = __builtin_ctzll(bits);
    last[j] = i;
    bits &= bits - 1;
    if(!bits) break;
    j = __builtin_ctzll(bits);
    last[j] = i;
    bits &= bits - 1;
    if(!bits) break;
    j = __builtin_ctzll(bits);
    last[j] = i;
    bits &= bits - 1;
    if(!bits) break;
    j = __builtin_ctzll(bits);
    last[j] = i;
    bits &= bits - 1;
    if(!bits) break;
    j = __builtin_ctzll(bits);
    last[j] = i;
    bits &= bits - 1;
}

:::

计算答案的部分我想不到什么比较好的优化了，于是直接将整个循环暴力展开，如果不想写 64 行代码，也可以自己另外写一段代码输出这一段程序。

:::success[代码]

ans += 1ull * last[0];
ans += 2ull * last[1];
ans += 4ull * last[2];
ans += 8ull * last[3];
ans += 16ull * last[4];
ans += 32ull * last[5];
ans += 64ull * last[6];
ans += 128ull * last[7];
ans += 256ull * last[8];
ans += 512ull * last[9];
ans += 1024ull * last[10];
ans += 2048ull * last[11];
ans += 4096ull * last[12];
ans += 8192ull * last[13];
ans += 16384ull * last[14];
ans += 32768ull * last[15];
ans += 65536ull * last[16];
ans += 131072ull * last[17];
ans += 262144ull * last[18];
ans += 524288ull * last[19];
ans += 1048576ull * last[20];
ans += 2097152ull * last[21];
ans += 4194304ull * last[22];
ans += 8388608ull * last[23];
ans += 16777216ull * last[24];
ans += 33554432ull * last[25];
ans += 67108864ull * last[26];
ans += 134217728ull * last[27];
ans += 268435456ull * last[28];
ans += 536870912ull * last[29];
ans += 1073741824ull * last[30];
ans += 2147483648ull * last[31];
ans += 4294967296ull * last[32];
ans += 8589934592ull * last[33];
ans += 17179869184ull * last[34];
ans += 34359738368ull * last[35];
ans += 68719476736ull * last[36];
ans += 137438953472ull * last[37];
ans += 274877906944ull * last[38];
ans += 549755813888ull * last[39];
ans += 1099511627776ull * last[40];
ans += 2199023255552ull * last[41];
ans += 4398046511104ull * last[42];
ans += 8796093022208ull * last[43];
ans += 17592186044416ull * last[44];
ans += 35184372088832ull * last[45];
ans += 70368744177664ull * last[46];
ans += 140737488355328ull * last[47];
ans += 281474976710656ull * last[48];
ans += 562949953421312ull * last[49];
ans += 1125899906842624ull * last[50];
ans += 2251799813685248ull * last[51];
ans += 4503599627370496ull * last[52];
ans += 9007199254740992ull * last[53];
ans += 18014398509481984ull * last[54];
ans += 36028797018963968ull * last[55];
ans += 72057594037927936ull * last[56];
ans += 144115188075855872ull * last[57];
ans += 288230376151711744ull * last[58];
ans += 576460752303423488ull * last[59];
ans += 1152921504606846976ull * last[60];
ans += 2305843009213693952ull * last[61];
ans += 4611686018427387904ull * last[62];
ans += 9223372036854775808ull * last[63];

:::

这两个和一起就做完了，AC 记录。而且这个居然还能跑进最优解第一页。