The sol to expr

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

思路

递归加上一点点优化……
重点:根据区间范围预处理出所有情况。

具体的看以下题解
https://www.luogu.com.cn/article/i0oqvl99
e……水完了

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int m,q,res[N];
string S;
#define FOR(i,_l,_r) for(int i=_l;i<=_r;i++)
bool isnum(char c){
    return c>='0'&&c<='9';
}
int RD(int s,int &x){
    x=0;
    while(isnum(S[s])){
        x=x*10+S[s]-'0';
        s++;
    }
    return s;
}
int clac(int s,int l,int r){
    if(isnum(S[s])){
        int lnum;
        int llim=RD(s,lnum);
        FOR(i,l,r)  res[i]=lnum;
        return llim;
    }
    int rnum;
    int rlim=RD(s+2,rnum);
    int p;
    if(S[s+1]=='>'){
        p=clac(rlim+1,rnum+1,r);
        return clac(p+1,l,rnum);
    }
    else{
        p=clac(rlim+1,l,rnum-1);
        return clac(p+1,rnum,r);
    }
}
int main(){
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    cin>>m>>q>>S;
    clac(0,1,m+1);
    while(q--){
        int x;
        cin>>x;
        x=min(x,m+1);
        cout<<res[x]<<endl;
    }
    return 0;
}