欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 1540 Tunnel Warfare(线段树区间合并)

程序员文章站 2022-06-02 13:39:43
...

题意:

现在有n个点,要进行一些操作,第一种是破坏某个点,第二个询问某个点所处的最长连续没破坏的区间长度,第三种修复最后一个被破坏的点

思路:

简单的区间合并
对于破坏和修复,是简单的单点修改,因为要修复最后一个,可以维护一个栈来方便记录一下,那么这个题需要思考的地方就只有怎么想最大区间了,我们可以这么想,如果这个点存在于我左右儿子的交界处,那么就可以直接输出这段的长度,否则,我们就要看这个点是处于我左儿子还是右儿子,因为它只可能属于左儿子或者右儿子或者中间,这样我们就可以递归地去找了
我的代码有个地方写的不好,就是每次进行完应该是要把栈pop空的,这个题数据不没卡这个地方,我没pop也AC了

错误及反思:

注意多组。。。

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N =50100;
int lsum[N<<2],rsum[N<<2],msum[N<<2];
int n,k,t;
stack<int> bef;
void pushup(int l,int r,int rt)
{
    int m=(l+r)/2;
    lsum[rt]=lsum[rt<<1];
    rsum[rt]=rsum[rt<<1|1];
    if(lsum[rt<<1]==m-l+1) lsum[rt]+=lsum[rt<<1|1];
    if(rsum[rt<<1|1]==r-m) rsum[rt]+=rsum[rt<<1];
    msum[rt]=max(lsum[rt<<1|1]+rsum[rt<<1],max(msum[rt<<1],msum[rt<<1|1]));
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        lsum[rt]=rsum[rt]=msum[rt]=1;
        return ;
    }
    int m=(l+r)/2;
    build(lson);
    build(rson);
    pushup(l,r,rt);
}
void update(int p,int v,int l,int r,int rt)
{
    if(l==r&&l==p)
    {
        lsum[rt]=rsum[rt]=msum[rt]=v;
        return ;
    }
    int m=(l+r)/2;
    if(p<=m) update(p,v,lson);
    else update(p,v,rson);
    pushup(l,r,rt);
    return ;
}
int query(int p,int l,int r,int rt)
{
    if(msum[rt]==r-l+1||msum[rt]==0||l==r)
        return msum[rt];
    int m=(l+r)/2;
    if(p<=m)
    {
        if(m-rsum[rt<<1]+1<=p) return rsum[rt<<1]+lsum[rt<<1|1];
        return query(p,lson);
    }
    else
    {
        if(m+lsum[rt<<1|1]>=p) return lsum[rt<<1|1]+rsum[rt<<1];
        return query(p,rson);
    }
}
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF){
        build(1,n,1);
        while(k--)
        {
            char temp[10];
            scanf("%s",temp);
            if(temp[0]=='D')
            {
                scanf("%d",&t);
                update(t,0,1,n,1);
                bef.push(t);
            }
            else if(temp[0]=='R'){
                if(bef.size()){
                    update(bef.top(),1,1,n,1);
                    bef.pop();
                }
            }
            else
            {
                scanf("%d",&t);
                printf("%d\n",query(t,1,n,1));
            }   
        }
    }
}
相关标签: 合并