1 条题解

  • 0
    @ 2026-4-23 16:50:02

    注意到输入的数据均为整数,而相对于直接的 [s,t][s,t]0.1-0.1+0.1+0.1 这一拓宽区间的行为显然不会让答案更大,也更不可能让答案更小,所以可以直接去掉。

    于是题意可以转化为:

    给定 NN 条线段,每条线段覆盖 [li,ri][l_i,r_i],带权值 cic_iMM 次询问,每次询问给定 [s,t][s,t],输出与 [s,t][s,t] 相交的线段的权值之和。

    显然,数据范围中 llrr 偏小,所以直接考虑根据时间戳(即线段端点下标)建立一个桶。瓶颈在于怎么维护数据。

    考虑特殊化数据,如果加入的数据是点而不是线段,可以直接用差分思想来计算。具体来说,定义 cnti\textrm{cnt}_i 表示在 1i1 \sim i 段内点的权值之和,则答案可等价表示为 1t1 \sim t 的答案减去 1s11 \sim s-1 的答案,即 cnttcnts1\textrm{cnt}_t-\textrm{cnt}_{s-1}

    如果假如线段,则可以定义两个数组 cntli\textrm{cntl}_icnt2i\textrm{cnt2}_i,分别表示 1i1 \sim i 内出现的线段的权值之和和结束的线段的权值之和,答案即为 cnt1tcnt2s1\textrm{cnt1}_t-\textrm{cnt2}_{s-1}。两个数组使用前缀和预处理即可。

    预期得分 100pts100\textrm{pts}

    #include <cstdio>
    long long cntl[1000002],cntr[1000002],c; 
    int n,m,l,r,s,t;
    int main() {
    	scanf("%d",&n);
    	while(n--) scanf("%d%d%lld",&l,&r,&c), cntl[l]+=c, cntr[r]+=c;
    	for(int i=1; i<=1000000; i++) cntl[i]+=cntl[i-1], cntr[i]+=cntr[i-1];
    	scanf("%d",&m);
    	while(m--) scanf("%d%d",&s,&t), printf("%lld\n",cntl[t]-cntr[s-1]);
        return 0;
    }
    
    • 1

    信息

    ID
    9655
    时间
    2000ms
    内存
    1024MiB
    难度
    8
    标签
    递交数
    14
    已通过
    6
    上传者