题解：P12182 DerrickLo's Brackets (UBC002E)

· · 题解

分析

赛后写一个出题人 & 验题人解。

读前注意：这篇题解非常不使用数学语言，但是比较形象。

我们先画出整个括号序列的图（假设一个 ( 使线往上走一格，一个 ) 往下走一格），假设它长这样：（红线间是一个 a_i）

那么转化完题意后结果就是要找那个区间内最长的线使得两边“海拔”相等。我们想一下什么样的线才最长，不妨设我们有一个 [l',r'] 是海拔相等的，若它的两端都不是某个 a_i 的两端，[l'-1,r'+1] 必定也是海拔相等的。

我们既然已经知道最长的海拔相等的线需要端点，不妨就从端点向左或者向右找最远的海拔相等的位置，且中间不被别的括号挡住（这里以向右为例）：

我们假设一个箭头从 s 点出发，箭头指向了区间 [t-1,t]（如果刚好指向了一个端点，我们认为那个端点就是 t），那么只要询问区间 [l,r] 包含 [s,t]，这段箭头就可能作为一个最长的海拔相等的线段，也就是可以为本次询问做贡献，这是一个二位数点问题。

但是我们漏了一些东西，请看这里：

如果很多的端点同一个高度，我们就需要知道询问区间 [l,r] 最多容纳多少个这样的端点，但这样的端点数量一定不少，于是我们研究一下就会发现只有满足该端点海拔为区间最小值的才会被漏算。如果不是最小值，往两边个扩展到下一个端点必然会比当前的长度长；如果不能扩展则说明有一个端点是询问区间的端点，会在第一部分（即二维数点）的时候被计算。如图：

这样一来，我们只需要支持区间最小值和区间某个数最前和最后的出现位置即可。我们分别使用线段树与 vector 上二分可以求得。

然后对两部分的最长线段长度取 \max 即可。

AC Code


#include <bits/stdc++.h>
using namespace std;
#define int long long
stack<int> st;
const int N=1e6+10;
int a[N],sum[N],h[N],n,q;
vector<int> pos[N];
string t;
set<int> lsh;
unordered_map<int,int> mp;
//hi->height of i
struct node
{
    int l,r,len;
}p[N<<1];
int cmp(node x,node y)
{
    return x.r<y.r;
}
struct query
{
    int l,r,id;
}qry[N];
int cmp2(query x,query y)
{
    return x.r<y.r;
}
int ans[N];
int tr[N<<2];
void add(int k,int c,int x=0,int y=n,int o=1)
{
    if(x==y)
    {
        tr[o]=max(tr[o],c);
        return;
    }
    int m=x+y>>1;
    if(k<=m) add(k,c,x,m,o<<1);
    else add(k,c,m+1,y,o<<1|1);
    tr[o]=max(tr[o<<1],tr[o<<1|1]);
}
void upd(int k,int c,int x=0,int y=n+1,int o=1)
{
    if(x==y)
    {
        tr[o]=c;
        return;
    }
    int m=x+y>>1;
    if(k<=m) upd(k,c,x,m,o<<1);
    else upd(k,c,m+1,y,o<<1|1);
    tr[o]=min(tr[o<<1],tr[o<<1|1]);
}
int qmax(int l,int r,int x=0,int y=n,int o=1)
{
    if(l<=x&&y<=r) return tr[o];
    int m=x+y>>1;
    int res=0;
    if(l<=m) res=qmax(l,r,x,m,o<<1);
    if(r>m) res=max(res,qmax(l,r,m+1,y,o<<1|1));
    return res;
}
int qmin(int l,int r,int x=0,int y=n+1,int o=1)
{
    if(l<=x&&y<=r) return tr[o];
    int m=x+y>>1;
    int res=1e9;
    if(l<=m) res=qmin(l,r,x,m,o<<1);
    if(r>m) res=min(res,qmin(l,r,m+1,y,o<<1|1));
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
    cin>>t;
    t=' '+t;
    for(int i=1;i<=n;i++) h[i]=h[i-1]+(t[i]=='('?1:-1)*a[i],lsh.insert(h[i]);
    lsh.insert(0);
    int lcnt=0;
    for(auto i:lsh) mp[i]=++lcnt;
    for(int i=0;i<=n;i++)
    {
        int nh=mp[h[i]];
        upd(i,nh);
        pos[nh].push_back(i);
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(t[i]=='(') st.push(i);
        else
        {
            while(st.size()&&h[i]<h[st.top()-1]&&h[st.top()-1]<=h[i-1])
            {
                p[++cnt]={st.top(),i,sum[i-1]-sum[st.top()-1]+h[i-1]-h[st.top()-1]};
                st.pop();
            }
        }
    }
    while(st.size()) st.pop();
    for(int i=n;i;i--)
    {
        if(t[i]==')') st.push(i);
        else
        {
            while(st.size()&&h[i]>=h[st.top()]&&h[st.top()]>h[i-1])
            {
                p[++cnt]={i,st.top(),sum[st.top()]-sum[i]+h[i]-h[st.top()]};
                st.pop();
            }
        }
    }
    for(int i=1;i<=q;i++)
    {
        cin>>qry[i].l>>qry[i].r;
        qry[i].id=i;
        int minn=qmin(qry[i].l-1,qry[i].r);
        ans[i]=sum[*(upper_bound(pos[minn].begin(),pos[minn].end(),qry[i].r)-1)]-sum[(*lower_bound(pos[minn].begin(),pos[minn].end(),qry[i].l-1))];
    }
    memset(tr,0,sizeof tr);
    sort(p+1,p+cnt+1,cmp);
    sort(qry+1,qry+q+1,cmp2);
    int pt=1;
    for(int i=1;i<=q;i++)
    {
        while(pt<=cnt&&p[pt].r<=qry[i].r)
        {
            add(p[pt].l,p[pt].len);
            pt++;
        }
        ans[qry[i].id]=max(ans[qry[i].id],qmax(qry[i].l,n));
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
}