ABC294E数组压缩存储计算重合数量

1、枚举b的区间
2、枚举重合区间
3、计算重合部分

#include <bits/stdc++.h>
#define LL long long
#define N 100050
using namespace std;
LL n, m, i, j, k, x, y, t, b, d, p, q, ans, a[N], c[N], s[N];
int main(){
    scanf("%lld%lld%lld", &n, &x, &y);
    for(i=1; i<=x; i++){
        scanf("%lld%lld", &a[i], &c[i]);
        s[i] = s[i-1] + c[i];
    }
    for(i=j=1; j<=y; j++){
        scanf("%lld%lld", &b, &d);
        p = q + 1, q += d;//数字b出现在位置[p, q]
        t = lower_bound(s+1, s+x+1, p) - s;
        for(k=t; k<=x; k++){//每个区间至多算2次
            if(s[k-1]+1 > q) break;
            if(a[k] != b) continue;
            ans += min(s[k], q) - max(s[k-1], p-1);
        }//数字a[k]在s[k-1]+1~s[k]，计算重合部分
    }//仅扫描可能的区间，统计区间重合部分
    printf("%lld\n", ans);
    return 0;
}

#include <bits/stdc++.h>
#define LL long long
#define N 100050
using namespace std;
LL n, m, i, j, k, x, y, t, b, d, p, q, ans, a[N], c[N], s[N];
int main(){
    scanf("%lld%lld%lld", &n, &x, &y);
    for(i=1; i<=x; i++){
        scanf("%lld%lld", &a[i], &c[i]);
        s[i] = s[i-1] + c[i];
    }
    for(i=j=1; j<=y; j++){
        scanf("%lld%lld", &b, &d);
        p = q + 1, q += d;//数字b出现在位置[p, q]
        t = lower_bound(s+1, s+x+1, p) - s;
        for(k=t; k<=x&&s[k]<=q; k++){//每个区间至多算2次
            if(a[k] != b) continue;
            ans += s[k] - max(s[k-1], p-1);
        }//数字a[k]在s[k-1]+1~s[k]，计算重合部分
        if(a[k] == b && q > s[k-1]){
            ans += q - max(s[k-1], p-1);
        }
    }
    printf("%lld\n", ans);
    return 0;
}