0

给定一个数组 a[]有n 个非负元素。我们有两种类型的查询：

A xyv : 找到 a[i]>v 的第一个索引 i (x<=i<=y)

B uv :更新a[u]=v;

我使用分段树，但在某些测试中它是 TLE。

这是我的代码。

it max(it A,it B)
{
    it C;
    C.mx=max(A.mx,B.mx);
    return C;
}

这是构建第一棵树的函数。

void build(int id,int l,int r)
{
    if(l==r)
    {
        st[id].mx=a[l];
        st[id].pos=l;
        return;
    }
    int m=l+r>>1;
    build(id<<1,l,m);
    build(id<<1|1,m+1,r);
    st[id]=max(st[id<<1],st[id<<1|1]);
}

更新查询：

void update(int id,int l,int r,int u,int v)
{
    if(u<l||r<u) return;
    if(l==r)
    {
        st[id].mx=v;
        return;
    }
    int m=l+r>>1;
    update(id<<1,l,m,u,v);
    update(id<<1|1,m+1,r,u,v);
    st[id]=max(st[id<<1],st[id<<1|1]);
}

“查找”查询：

int getmin(int id,int l,int r,int u,int v,int value)
{
    if(v<l||r<u) return 1e9;
    if(l==r)
    {
        return st[id].pos;
    }
    int m=l+r>>1;
    //cout<<"->"<<id<<" "<<l<<" "<<r<<endl;
    if(st[id<<1].mx<=value)
    {
        if(st[id<<1|1].mx<=value)
            return 1e9;
        else return getmin(id<<1|1,m+1,r,u,v,value);
    }
    else
    {
        if(st[id<<1|1].mx<=value)
            return getmin(id<<1,l,m,u,v,value);
        else return min(getmin(id<<1,l,m,u,v,value),getmin(id<<1|1,m+1,r,u,v,value));
    }
}
4

1 回答 1

0

您的问题的查询是“查找第一个索引 i”，但您的代码getmin在 [x,y] 中找到了最小值 val > v。

这就是你所期望的？这句话return min(getmin(id<<1,l,m,u,v,value),getmin(id<<1|1,m+1,r,u,v,value))是导致TLE的原因。

如果要查找第一个索引i (x<=i<=y)，a[i]>v请使用下面的代码（取消选中）来获取一个区间内的最大值，而不是使用二进制搜索来查找第一个索引。

int getMax(int id,int l,int r,int x,int y)
{
    if(x <= l && r <= y) return st[id].mx;
    if(l > y || r < x) return -1e9;
    
    int m=l+r>>1;
    return max(getMax(id<<1,l,m,x,y), getMax(id<<1|1,m+1,r,x,y));
}

/* 
 * ROOT is the root of the segtree.
 * L,R are the index bound of segtree.
 * return -1 if no such element.
 * */
int getFirstIndex(int x, int y, int v) {
   
   if(getMax(ROOT, L, R, x, y) <= v) return -1;
   
   int mid = -1;
   while(x <= y) {
       mid = (x + y) >> 1;
       if(getMax(ROOT,L,R,x, mid) > v) {
          y = mid - 1;
       } else{
          x = mid + 1;
       }
   }
   return x;
}
于 2021-08-13T12:33:06.930 回答