A1. Oh Sweet Beaverette

https://codeforces.com/contest/331/problem/A1

关键点：
前缀和，记录每个负数的位置，以及变式前缀和（只记录正数）

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>

using namespace std;
typedef long long ll;



ll lst[300010];//所有的前缀和
ll lstpos[300010];//只记录正数的前缀和
struct pai
{
	ll start, end;//起始端点，结束端点：[start,end]
	pai() { start = -1; end = -1; }
};
int main()
{
	ll n; cin >> n;
	map<ll, pai>mp;//ll指的是这个数，单纯的这个数
	queue<ll>negid;//负数的id，后面输出用
	memset(lst, 0, sizeof(lst));
	for (ll i = 1; i <= n; i++)
	{
		
		cin >> lst[i];
		ll tem = lst[i];//后面处理用
		bool fa = false;//同上
		if (mp[lst[i]].start == -1)mp[lst[i]].start = i;//没有起始，这是第一个
		else if(mp[lst[i]].end == -1) mp[lst[i]].end = i;//有起始没有终止，无条件添加为end
		else//都有就需要比较，如果后一段的和小于等于零，不修改；如果后一段大于0，修改end = i，这里先记录fa，因为lstpos尚未更新，不能直接处理
		{
			fa = true;
			
		}
		lstpos[i] = lst[i];
		if (lstpos[i] < 0) { lstpos[i] = lstpos[i - 1]; negid.push(i); }
		else lstpos[i] += lstpos[i - 1];
		lst[i] += lst[i - 1];
		if (fa)//对应fa那段的处理
		{
			ll jud = lstpos[i] - lstpos[mp[tem].end - 1] + min((ll)0, tem);
			if (jud > 0)
			{
				mp[tem].end = i;
			}
		}
	}
	ll ans = LLONG_MIN;
	map<ll, pai>::iterator it = mp.begin();//预备遍历map
	ll k = 0;
	ll lef = 0, righ = 0;
	while (it != mp.end())
	{
		if (it->second.end != -1 and it->first < 0)//记住这个怎么用
		{
			if (ans < lstpos[it->second.end] - lstpos[it->second.start - 1] + 2 * it->first)//当是个负数，首先要用lstpos的前缀和，然后别忘了加上两端的负数
			{
				ans =  lstpos[it->second.end] - lstpos[it->second.start - 1] + 2 * it->first;
				lef = it->second.start, righ = it->second.end;

			}
		}
		else if (it->second.end != -1 and it->first >= 0)
		{
			if (ans < lstpos[it->second.end] - lstpos[it->second.start - 1])//这个就正常用lstpos就行
			{
				ans = lstpos[it->second.end] - lstpos[it->second.start - 1];
				lef = it->second.start, righ = it->second.end;
			}
		}
		it++;
	}

	cout << ans << ' ' ;
	ll num = lef - 1 + n - righ;//num构成：前+中（negid）+后
	queue<ll>outa;
	while (!negid.empty() and negid.front() <= lef)negid.pop();//弹掉太超前的
	while (!negid.empty() and negid.front() < righ)//压到队列中，预备输出
	{
		outa.push( negid.front()) ;
		negid.pop();
		num++;
	}
	cout << num << endl;//这是完整的num
	for (int i = 1; i < lef; i++)//前
	{
		cout << i << ' ';
	}
	while (!outa.empty())//中
	{
		cout << outa.front() << ' ';
		outa.pop();
	}
	for (int i = righ + 1; i <= n; i++)cout << i << ' ';//后
	return 0;
}

略有成就感的一题，有趣○( ＾皿＾)っHahaha…
小细节可以debug出来