【zzuliOJ】1917 - 晴天算价值（二分 & STL）

FishWang

发布于 2025-08-27 10:53:41

16400

代码可运行

运行总次数：0

代码可运行

点击打开题目

1917: 晴天算价值

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 95 Solved: 12 Submit Status Web Board

Description

晴天有非常严重的选择恐惧症，每次吃饭前他都在纠结到底吃什么。。今天又到了吃饭的时候了。

重光：我给你一个包含n个不同整数的序列a，如果它所有连续子序列的价值和是素数咱们就吃米，不然就吃面。

定义一个序列的价值为序列中所有元素的最小值。

晴天：这不是分分钟给你算出来。

嗯...十分钟过去了，晴天选择死亡。

这个任务就交给你啦。

算出所有连续子序列的价值和。

Input

第一行输入一个整数t，代表有t组测试数据。每组数据第一行包含一个整数n，表示序列a的元素个数。接下来一行包含n个整数，表示序列a。 0<=n<=50000，1<=ai<=50000。

Output

对于每组数据输出一个整数，表示序列a的所有连续子序列的价值和。

Sample Input

1 2 3

Sample Output

HINT

Source

haut

题目名称还是我编的。

我们求出每一个数对区间最小值的贡献就行了。

先把数字编码，然后sort一下。依次取当前最小的数，往vector中插入（二分插入），它前后的下标是自身贡献的区间的区间边缘，就是说，到那些数的时候，它的贡献停止。

为了方便计算，我们先把vector中加入一个0一个n+1.

代码如下：

#include <stdio.h>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define CLR(a,b) memset(a,b,sizeof(a))
struct node
{
	int num,k;
}data[50011];
bool cmp(node a,node b)
{
	return a.num < b.num;
}
int main()
{
	int u;
	int n;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d",&n);
		for (int i = 1 ; i <= n ; i++)
		{
			scanf ("%d",&data[i].num);
			data[i].k = i;
		}
		sort(data+1 , data+1+n , cmp);
		vector<int> s;
		s.push_back(0);
		s.push_back(n+1);
		LL ans = 0;
		int pos;
		for (int i = 1 ; i <= n ; i++)
		{
			pos = upper_bound(s.begin() , s.end() , data[i].k) - s.begin();
			ans += data[i].num * (data[i].k - s[pos-1]) * (s[pos] - data[i].k);
			s.insert(s.begin() + pos , data[i].k);
		}
		printf ("%lld\n",ans);
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除

int