刷题记录（NC208250 牛牛的最美味和最不美味的零食）

NC208250 牛牛的最美味和最不美味的零食

题目链接

关键点：

因为题目是将节点将区间去掉，如何表示区间去掉，可以加一个数num表示当前区间里的元素个数。

法一：

区间里的删除节点操作和计算最大最小值的操作，根据当前区间的相对位置来计算

删除节点（删除第x个节点）：

if (tree[2*p].num >= x) dlt(2*p, l, mid, x);//x在左区间
else dlt(2*p+1, mid+1, r, x-tree[p*2].num);

如果左区间的元素个数大于x，说明x在左区间内

如果元素个数小于x，说明x在右区间

查询区间[x, y]（第x个元素到第y个元素）

if (tree[p*2].num>=y)//查询区间均在左孩子
        return find(2*p, l, mid, x, y);
    if (tree[p*2].num//查询区间均在右孩子
        return find(2*p+1, mid+1, r, x-tree[2*p].num, y-tree[2*p].num);//[左区间的开端,左区间结束（相对位置）]
    ty t1 = find(p*2, l, mid, x, tree[2*p].num);
    ty t2 = find(p*2+1, mid+1, r, 1, y-tree[2*p].num);
    t1.maxx = max(t1.maxx, t2.maxx);//只要最低和最高
    t1.minn = min(t1.minn, t2.minn);
    return t1;

如果左区间的元素个数大于y，说明区间[x, y]全在左区间

如果左区间元素个数小于x，说明区间[x, y]全在右区间

否则，[x, y]就包括左右区间，找左区间[x, tree[2*p].num]+右区间[1, y-tree[2*p].num](从1开始)

完整代码：

# include 
using namespace std;
const int N = 1e6+10;
struct ty
{
    int maxx, minn, num;
}tree[N*4];
int n, m;
int a[N];
void build(int p, int l, int r)
{
    if (l == r)
    {
        tree[p].maxx = a[l];
        tree[p].minn = a[l];
        tree[p].num = 1;
        return ;
    }
    int mid = (l+r)/2;
    build(2*p, l, mid);
    build(2*p+1, mid+1, r);
    tree[p].maxx = max(tree[p*2].maxx, tree[2*p+1].maxx);
    tree[p].minn = min(tree[p*2].minn, tree[2*p+1].minn);
    tree[p].num = tree[2*p].num + tree[2*p+1].num;
}
void dlt(int p, int l, int r, int x)
{
    if (l == r)//找到x位置
    {
        tree[p].maxx = -1e9-10;
        tree[p].minn = 1e9+10;
        tree[p].num = 0;
        return ;
    }
    int mid = (l+r)/2;
    if (tree[2*p].num >= x) dlt(2*p, l, mid, x);//x在左区间
    else dlt(2*p+1, mid+1, r, x-tree[p*2].num);
    tree[p].maxx = max(tree[p*2].maxx, tree[2*p+1].maxx);
    tree[p].minn = min(tree[p*2].minn, tree[2*p+1].minn);
    tree[p].num = tree[2*p].num + tree[2*p+1].num;
}
ty find(int p, int l, int r, int x, int y)//（x：当前区间查询区间开端,y:当前区间查询区间开端）
{
    if (x==1 && y==tree[p].num)
    {
        return tree[p];
    }
    int mid = (l+r)/2;
    if (tree[p*2].num>=y)//查询区间均在左孩子
        return find(2*p, l, mid, x, y);
    if (tree[p*2].num//查询区间均在右孩子
        return find(2*p+1, mid+1, r, x-tree[2*p].num, y-tree[2*p].num);//[左区间的开端,左区间结束（相对位置）]
    ty t1 = find(p*2, l, mid, x, tree[2*p].num);
    ty t2 = find(p*2+1, mid+1, r, 1, y-tree[2*p].num);
    t1.maxx = max(t1.maxx, t2.maxx);//只要最低和最高
    t1.minn = min(t1.minn, t2.minn);
    return t1;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i=1; i<=m; i++)
    {
        int k;
        scanf("%d", &k);
        if (k == 1)
        {
            int x;
            scanf("%d", &x);
            dlt(1, 1, n, x);
        }
        else
        {
            int x, y;
            scanf("%d%d", &x, &y);
            ty t;
            t = find(1, 1, n, x, y);
            printf("%d %d\n", t.minn, t.maxx);
        }
    }
    
    
    return 0;
}

法二：

先计算好相对位置，然后就可以正常的按照线段树模板来求

比方说x在线段树的相对位置进行转换

int calc(int p, int l, int r, int x)
{
    if (l == r)
        return l;
    int mid = (l+r)/2;
    if (tree[2*p].num>=x) return calc(2*p, l, mid, x);
    else return calc(2*p+1, mid+1, r, x-tree[2*p].num);
}

转换方法与上述同理

完整代码：

# include 
using namespace std;
const int N = 1e6+10;
struct ty
{
    int maxx, minn, num;
}tree[N*4];
int n, m;
int a[N];
void build(int p, int l, int r)
{
    if (l == r)
    {
        tree[p].maxx = tree[p].minn = a[l];
        tree[p].num = 1;
        return ;
    }
    int mid = (l+r)/2;
    build(2*p, l, mid);
    build(2*p+1, mid+1, r);
    tree[p].maxx = max(tree[p*2].maxx, tree[2*p+1].maxx);
    tree[p].minn = min(tree[p*2].minn, tree[2*p+1].minn);
    tree[p].num = tree[2*p].num + tree[2*p+1].num;
}
void dlt(int p, int l, int r, int x)
{
    if (l == r)//找到x位置
    {
        tree[p].maxx = -1e9-10;
        tree[p].minn = 1e9+10;
        tree[p].num = 0;
        return ;
    }
    int mid = (l+r)/2;
    if (x<=mid) dlt(2*p, l, mid, x);//x在左区间
    else dlt(2*p+1, mid+1, r, x);
    tree[p].maxx = max(tree[p*2].maxx, tree[2*p+1].maxx);
    tree[p].minn = min(tree[p*2].minn, tree[2*p+1].minn);
    tree[p].num = tree[2*p].num + tree[2*p+1].num;
}
ty find(int p, int l, int r, int x, int y)//（x：当前区间查询区间开端,y:当前区间查询区间开端）
{
    if (x==l && r == y)
    {
        return tree[p];
    }
    int mid = (l+r)/2;
    if (y<=mid)//查询区间均在左孩子
        return find(2*p, l, mid, x, y);
    if (x>mid)//查询区间均在右孩子
        return find(2*p+1, mid+1, r, x, y);//[左区间的开端,左区间结束（相对位置）]
    ty t1 = find(p*2, l, mid, x, mid);
    ty t2 = find(p*2+1, mid+1, r, mid+1, y);
    t1.maxx = max(t1.maxx, t2.maxx);//只要最低和最高
    t1.minn = min(t1.minn, t2.minn);
    return t1;
}
int calc(int p, int l, int r, int x)
{
    if (l == r)
        return l;
    int mid = (l+r)/2;
    if (tree[2*p].num>=x) return calc(2*p, l, mid, x);
    else return calc(2*p+1, mid+1, r, x-tree[2*p].num);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i=1; i<=m; i++)
    {
        int k;
        scanf("%d", &k);
        if (k == 1)
        {
            int x;
            scanf("%d", &x);
            int a = calc(1, 1, n, x);
            dlt(1, 1, n, a);
        }
        else
        {
            int x, y;
            scanf("%d%d", &x, &y);
            int a = calc(1, 1, n, x), b = calc(1, 1, n, y);
            ty t;
            t = find(1, 1, n, a, b);
            printf("%d %d\n", t.minn, t.maxx);
        }
    }
    
    
    return 0;
}