题解 | 染色

这一题是差分数组的应用，因为是在一段区间里面的批量操作

当向油漆桶中假如各种颜色的油漆时，会有不同的结果

那么我们就可以根据它调料颜色的种类创建三种差分数组，用于表示加该种颜色的次数的差分数组

如果k==1，那么dy[l]+=1;dy[r+1]-=1;……

最后我们久对它们求前缀和，变成原数组，也就是表示该油漆桶中加入了哪些调料，然后根据加入调料的情况，选择绿色那一种

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int m=scanner.nextInt();
		int dy[]=new int[n+2];
		int db[]=new int[n+2];
		int dr[]=new int[n+2];
		while(m-->0) {
			int l=scanner.nextInt();
			int r=scanner.nextInt();
			int k=scanner.nextInt();
			if(k==1) {
				dy[l]+=1;
				dy[r+1]-=1;
			}else if(k==2) {
				db[l]+=1;
				db[r+1]-=1;
				
			}else {
				dr[l]+=1;
				dr[r+1]-=1;
			}
			
		}
		int count=0;
		for (int i = 1; i < dr.length; i++) {
			dy[i]+=dy[i-1];
			db[i]+=db[i-1];
			dr[i]+=dr[i-1];
			if(dy[i]>0&&db[i]>0&&dr[i]==0) {
				count++;
			}
		}
		System.out.println(count);

	}

}