HDU 6979. Photoshop Layers

题意：

颜色可以通过\((R,G,B)\)来表示，其中\(R,G,B\)是\([0,255]\)​上的整数，从而一个像素的颜色可以用一个\(6\)位十六进制数表示。例如：\((R=100,G=255,B=50)\)可以被表示成64FF32​。

现有\(n\)​​个图层，每一图层的所有像素颜色都相同，从底到顶依次编号为\(1,2,3,...,n\)​​​​。屏幕将会从底到顶地处理这些图层。为方便描述，记第\(i\)​层的颜色是\(c_i=(R_i,G_i,B_i)\)​，混合方式为\(m_i(m_i\in \{1,2\})\)​

• 若\(m_i=1\)​​​，混合方式为“普通”，即假定前面所有层的显示的颜色为\((R_p,G_p,B_p)\)，加上这一层后的颜色后为\((R_i,G_i,B_i)\)​。
• 若\(m_i=2\)，混合方式为“线性减淡”，即假定前面所有层的显示的颜色为\((R_p,G_p,B_p)\)​，加上这一层后的颜色为\((\min(R_p+R_i,255),\min(G_p+G_i,255),\min(B_p+B_i,255))\)

现在有\(q\)个询问，第\(i\)个询问中会给出\(l_i,r_i(1\leq l_i\leq r_i \leq n)\)​，问：只保留\([l_i,r_i]\)​​区间的图层，最终屏幕上显示的颜色。

分析：

不涉及修改操作，可以考虑维护前\(i\)个图层的颜色前缀和\(r_i,g_i,b_i\)以及对于第\(i\)个图层，它底下离它最近的（包括它本身）混合方式为“普通”的图层编号\(f_i\)​。询问时，若\(f_r<l\)，答案则为区间\([l,r]\)的和（超过255按255计算），反之，答案则为\([f_r,r]\)的和。

由于一个十六进制数的\(1\)​位恰好对应二进制数的\(4\)位，故对于一个用\(6\)位十六进制表示的颜色\(x\)，可以使用位运算来取出它对应分量（\(R,G,B\)）的值。

取出方法：

r[i] = (x >> 16) & 0xFF;
g[i] = (x >> 8) & 0xFF;
b[i] = x & 0xFF;

C/C++中的scanf和cin都自带读入十六进制数的方法，具体方法可以上网查找。

代码：

#include <cstdio>
const int maxn = 1e5 + 10;
int r[maxn], g[maxn], b[maxn], f[maxn];
int query(int* p, int l, int r) {
    int t = f[r], res;
    if (t < l)
        res = p[r] - p[l - 1];
    else
        res = p[r] - p[t - 1];
    return res > 0xFF ? 0xFF : res;
}
void solve() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int t, x;
        scanf("%d%X", &t, &x);
        r[i] = (x >> 16) & 0xFF;
        g[i] = (x >> 8) & 0xFF;
        b[i] = (x)&0xFF;
        r[i] += r[i - 1];
        g[i] += g[i - 1];
        b[i] += b[i - 1];
        if (t == 1)
            f[i] = i;
        else
            f[i] = f[i - 1];
    }
    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%02X%02X%02X\n", query(r, x, y), query(g, x, y),
               query(b, x, y));
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}