BZOJ4964 加长的咒语题解

题意：

VictBr发现是他上一次念的咒语是假的！咒语是由且仅由 ( 和 ) 构成的一段连续的字符串，一个咒语合法当且仅当这个咒语的任意一个前缀都满足 ( 的个数不少于 ) 的个数，且整个串的 ( 和 ) 的个数相等。

VictBr的膜法书上只有一长度为 \(n\) 的仅由 ( 和 ) 构成的字符串。长者告诉他世界上所有咒语都在这本膜法书中。

在长者的教诲下，Victbr学会了假的念咒术，然后他向世界上最强的OIer们发出挑战，在欢声笑语中打出GG。为了战胜他们，Victbr写出了更长的膜法书，并再次向最强的OIer们发出挑战。你能回答出他的问题么？

具体的问题是：每次询问膜法书中的一个片段，求这个片段中最长的咒语的长度。

输入格式：

第一行两个正整数 \(n,m\) ，分别表示字符串长度和询问个数。接下来一行一个长度为 \(n\) 的仅由 ( 和 ) 组成的字符串。接下来 \(m\) 行, 每行两个整数 \(x,y\) ，表示询问的片段的左右端点。下标从 \(1\) 开始。满足 \(1 \leq n,m \leq 4 \times 10^{5}\)

输出格式：

对于每个询问，输出最长的咒语的长度。

括号匹配常见思路是把 \(\mathtt{(}\) 看作 \(1\) ，\(\mathtt{)}\) 看作 \(-1\) ，然后求个前缀和。

根据题意，如果一段区间 \([l,r]\) 是匹配的，当且仅当 \(s_{l-1}=s_r=\min_{l-1 \leq i \leq r} s_i\)

考虑如何求最长的匹配子串。我们首先求出区间 \(s_l,s_{l+1},\cdots,s_r\) 中的最小值 \(p\) ，

并记 \(s_u,s_v\) 为 \(p\) 出现的最左和最右端点，此时区间被划分为了三段 \([l,u),[u,v],(v,r)\) （图自参考文献）

容易发现，\([u,v]\) 的答案是一个极大值，因为不存在一个合法区间能跨越 \([u,v]\) 。

因此我们只要在左右两个区间里寻找极大值。例如对于左区间，我们只要计算出每个 \(i\) 向右匹配的最大值即可

时间复杂度 \(\mathcal{O}(n \log n + q)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))
#define LN 20
typedef int sparse_table[LN][N];

char s[N]; sparse_table stl,str,stu,stv;
int n,Q,h[N],nxt[N],pre[N],lg[N],_tmp[N * 2 + 5], *tmp = _tmp + N;
int hmin(int x,int y) { return h[x] <= h[y] ? x : y; }
void init()
{
    int *l = stl[0], *r = str[0], *u = stu[0], *v = stv[0];
    lg[1] = 0; for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 0; i < n; i++) h[i + 1] = h[i] + (s[i] == '(' ? 1 : -1);
    for(int i = 0; i <= n; i++) l[i] = r[i] = i;
    memset(nxt, -1, sizeof(nxt)); memset(pre, -1, sizeof(pre));
    memset(_tmp, -1, sizeof(_tmp)); tmp[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        if(h[i - 1] > h[i]) tmp[h[i - 1]] = -1;
        if(~tmp[h[i]]) nxt[pre[i] = tmp[h[i]]] = i;
        tmp[h[i]] = i;
    }
    for(int i = n; ~i; i--)
    {
        if((~nxt[i]) && (~nxt[nxt[i]])) nxt[i] = nxt[nxt[i]];
        u[i] = ((~nxt[i]) ? nxt[i] - i : 0);
    }
    for(int i = 0; i <= n; i++)
    {
        if((~pre[i]) && (~pre[pre[i]])) pre[i] = pre[pre[i]];
        v[i] = ((~pre[i]) ? i - pre[i] : 0);
    }
}
void build_sparse_table()
{
    int k = n, *fl, *fr, *fu, *fv;
    int *gl = stl[0], *gr = str[0], *gu = stu[0], *gv = stv[0];
    for(int j = 0; (1 << (j + 1)) <= n; j++)
    {
        fl = gl; gl = stl[j + 1]; fr = gr; gr = str[j + 1];
        fu = gu; gu = stu[j + 1]; fv = gv; gv = stv[j + 1]; k -= (1 << j);
        for(int i = 0; i <= k; i++)
        {
            gl[i] = hmin(fl[i], fl[i + (1 << j)]);
            gr[i] = hmin(fr[i + (1 << j)], fr[i]);
            gu[i] = max(fu[i], fu[i + (1 << j)]);
            gv[i] = max(fv[i], fv[i + (1 << j)]);
        }
    }
}
int range(int L,int R,int (*st)[N])
{
    int k = lg[R - L];
    return max(st[k][L], st[k][R - (1 << k)]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q >> s; init(); build_sparse_table();
    for(int x,y,l,r,k,res; Q--; )
    {
        cin >> x >> y; ++y; --x; k = lg[y - x];
        l = hmin(stl[k][x], stl[k][y - (1 << k)]);
        r = hmin(str[k][y - (1 << k)], str[k][x]);
        res = r - l;
        if(x < l) up(res, range(x, l, stu));
        if(y > r + 1) up(res, range(r + 1, y, stv));
        cout << res << '\n';
    }
    return 0;
}