CF竞赛题目讲解_CF1824D(具有TAG的线段树 + 前缀和)
2023-05-16 15:58 作者:Clayton_Zhou | 我要投稿
AC代码:
https://codeforces.com/contest/1824/submission/206049532
题意:
已知一个由n个整数组成的数组a,索引从1开始, 1≤ai≤n。
定义g(i,j)如下:
g(i,j)是满足{ap:i≤p≤j}={aq:x≤q≤j}而i≤j的最大整数x;
并且g(i,j)=0,而i>j。
有q个查询。对于每个查询,您得到四个整数l、r、x、y,您需要计算∑i=lr∑j=xy g(i,j)。
题解:
具有TAG的线段树 + 前缀和