https://www.myijk.com/p/2768

#绿，#括号匹配，#二维数点，#扫描线

分析

识别——括号匹配问题

观察题目特征：

1. 两种字符。
2. 可以进行有向匹配。

可以发现，这就是一个括号序列，$\texttt{4}$ 为左括号，$\texttt{7}$ 为右括号。

题目中的删除操作是对整个序列的动态操作，我们显然不能模拟。我们需要静态地处理。
静态操作的难点就在于下标的改变，此处按下不表。

定义——括号对的等级

每一个极大的合法括号子串，其中的匹配括号对在不同的时刻被删除。

我们定义一个括号对的等级为“它被删除的时刻”。
例如，一个相邻匹配的括号对 $\texttt{()}$ 的等级为 1。

一个括号对的等级，等于这个括号对之间，最大的括号对等级+ 1。
例如，$\texttt{((())())}$ 中各个括号的等级为 $\texttt{32112113}$。

克服——“下标改变”

现在我们来处理下标改变（位移）的问题。由于只有左括号会对答案做出贡献，我们只研究左括号的移动。

如果一个括号对的等级为 $k$，那么在它被删除之前，等级 $[1, k-1]$ 的括号就全部被删除了。
这些括号被删除，就可能导致当前括号对的下标改变。

设当前括号对 $(l, r)$。设 $[1, l-1]$ 中有 $s$ 个括号属于等级为 $[1, k-1]$ 的括号对。
那么，当前括号对的左括号就向前移动了 $s$ 个单位。当前括号对给答案的贡献就是 $l-s$。

求解——二维数点

好，思路有了，接下来就是如何实现。
观察特征：二维查询，下标为第一维，等级为第二维。

没错，这就是一个二维数点问题。

将下标作为第一维，等级作为为第二维。使用扫描线的思想，动态地从左向右扫描这个数列。

查询和加入点都是按照横坐标顺序的，于是可以采取“扫到再加点”的策略。

设当前下标为 $i$, 所在括号对为 $(l, r)$，等级为 $k$。

• 如果 $i = l$，查询矩形 $( (1, 1), (l-1,k-1) )$ 内点的数量 $s$，对答案做出 $l - s$ 的贡献。
• 如果 $i = l$ 或 $i = r$，在坐标系中插入一个点 $(i, k)$。

查询与操作都是在动态扫描中进行的，可以使用树状数组维护权值数组。

终结——代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int n, tp, level[N], tr[N];
pair<int, int> stk[N];
ll ans;
string s;
//树状数组维护权值数组
int lowbit(int x){return x & (-x);}
int ask(int x){
	int res = 0;
	for(int i = x; i >= 1; i -= lowbit(i)) res += tr[i];
	return res;
}
void change(int x, int k){
	for(int i = x; i <= n; i += lowbit(i)) tr[i] += k;
}
int main(){
	ios::sync_with_stdio(0);
	cin >> n >> s;
	s = '#' + s;
	//给匹配的括号序列计算等级，将等级记录到左括号和右括号上
	for(int i = 1; i <= n; i ++){
		if(tp && s[i] == '7' && s[stk[tp].first] == '4'){
			//assign the level[i] and level[stk[tp]]
			level[i] = level[stk[tp].first] = stk[tp].second;
			--tp;
			stk[tp].second = max(stk[tp].second, level[i] + 1);
		}else{
			stk[++tp] = {i, 1};
		}
	}
	for(int i = 1; i <= n; i ++) cerr << level[i] << " ";
	cerr << "\n";
	//扫描线的过程
	for(int i = 1; i <= n; i ++){
		if(s[i] == '4' && level[i] > 0){//左括号，查询
			if(level[i] == 1) ans += 1ll*i;
			else ans += 1ll*i - ask(level[i]-1);
		}
		if(level[i] > 0){//修改
			change(level[i], 1);
		}
	}
	cout << ans;
	return 0;
}

lucky

不难想到，括号匹配。

令 $4='('$， $7 = ')$

于是用 stack 维护，不难发现，其第几轮删除（匹配）是容易计算的。于是，最后我们按删除的顺序加贡献就行了。

具体地，设匹配为 $(l, r)$ 其中 $l<r$ 且 $l$ 是左括号，则在令 $f(x)$ 表示 $x$ 在第几轮删除（不删除为 $0$），则 $f(l) = f(r) = (\max_{i=l+1}^{i=r-1}{f(i)}) + 1$。

最后，按照删除的顺序遍历，维护每个括号位置删没删，发现这很简单。

按顺序遍历

//用 bit 维护 位置 i 有没有被删。

for i in [1, n]
  for j in 在 i 删除的位置
      ans <- ans + j - Q(j) // 有几个被删掉就去掉几个。
  for j in 在 i 删除的位置
      add(j, 2) // 删掉