题解：P5067 [Ynoi Easy Round 2014] 长存不灭的过去、逐渐消逝的未来

· · 题解

前言：写平衡树写破防了，然后发现对拍的 std 跑的飞快，还非常短，是线段树？

然后就会了，很原啊。

考虑在线段树每个结点上维护其代表的区间的等价表达式。 先把减号替换为 \times (mod-1)+ 以方便后续讨论，这样是等价的。

粗略地来说，替换的形式形如 (3)\rightarrow 3,+2\times 5+\rightarrow +10+。具体地，当我们往右侧加入一个字符时，如果后缀字符形如 +num+num+（即三个运算符（包含括号）与两个数字）或 (num) 时，可以进行缩短。

特殊的是，当最左与最右的运算符存在 \times，且中间的运算符为+，无法进行收缩。但是仍然容易证明，在不出现括号的情况下，且排除不合法情况，收缩后的串长是 O(1) 的。

不过同侧括号将串分割成的若干部分是没法合并的，不过这样只会让我们的时空复杂度都乘 k 罢了（k 即是括号嵌套层数）。

这样就基本完了，合并左右子区间时维护前后缀数字长度方便数字拼接，再将右区间的等价串依次插入左区间的串就好了。

不卡掉空间 O(nk)，只能变成 3 分题了。

实际上空间复杂度并不是 O(nk)，而是 \sum \min(r-l+1,O(k))，下层结点等价串长度不超过 r-l+1，可以认定空间复杂度为 O(n\log{k})。而上层结点总数不多，且容易分析出复杂度为 O(n)。

所以总空间复杂度为 O(n\log k)，实际约为 11n。卡到 31.89MB 了，应该不会被卡了吧。

真成 3 分题了。

系列最后一道，可以安心了？不然对不起 Chtholly

主要代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3e5+5,P=1e9+7;
bool Mst;
inline bool cnum(int x){return x>=0;}
inline int to(char c){
    if(c=='+')return -1;
    if(c=='-')return -2;
    if(c=='*')return -3;
    if(c=='(')return -4;
    return -5;
}
inline bool isbr(int x){return x==-4||x==-5;}
int mi[N];
inline int mol(int x,int y){return x+y>=P?x+y-P:x+y;}
struct myd{
    int p,a[405],pr,sf;
    inline void sig(char c){
        p=0;
        if(c>='0'&&c<='9')a[++p]=c-'0',pr=sf=1;
        else{
            if(c=='-')a[++p]=-1,a[++p]=P-1,a[++p]=-3;
            else a[++p]=to(c);
            pr=sf=0;
        }
    }
    inline void add(int x){
        if(cnum(a[p])||a[p]==-5){
            if(x==-4||cnum(x))return p=-1,void();
        }
        else{
            if(x!=-4&&!cnum(x))return p=-1,void();
        }
        a[++p]=x;
        while(p){
            if(p>=3&&a[p]==-5&&a[p-1]>=0&&a[p-2]==-4){
                a[p-2]=a[p-1],p-=2;
                continue;
            }
            else if(p>=5&&cnum(a[p-1])&&cnum(a[p-3])&&!((a[p]==-3||a[p-4]==-3)&&a[p-2]==-1)){
                if(a[p]==-3||a[p-4]==-3){
                    if(a[p-2]==-1)assert(0);
                    a[p-3]=1ll*a[p-3]*a[p-1]%P;
                }
                else{
                    if(a[p-2]==-1)a[p-3]=mol(a[p-3],a[p-1]);
                    else a[p-3]=1ll*a[p-3]*a[p-1]%P;
                }
                a[p-2]=a[p];p-=2;
                continue;
            }
            break;
        }
    }
    inline void ins(const myd &cur){
        if(p==-1||cur.p==-1)return p=-1,void();
        bool fl=sf&&cur.pr;
        sf=cur.sf;
        if(fl){
            a[p]=(1ll*mi[cur.pr]*a[p]+cur.a[1])%P;
            if(p==1)sf+=cur.sf,pr+=cur.pr;
        }
        for(int i=fl+1;i<=cur.p;i++){
            add(cur.a[i]);
            if(p==-1)return ;
        }
    }
    inline int gt(){
        if(p==-1)return -1;
        for(int i=1;i<=p;i++)if(isbr(a[i]))return -1;
        if(!cnum(a[1])||!cnum(a[p]))return -1;
        int res=0;
        for(int i=1;i<=p;i++){
            int cur=a[i];
            while(i+1<=p&&a[i+1]==-3)cur=1ll*cur*a[i+2]%P,i+=2;
            res=mol(res,cur);
            i++;
        }
        return res;
    }
}tr[N<<2];