洛谷 P3797 妖梦斩木棒 题解【线段树】

作者: wjyyy 分类: 线段树,解题报告 发布时间: 2018-07-10 10:46

点击量:19

 

   美妙的线段树啊。。。

 

题目背景

妖梦是住在白玉楼的半人半灵,拥有使用剑术程度的能力。

题目描述

有一天,妖梦正在练习剑术。地面上摆放了一支非常长的木棒,妖梦把它们切成了等长的n段。现在这个木棒可以看做由三种小段构成,中间的n-2段都是左右都被切断的断头,我们记做’X’,最左边的一段和最右边的一段各有一个圆头,记做’(‘和’)’。幽幽子吃饱后闲来无事,决定戏弄一下妖梦。她拿来了许多这样的三种小段木棒,来替换掉妖梦切下来的n段中的一部分,然后问妖梦一些问题。这些操作可以这样描述:

  • 1 x C 将第x个小段的木棒替换成C型,C只会是’X’,’(‘,’)’中的一种
  • 2 l r 询问妖梦从第l段到第r段之间(含l,r),有多少个完整的木棒

完整的木棒左右两端必须分别为’(‘和’)’,并且中间要么什么都没有,要么只能有’X’。

 

虽然妖梦能够数清楚这些问题,但幽幽子觉得她回答得太慢了,你能教给妖梦一个更快的办法吗?

 

输入输出格式

输入格式:

第一行两个整数n,m,n表示共有n段木棒,m表示有m次操作。

 

木棒的初始形状为(XXXXXX……XXXXXX)。

 

接下来m行,每行三个整数/字符,用空格隔开。第一个整数为1或2,表示操作的类型,若类型为1,则接下来一个整数x,一个字符C。若类型为2,接下来两个整数l,r。含义见题目描述。

 

输出格式:

对于每一个操作2,输出一行一个整数,表示对应询问的答案。

 

输入输出样例

输入样例#1:
4 4
2 1 4
2 2 4
1 2 (
2 2 4
输出样例#1:
1
0
1

说明

对于30%的数据,1<=n,m<=1000

 

对于100%的数据,1<=n,m<=200000

 

by-orangebird

 

题解:

   表面看上去是一个单点修改,区间查询的线段树,可是维护木棍个数是个问题。可以看出,如果把木棍看作线段树的区间,而拼出来的木棍中间不能出现多余的'(‘或’)’,那么我们计算线段树区间和时,只需要把两边原本就有的木棍数加起来,并判断左区间最右边的左括号和右区间最左边的右括号之间有没有其他括号。如果有,则不增加,如果没有,把个数增加1。

 

   这样一来,我们要维护的信息是:区间内存在的完整木棍数v,最右边的左括号rl,最左边的右括号lr,最左边的左括号ll,最右边的右括号rr。因为我们维护的是最值,所以当没有的时候就设为缺省值。维护最左边的,缺省值为233333(大于200000就可以);维护最右边的,缺省值为0。这样取min或max的时候,在另一个参数有意义时,就不会有影响。

 

   重构代码大法好。一开始准备在原来的代码上改改,后来一个小时过去实在弄不下去了直接重构。改完语法错误就过了= =

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
using std::min;
using std::max;
struct node
{
    int l,r,v,lr,rl,ll,rr;
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        v=0;
    }
    node(){v=0;}
}t[810000];
void maintain(int k)
{
    if(t[ls].rl>t[ls].rr&&t[rs].lr<t[rs].ll)//左区间最右边的左括号和有区间最左边的右括号中间没有其他括号
        t[k].v=t[ls].v+t[rs].v+1;
    else
        t[k].v=t[ls].v+t[rs].v;
    t[k].ll=min(t[ls].ll,t[rs].ll);//维护最大/最小
    t[k].lr=min(t[ls].lr,t[rs].lr);
    t[k].rr=max(t[ls].rr,t[rs].rr);
    t[k].rl=max(t[ls].rl,t[rs].rl);
    return;
}
int n;
void build(int k,int l,int r)
{
    t[k]=node(l,r);
    if(l==r)
    {
        if(l==1)
        {
            t[k].lr=233333;//l开头的缺省值为233333
            t[k].rl=1;//r开头的缺省值为0
            t[k].ll=1;
            t[k].rr=0;
        }
        else if(l==n)
        {
            t[k].lr=n;
            t[k].rl=0;
            t[k].ll=233333;
            t[k].rr=n;
        }
        else
        {
            t[k].lr=233333;
            t[k].rl=0;
            t[k].ll=233333;
            t[k].rr=0;
        }
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    maintain(k);
}
void change(int k,int x,char c)
{
    if(t[k].l==t[k].r)
    {
        if(c=='(')
        {
            t[k].lr=233333;
            t[k].rr=0;
            t[k].ll=x;
            t[k].rl=x;
        }
        else if(c==')')
        {
            t[k].lr=x;
            t[k].rr=x;
            t[k].ll=233333;
            t[k].rl=0;
        }
        else
        {
            t[k].lr=233333;
            t[k].rr=0;
            t[k].ll=233333;
            t[k].rl=0;
        }
        return;
    }
    if(x<=Mid)
        change(ls,x,c);
    else
        change(rs,x,c);
    maintain(k);
    return;
}
int ask(int k,int l,int r)
{
    if(t[k].l==l&&t[k].r==r)
        return t[k].v;
    if(r<=Mid)
        return ask(ls,l,r);
    else if(l>Mid)
        return ask(rs,l,r);
    if(t[ls].rl>t[ls].rr&&t[rs].lr<t[rs].ll&&l<=t[ls].rl&&r>=t[rs].lr)//记得判范围
        return ask(ls,l,Mid)+1+ask(rs,Mid+1,r);
    else
        return ask(ls,l,Mid)+ask(rs,Mid+1,r);
}
int main()
{
    int m,op,l,r;
    char c;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d %c",&l,&c);
            change(1,l,c);
        }
        else
        {
            scanf("%d%d",&l,&r);
            printf("%d\n",ask(1,l,r));
        }
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */