1 条题解
-
0
注意到输入的数据均为整数,而相对于直接的 , 和 这一拓宽区间的行为显然不会让答案更大,也更不可能让答案更小,所以可以直接去掉。
于是题意可以转化为:
给定 条线段,每条线段覆盖 ,带权值 。 次询问,每次询问给定 ,输出与 相交的线段的权值之和。
显然,数据范围中 和 偏小,所以直接考虑根据时间戳(即线段端点下标)建立一个桶。瓶颈在于怎么维护数据。
考虑特殊化数据,如果加入的数据是点而不是线段,可以直接用差分思想来计算。具体来说,定义 表示在 段内点的权值之和,则答案可等价表示为 的答案减去 的答案,即 。
如果假如线段,则可以定义两个数组 和 ,分别表示 内出现的线段的权值之和和结束的线段的权值之和,答案即为 。两个数组使用前缀和预处理即可。
预期得分 。
#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
- 上传者