AC日记——妖梦斩木棒 洛谷 P3797

妖梦斩木棒

思路：

　　略坑爹；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 200005

#define maxm maxn<<2

int n,m,L[maxm],R[maxm],mid[maxm],dis[maxm];

bool xx[maxm],ll[maxm],rr[maxm];

struct AnsType {

    int dis;

    bool l,r,x;

};

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'')Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

void updata(int now)

{

    xx[now]=xx[now<<]&xx[now<<|];

    dis[now]=dis[now<<]+dis[now<<|];

    if(rr[now<<]&&ll[now<<|]&&!xx[now<<]&&!xx[now<<|]) dis[now]++;

    ll[now]=xx[now<<]?ll[now<<|]:ll[now<<];

    rr[now]=xx[now<<|]?rr[now<<]:rr[now<<|];

}

struct AnsType node(AnsType a,AnsType b)

{

    AnsType res;

    res.x=a.x&b.x;

    res.l=a.x?b.l:a.l;

    res.r=b.x?a.r:b.r;

    res.dis=a.dis+b.dis;

    if(a.r&&b.l&&!a.x&&!b.x) res.dis++;

    return res;

}

void build(int now,int l,int r)

{

    L[now]=l,R[now]=r;

    if(l==r)

    {

        if(l==) rr[now]=;

        else if(r==n) ll[now]=;

        else xx[now]=,ll[now]=,rr[now]=;

        return;

    }

    mid[now]=l+r>>;

    build(now<<,l,mid[now]);

    build(now<<|,mid[now]+,r);

    updata(now);

}

void updata(int now,int to,int t)

{

    if(L[now]==R[now])

    {

        ll[now]=rr[now]=xx[now]=;

        if(t==) xx[now]=,ll[now]=,rr[now]=;

        if(t==) ll[now]=;

        if(t==) rr[now]=;

        return ;

    }

    if(to<=mid[now]) updata(now<<,to,t);

    else updata(now<<|,to,t);

    updata(now);

}

AnsType query(int now,int l,int r)

{

    if(L[now]==l&&R[now]==r) return (AnsType){dis[now],ll[now],rr[now],xx[now]};

    if(r<=mid[now]) return query(now<<,l,r);

    else if(l>mid[now]) return query(now<<|,l,r);

    else return node(query(now<<,l,mid[now]),query(now<<|,mid[now]+,r));

}

int main()

{

    in(n),in(m),build(,,n);

    int op,l,r,x;char ch[];

    while(m--)

    {

        in(op);

        if(op==)

        {

            in(x),scanf("%s",ch);

            if(ch[]=='X') ch[]=;

            else if(ch[]==')') ch[]=;

            else ch[]=;

            updata(,x,ch[]);

        }

        else

        {

            in(l),in(r);

            AnsType res=query(,l,r);

            printf("%d\n",res.dis);

        }

    }

    return ;

}