P5658 [CSP-S2019] 括号树

· · 个人记录

https://www.luogu.com.cn/problem/P5658

复杂度分析

本题数据范围 n<=5e5

考虑每一个位置是不可改变的，时间复杂度为O( n )

那么处理字符串需要优化至O( 1 ) 或 O( logn )

遇事不决，先打暴力

枚举位置，生成字符串，查询括号对数

暴力复杂度O( n^4 ) 哈人

但是可以注意到，许多查询都是冗余的，因为 s_{i} 是由 s_{fa[i]} 增加一个字符转移而来的，所以考虑从这里优化

想不出来，特解开摆

本题的特殊性质是：图是一条链

体现为字符串一直增长

从优化的角度思考，要用已处理好的小问题快速地解决大问题

记 k_{i} 为以 i 为结尾的字符串的合法子串数

记 lst_{i} 为以 i 为结尾的字符串 在添加字符后的贡献

如何理解 lst_{i} 呢

比如字符串 ( ))(( ))（） ta的 lst=2

在添加末尾的 ) 时

增加的合法子串是 ( ) 与 (( ))( ) 有 2 个

也就是 本身与并列的括号对一一组合

$k_{i}$ = $ k_{i-1}
  1. 没有匹配的左括号

与加入左括号相同

  1. 位置 j 的左括号与位置 i 匹配
lst_{i}$ = $lst_{j-1}+1

把[ j , i ]当做整体，贡献为 1

k_{i}$ = $ k_{i-1}$ + $ lst_{i}

原先的合法子串不变 增加了 lst_{i} 个

考虑维护栈，来求匹配的 j

左括号：将下标入栈

右括号：栈顶为所求的 j ，弹出 // 树的情况需要记录 j

若为空，则没有匹配

从特解到正解的旅途

从链到树，上述 k_{i} lst_{i}的性质依然成立

不过i-1不能访问ta的上一个节点了，需要用 fa_{i}

把上述的i-1下标换成 fa_{i} 即可，j-1 同理

链类似递推不需要回溯，但树是需要的

与入时相反即可

左括号：弹出栈顶

右括号：将 记录的 j 入栈

#include<bits/stdc++.h>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define int long long
inline int read(){
    int x=0;bool f=true;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=false;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    return f?x:(~(x-1));
}  
const int N=5e5+100;
int n;
int ans=0,id=0,fa[N],c[N],h[N],lst[N],sum[N];
stack<int> s;
struct edge{
    int to,ne;
}e[N];
void add(int u,int v){
    e[++id]=(edge){v,h[u]};
    h[u]=id;
}
void dfs(int u){
    int flag=0;
    if(c[u]==0){
        s.push(u);
    }else{
        if(!s.empty()){
            flag=s.top();
            lst[u]=lst[fa[s.top()]]+1;
            s.pop();
        }
    }
    sum[u]=sum[fa[u]]+lst[u];
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].to;
        dfs(v);
    }
    if(flag!=0){
        s.push(flag);
    }else if(!s.empty()){
        s.pop();
    } 
} 
signed main(){
    n=read();
    string s;cin>>s;s=" "+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='(') c[i]=0;
        else c[i]=1; 
    } 
    for(int i=2;i<=n;i++){
        fa[i]=read();
        add(fa[i],i); 
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        ans=ans xor (sum[i]*i);
    }
    printf("%lld\n",ans);
    return 0;
}