[数据结构与算法]杭电三补题1007

21杭电三

链接

题意和题解 都不重要

算法很简单

重要的是，16进制的读入读出以及lower_bound的越界问题

注意vector 和 lower_bound结合时，会不会vector访问越界

tip

格式说明符：

%c 字符型

%d 十进制数

%i 读入十进制，八进制，十六进制数。输入的时候正常是十进制数，若输入0前缀的数将读入八进制，0x前缀读入16进制。若输入09 则读入0，9进入缓冲区

%f 浮点数

%o 八进制数

%s 字符串，碰到空格或回车结束

%x 16进制数

%p 指针

%n 至此已读入值的等价字符数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e5 +10;
ll a[MAX][4];
int m[MAX];

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        vector<int>idx;
        int n, q;
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; i++) {
            scanf("%d %2X%2X%2X", &m[i], &a[i][0], &a[i][1], &a[i][2]);
        }
        a[0][0] = 0, a[0][1] = 0, a[0][2] = 0;
        for(int i = 1; i <= n; i++) {
            if(m[i] == 1) {
                idx.push_back(i);
            }
            if(m[i] == 2) {
                a[i][0] += a[i - 1][0];
                a[i][1] += a[i - 1][1];
                a[i][2] += a[i - 1][2];
            }
        }
        while(q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            ll ans[4];
            ll pos = lower_bound(idx.begin(), idx.end(), l) - idx.begin();
            if(idx.size() == 0 || pos == idx.size()) {
                for(int j = 0; j < 3; j++) {
                    ans[j] = a[r][j] - a[l - 1][j];
                }
            }
            else if(idx[pos] <= r) {
                for(int j = 0; j < 3; j++) {
                    ans[j] = a[r][j];
                }
            }
            else {
                for(int j = 0; j < 3; j++) {
                    ans[j] = a[r][j] - a[l - 1][j];
                }
            }
            printf("%02X%02X%02X\n", min(255ll, ans[0]), min(255ll, ans[1]), min(255ll, ans[2]));
        }
    }
}