2021“MINIEYE杯”中国大学生算法设计超级联赛（3）1007.Photoshop Layers (前缀和,进制转换）

题意：给你\(n\)个用16进制表示的RGB三元组，\(q\)个询问，询问区间\([l,r]\)的三元组和，如果某个三个元组的状态为\(1\),那么直接用该三元组的值覆盖前面的值，如果是\(2\)则正常求和.

题解：用nx数组记录离当前位置最近的状态为\(1\)的三元组的位置，然后前缀和记录判断一下就好了.这题读入好像卡的很死，要用scanf.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,q;
struct misaka{
    int m;
    int r,g,b;
}lay[N],sum[N];
int nx[N];

int fpow(int a,int k){
    int res=1;
    while(k){
        if(k&1) res=res*a;
        k>>=1;
        a*=a;
    }
    return res;
}

int main() {
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        scanf("%d %d",&n,&q);
        rep(i,1,n){
            scanf("%d",&lay[i].m);
            char s[6];
            scanf("%s",&s);
            for(int k=0;k<6;k+=2){
                int num=0;
                rep(j,k,k+1){
                    int cnt=0;
                    if(s[j]=='A') cnt=10;
                    else if(s[j]=='B') cnt=11;
                    else if(s[j]=='C') cnt=12;
                    else if(s[j]=='D') cnt=13;
                    else if(s[j]=='E') cnt=14;
                    else if(s[j]=='F') cnt=15;
                    else cnt=s[j]-'0';
                    num+=cnt*fpow(16,1-(j-k));
                }
               // cout<<num<<'\n';
                if(k==0) lay[i].r=num;
                if(k==2) lay[i].g=num;
                if(k==4) lay[i].b=num;
            }
        }
        int f=0;
        rep(i,1,n){
            if(lay[i].m==1){
                sum[i].r=lay[i].r;
                sum[i].g=lay[i].g;
                sum[i].b=lay[i].b;
                f=i;
            }
            else{
                sum[i].r=sum[i-1].r+lay[i].r;
                sum[i].g=sum[i-1].g+lay[i].g;
                sum[i].b=sum[i-1].b+lay[i].b;
            }
           // cout<<sum[i].r<<' '<<sum[i].g<<' '<<sum[i].b<<'\n';
            nx[i]=f;
        }
        rep(i,1,q){
            int l,r;
            scanf("%d %d",&l,&r);
            if(lay[r].m==1 || nx[r]>=l){
                printf("%02X%02X%02X\n",min(255,sum[r].r),min(255,sum[r].g),min(255,sum[r].b));
                continue;
            }
            int resr=min(255,sum[r].r-sum[l-1].r);
            int resg=min(255,sum[r].g-sum[l-1].g);
            int resb=min(255,sum[r].b-sum[l-1].b);
            printf("%02X%02X%02X\n",resr,resg,resb);
        }
    }


    return 0;
}