HDU6979 Photoshop Layers（前缀和）

题目链接：HDU6979 Photoshop Layers

题目描述：

给你 n 个图层，自底向上编号从 $1$​ 到 $n$。图层的混合方式有两种，若 $m=1$，则在之前的图层用当前图层覆盖， 即 $R_n=R_i,G_n=R_i,B_n=B_i$；若 $m=2$，则在之前的图层上叠加当前层，即 $R_n=min(R_p+R_i,255),G_N=min(G_p+G_i,255),B_n=min(B_p+B_i,255)$​​。现在你需要计算 图层 $[l,r]$ 最终显示的RGB值。

输入数据格式为，第一行输入测试样例组数 $T$​​​。对于每组测试样例，第一行输入两个整数 $n$​​，$q$​，表示图层总数和询问次数。接下来 $n$​ 行，输入当前图层的混合模式 $m_i$​，RGB值。接下来 $q$​ 行，输入两个整数 $l_i$ ，$r_i$，表示查询区间。其中 ，$1\le n,q\le 10^5$，$1\le l_i\le r_i\le n$​。

输出数据格式为，对于每次询问，输出一个十六进制数，表示区间 [l,r] 混合后的RGB值。

题目解析：

用 last 数组记录当前图层左边第一个模式为 1 的值。然后用前缀和计算即可。

参考代码：

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1e5+10;

struct node
{
   
	int m, r, g, b;
}node[N];
int last[N], pre1[N], pre2[N], pre3[N];

int main() {
   
	
	int t;
	scanf("%d", &t);
	while (t--) {
   
		memset(node, 0, sizeof(node));
		memset(last, 0, sizeof(last));
		memset(pre1, 0, sizeof(pre1));
		memset(pre2, 0, sizeof(pre2));
		memset(pre3, 0, sizeof(pre3));

		int n, q; scanf("%d%d", &n, &q);
		last[0] = -1;
		for (int i = 1; i <= n; i++) {
   
			int mode, x;
			scanf("%d%x", &mode, &x);
			node[i].m = mode, node[i].r = (x/256/256)%256, node[i].g = (x/256)%256, node[i].b = (x)%256; 
			if (mode == 1) last[i] = i;
			else last[i] = last[i-1];
			pre1[i] = pre1[i-1] + node[i].r;
			pre2[i] = pre2[i-1] + node[i].g;
			pre3[i] = pre3[i-1] + node[i].b;
		}
		
		for (int i = 1; i <= q; i++) {
   
			int l, r;
			scanf("%d %d", &l, &r);
			int rr, gg, bb;
			if (last[r] >= l && last[r] <= r) {
   
				rr = min(node[last[r]].r + pre1[r] - pre1[last[r]], 255);
				gg = min(node[last[r]].g + pre2[r] - pre2[last[r]], 255);
				bb = min(node[last[r]].b + pre3[r] - pre3[last[r]], 255);
			} else {
   
				rr = min(pre1[r] - pre1[l-1], 255);
				gg = min(pre2[r] - pre2[l-1], 255);
				bb = min(pre3[r] - pre3[l-1], 255);
			}
			printf("%02X%02X%02X\n", rr, gg, bb);
		}

	}
	return 0;
}