传送门


这道题挺有意思的，而且自己搞了一个和大多数题解不一样的解法。


首先我们枚举断环为链的地方\(i\)。对于从\(i-1\)到\(i\)，相当于只把元素\(a_i\)挪到了序列最后，因此最多只会影响一个基因编号所在的括号序列，那么我们可以把每一个基因编号单独考虑，分别求出把当前最前面的括号挪到了后面后，这个括号序列是否是合法的。最后扫一遍就能得出答案。


具体思路是这样的：
首先我们可以排除左右括号总数不相等的基因编号，因为这样的括号序列一定是不合法的。
对于剩下的序列，以其中基因编号为\(x\)的序列为例：
判断括号序列是否合法，就是要保证任何时刻左括号数目不少于右括号数目，这个把左括号看成1，右括号看成-1，求一遍前缀和\(sum\)就行。如果\(min\{sum_i\} \geqslant 0\)，那么括号序列就合法（经过第一步筛选已经保证了左右括号数目相等）
现在要将第一个括号挪到最后，我们考虑对他后面的\(sum_i\)的影响：如果第一个括号为左括号，那么后面的\(sum_i\)都要-1；如果第一个括号为右括号，那么后面的\(sum_i\)都要+1，这样操作完后就能用同样的方法判断括号序列是否合法了。


所以我们现在要用单次\(O(1)\)或者\(O(logn)\)的复杂度来实现一下操作：
1.删除队首元素
2.向队尾添加元素
3.队列中的所有元素+1/-1.
4.查找队列中的最小值。


操作1和2好办；先不考虑3操作，操作4可以用set维护，只不过取set首元素的时候要判断是否已经被当做队首删除，若删除了就不要，直到取到一个没被删除的或者当做队尾新添加的元素。
现在有了操作3，我们可以换一个思路：保持队列中的元素不变，单独开一个变量\(A\)记录队列所有元素变化了多少，那么最后判断是否小于0的时候只要跟\(A\)比较而不是0就好了。


这样我们就在单次\(O(logn)\)的时间复杂度内实现了上述操作：即动态判断一个序列是否合法。
最后我们对于每一个断点\(x\)，记\(ans[x]\)表示将\(a_x\)挪到后面后他所在的基因编号的括号序列的变化情况：是从合法变成不合法，还是从不合法变成了合法，还是没有改变。这样我们扫一遍就能统计每一个断点对应的合法的括号序列个数了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<set>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e6 + 5;
In ll read()
{
	ll ans = 0;
	char ch = getchar(), las = ' ';
	while(!isdigit(ch)) las = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	if(las == '-') ans = -ans;
	return ans;
}
In void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}

int n, N = 0, Max = 0, pos = 1;
bool vis[maxn];
struct Node
{
	int flg, id;	
}t[maxn];

char ss[20];
In void change(int x)
{
	t[x].flg = (ss[0] == 's') ? 1 : -1;
	int tp = 0, len = strlen(ss);
	for(int i = 1; i < len; ++i) tp = tp * 10 + ss[i] - '0';
	N = max(N, tp), vis[t[x].id = tp] = 1;
}

struct Set
{
	int val, p, New;		//val是对应的前缀和，p表示第几个元素，New表示是否是当做队尾新加入的 
	In bool operator < (const Set& oth)const
	{
		if(val ^ oth.val) return val < oth.val;
		if(New ^ oth.New) return New < oth.New;
		return p < oth.p;
	}
};
#define sSet set<Set>::iterator
vector<int> v[maxn];
set<Set> s;
int sum, las = 1;
In int init(int ID)
{
	s.clear();
	sum = 0, las = 1;
	for(int i = 0; i < (int)v[ID].size(); ++i) 
	{
		sum += t[v[ID][i]].flg;
		s.insert((Set){sum, v[ID][i], 0});
		if(sum < 0) las = 0;
	}
	if(sum) las = 0;
	return las;
}

int ans[maxn];
bool ha[maxn];                                                      	       //表示这个元素是否已经被当做队首删除
In void solve(int ID)
{
	int A = 0;
	for(int i = 0; i < (int)v[ID].size(); ++i)
	{
		int p = v[ID][i];
		A += t[p].flg, ha[p] = 1;
		s.insert((Set){A, p, 1});
		while(1)
		{
			sSet it = s.begin(); Set tp = *it;
			if(ha[tp.p] && !tp.New) s.erase(it);		      //当前set首元素无效 
			else 
			{
				bool flg = (tp.val - A) >= 0;
				if(las ^ flg)				      //判断括号序列的变化情况 
				{
					ans[p] = las ? -1 : 1;
					las ^= 1;
				}
				break;
			}
		}
	}
}

int main()
{
	n = read();
	for(int i = 1; i <= n; ++i)
	{
		scanf("%s", ss);
		change(i);
	}
	for(int i = 1; i <= n; ++i) v[t[i].id].push_back(i);	//存每一个基因编号对应的括号序列 
	for(int i = 1; i <= N; ++i) if(v[i].size())
	{
		Max += init(i);
		if(!sum) solve(i);
	}
	int Ans = Max, pos = 1;
	for(int i = 1; i <= n; ++i) 
	{
		Max += ans[i];
		if(Max > Ans) Ans = Max, pos = i + 1;
	}
	write(pos), space, write(Ans), enter;
	return 0;
}