bzoj2209

题解：

splay打标机

往下传递

记录x，y为化简后，区间有多少(,)

代码：

#include<bits/stdc++.h>

const int N=;

using namespace std;

int n,m,t,l,r,c[N][],sum[N],a[N],sz[N],fa[N],rt,rev[N],ops[N];

char s[N];

struct node

{

    int l0,l1,r0,r1;

}val[N];

void maintain(int k)

{

    int l=c[k][],r=c[k][];

    sum[k]=a[k]+sum[l]+sum[r];sz[k]=sz[l]+sz[r]+;

    val[k].l0=min(val[l].l0,sum[l]+a[k]+val[r].l0);

    val[k].l1=max(val[l].l1,sum[l]+a[k]+val[r].l1);

    val[k].r0=min(val[r].r0,sum[r]+a[k]+val[l].r0);

    val[k].r1=max(val[r].r1,sum[r]+a[k]+val[l].r1);

}

void rever(int k)

{

    rev[k]^=;

    swap(val[k].l0,val[k].r0);

    swap(val[k].l1,val[k].r1);

}

void opsite(int k)

{

    ops[k]^=;sum[k]=-sum[k];a[k]=-a[k];

    swap(val[k].l0,val[k].l1);

    swap(val[k].r0,val[k].r1);

    val[k].l0=-val[k].l0;val[k].l1=-val[k].l1;

    val[k].r0=-val[k].r0;val[k].r1=-val[k].r1;

}

void pushdown(int k)

{

    if (rev[k])

     {

        swap(c[k][],c[k][]);rev[k]=;

        rever(c[k][]);rever(c[k][]);

     }

    if (ops[k])

     {

        opsite(c[k][]);

        opsite(c[k][]);

        ops[k]=;

     }

}

void rotate(int x,int &k)

{

    int y=fa[x],z=fa[y],r=(x==c[y][])?:;

    if (y==k)k=x;

    else if (c[z][]==y)c[z][]=x;

    else c[z][]=x;

    fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

    c[y][r^]=c[x][r];c[x][r]=y;

    maintain(y);maintain(x);

}

void splay(int x,int &k)

{

    while (x!=k)

     {

        int y=fa[x],z=fa[y];

        if (y!=k)

         if ((c[y][]==x)^(c[z][]==y))rotate(x,k);

         else rotate(y,k);

        rotate(x,k);

     }

}

int find(int k,int rst)

{

    pushdown(k);

    int l=c[k][],r=c[k][];

    if (sz[l]+==rst)return k;

    if (sz[l]>=rst)return find(l,rst);

    return find(r,rst-sz[l]-);

}

void build(int &k,int l,int r,int last)

{

    if (l>r)

     {

         k=;

        return;

     }

    k=(l+r)>>;

    fa[k]=last;

    if (l==r)

     {

        sum[k]=a[l];sz[k]=;

        if (a[l]<)val[k].l0=val[k].r0=-;

        if (a[l]>)val[k].l1=val[k].r1=;

        return;

     }

    build(c[k][],l,k-,k);

    build(c[k][],k+,r,k);

    maintain(k);

}

int main()

{

    scanf("%d%d",&n,&m);

    scanf("%s",s+);

    for (int i=;i<=n+;i++)

     if (s[i]=='(')a[i]=;else a[i]=-;

    build(rt,,n+,);

    while (m--)

     {

        scanf("%d%d%d",&t,&l,&r);

        l=find(rt,l);r=find(rt,r+);

        splay(l,rt);splay(r,c[l][]);

        int k=c[r][];

        if (t==)printf("%d\n",(val[k].r1+)/-(val[k].l0-)/);

        if (t==)opsite(k);

        if (t==)rever(k);

     }

}