Revenge of Segment Tree(思维)
Revenge of Segment TreeTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1796 Accepted Submission(s): 666 Problem Description In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. A similar data structure is the interval tree.
Input The first line contains a single integer T, indicating the number of test cases.
Output For each test case, output the answer mod 1 000 000 007.
Sample Input 2 1 2 3 1 2 3
Sample Output 2 20 Hint For the second test case, all continuous sub-sequences are [1], [2], [3], [1, 2], [2, 3] and [1, 2, 3]. So the sum of the sum of the sub-sequences is 1 + 2 + 3 + 3 + 5 + 6 = 20. Huge input, faster I/O method is recommended. And as N is rather big, too straightforward algorithm (for example, O(N^2)) will lead Time Limit Exceeded. And one more little helpful hint, be careful about the overflow of int. |
题意 : 求所有区间的和 .
题解: 对于当前第i 个数 ,我们只需要计算出一共在多少个子区间中出现a[i] , 再用 C(a[i]) 表示a[i] 在所有子区间的出现次数. 答案是C(a[i]) = i*(n-i+1), i代表第i个数前面有多少个数,包括它自己,(n-i+1)代表第i个数后面有多少个数,包括它自己,然后相乘,代表前面的标号和后边的标号两两配对 .
参考 : https://blog.csdn.net/sr_19930829/article/details/40707173
如图:
#include <iostream>
#include <cstdio>
using namespace std ;
typedef long long LL ;
const LL mod = 1000000007 ;
int main(){
int T ;
cin >>T ;
while(T--){
LL n ;
LL x ;
LL ans = 0 ;
scanf("%I64d",&n);
for(int i = 1 ; i<=n ;i++ ){
scanf("%I64d",&x);
ans = (ans +i*(n-i+1)%mod*x%mod)%mod ;
}
printf("%I64d\n",ans);
}
return 0 ;
}
上一篇: 液晶显示器使用经验谈
下一篇: 7-52 两个有序链表序列的交集 C语言
推荐阅读
-
浅谈线段树 Segment Tree
-
线段树(segment tree)详解
-
Leetcode-307. 区域和检索 - 数组可修改 Range Sum Query - Mutable (线段树Segment Tree)-超详细Python
-
构造思维+树形结构 Codeforces Round #612 (Div. 2) D题 Numbers on Tree
-
2020牛客暑期多校第二场 C - Cover the Tree(思维/贪心)
-
简单了解一下 Segment Tree 和 Fenwick Tree(Binary Indexed Tree)
-
Revenge of Segment Tree(思维)
-
hdu6228 Tree (图论思维题)
-
hdu-6228 Tree 2017年ICPC沈阳站L题 DFS+思维
-
浅谈线段树 Segment Tree