CodeForces 1373C. Pluses and Minuses

题意:你有一个字符串只包含+和-，你可以进行一些程序在这个字符串上，这个程序的操作如下。

分析:可以发现，当外层循环结束时，依赖的是内层循环的每一次cur都>=0，意味着当cur初值为这个字符串内部前缀和的最小值的绝对值时(当内部有负数的前缀和时)，那么整个程序就会结束。即(cur >= abs(min(presum[1], presum[2], ...)))，那么程序结束。所以循环的次数为0~abs(最小前缀和)次，因为时间复杂度的关系，我们第二层循环可以进行优化，快速找到cur + presum[j] < 0的位置，并把j加到res上，我们可以先排个序，再二分，最后一次循环需要加上整个字符串的长度。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
using LL = long long;
const int N = 1000005;
const int inf = 0x3f3f3f3f;
char s[N];
int sum[N];
struct Node
{
	int val;
	int id;
	bool operator<(const Node& rhs)const
	{
		if (val == rhs.val)
			return id > rhs.id;
		return val < rhs.val;
	}
}sum2[N];
int main()
{
	int t;
	scanf("%d", &t);

	while (t--)
	{
		scanf("%s", s + 1);

		int len = strlen(s + 1);

		for (int i = 1; i <= len; ++i)
		{
			if (s[i] == '+') sum[i] = sum[i - 1] + 1;
			else sum[i] = sum[i - 1] - 1;
		}

		int mn = inf;
		bool flag = true;
		for (int i = 1; i <= len; ++i) if (sum[i] < 0) mn = min(mn, sum[i]), flag = false;

		if (flag)
		{
			cout << len << endl;
		}
		else
		{
			for (int i = 1; i <= len; ++i) sum2[i].val = sum[i], sum2[i].id = i;

			sort(sum2 + 1, sum2 + len + 1);

			LL res = 0;
			for (int i = 0; i < abs(mn); ++i)
			{
				int cur = i;
				int l = 1, r = len;
				while (l < r)
				{
					int mid = l + r + 1 >> 1;
					if (sum2[mid].val < -cur) l = mid;
					else r = mid - 1;
				}
				res = res + sum2[l].id;
			}

			res = res + len;

			cout << res << endl;
		}
	}

	return 0;
}