P7073

Aryper · 2021-06-17 11:54:15 · 个人记录

[CSP-J2020] 表达式

考场上写挂了，最后只有35pts。

所以快 \dfrac{3}{4} 年之后再重写是个什么鬼。。。

先给每一个元素标号，再通过栈来建一颗后缀表达式的树。

假如一个点的改变对整棵树有影响就不标记，并继续搜索其子树，否则就将其以及其子树全部标记。

然后问题是我的取反只能取一次。

真的脑子不够用了，居然查了有半个小时。。

2.14KB的代码我也真是神仙。。。

时间复杂度 O(n+q) 。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e5,M=1e6;

ll m,n,cnt,tmp,tot,top,rt,ans,q,x;

string s;

ll a[N+5],b[M+5],st[M+5],rf[N+5],fa[M+5],l[M+5],r[M+5],fei[M+5],c[M+5],f[M+5];

ll dfs(ll p) {
    if(b[p]==-1) return f[p]=fei[p]?!(dfs(l[p])&dfs(r[p])):dfs(l[p])&dfs(r[p]);
    if(b[p]==-2) return f[p]=fei[p]?!(dfs(l[p])|dfs(r[p])):dfs(l[p])|dfs(r[p]);
    if(b[p]>0) return f[p]=fei[p]?!a[b[p]]:a[b[p]];
    return f[p];
}

void fg(ll p,ll flg) {
    if(flg==1) {
        c[p]=1;
        if(b[p]<0) {
            fg(l[p],1);fg(r[p],1);
        }
        return;
    }
    if(b[p]<0) {
        if(b[p]==-1) {
            if(f[l[p]]==0) fg(r[p],1);
            if(f[r[p]]==0) fg(l[p],1);
            if(f[l[p]]==1) fg(r[p],0);
            if(f[r[p]]==1) fg(l[p],0);
        }
        if(b[p]==-2) {
            if(f[l[p]]==1) fg(r[p],1);
            if(f[r[p]]==1) fg(l[p],1);
            if(f[l[p]]==0) fg(r[p],0);
            if(f[r[p]]==0) fg(l[p],0);
        }
    }
    return;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>10) write(x/10);
    putchar(x%10+48);
}

int main() {

    getline(cin,s);

    m=s.size();

    n=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();
    }

    while(cnt<m) {
        if(s[cnt]=='x') {
            cnt++;tmp=0;
            while(s[cnt]!=' '&&cnt<m) {
                tmp=tmp*10+s[cnt]-48;cnt++;
            }
            b[++tot]=tmp;rf[tmp]=tot;
        }
        else {
            if(s[cnt]=='&') b[++tot]=-1;
            if(s[cnt]=='|') b[++tot]=-2;
            if(s[cnt]=='!') b[++tot]=-3;
        }
        cnt++;
    }

    for(ll i=1;i<=tot;i++) {
        if(b[i]>0) {
            st[++top]=i;
        }
        else {
            if(b[i]==-1||b[i]==-2) {
                l[i]=st[top];r[i]=st[top-1];
                fa[st[top]]=i;fa[st[top-1]]=i;
                top--;st[top]=i;
            }
            if(b[i]==-3) {
                fei[st[top]]=!fei[st[top]];
            }
        }
    }

    for(ll i=1;i<=tot;i++) {
        if(b[i]!=-3&&fa[i]==0) {
            rt=i;break;
        }
    }

    memset(f,-1,sizeof(f));

    ans=dfs(rt);

    fg(rt,0);

    q=read();

    for(ll i=1;i<=q;i++) {
        x=read();
        write(c[rf[x]]?ans:!ans);putchar('\n');
    }

    return 0;
}