P9094 [PA 2020] Mieszanie kolorów 题解

正常用三个差分数组得别的楼主已经讲的十分详细了，这里给大家提供一个类似哈希的写法。

思路

首先，因为我们知道只有蓝和黄加一块才能变成绿色，所以我们可以遇到红色就把差分数组的对应位加上一个极大的数，之后是蓝色，因为我们要区分到底是否使用了蓝色和黄色两种颜色，所以蓝色的差分数组的值就要很严谨，首先我们知道最多次数是 1000000 次，所以我们就可以将蓝色设为红色值除以 1000000 数，之后黄色我们设一个小的数字就可以了，但一定要是蓝色值得因数，这样我们再进行判断就可以了。

Code

#include <bits/stdc++.h>
using namespace std;
#define int __int128
const int N=1e6+5;
int sum[N],a[N];
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
    return k*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
signed main(){
    int n,m;
    n=read(),m=read();
    signed cnt=0;
    while (m--){
        int l,r,k;
        l=read(),r=read(),k=read();
        if (k==3){
            k=1e15;
        }
        if (k==2){
            k=1e7;
        }
        if (k==1){
            k=2;
        }
        a[l]+=k,a[r+1]-=k;
    }
    int MAX=1e7,MAXN=1e15;
    for (int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
        if (sum[i]<MAXN && sum[i]%2==0 && sum[i]%MAX!=0 && sum[i]>=MAX){
            cnt++;
        }
    }
    write(cnt);
    return 0;
}