hdu6406 Taotao Picks Apples（线段树）

Taotao Picks Apples

题目传送门

解题思路

建立一颗线段树，维护当前区间内的最大值maxx和可摘取的苹果数num。最大值很容易维护，主要是可摘取的苹果数怎么合并。合并左右孩子时，左孩子里可摘取苹果必然还是可以摘取，所以我们讨论右孩子。

如果右孩子的最大值小于左孩子，根据题目条件，右孩子里的苹果都不能摘取了，合并结果就是左孩子的数量，如果右孩子的最大值大于左孩子，那么右孩子里存在可以摘取的苹果，接下来就是一个递归的过程，假设右孩子为t，左孩子的最大值为k，如果t->lchild->maxx < k, 那么t->lchild中不存在可摘取的苹果，递归t->rchild求t->rchild中的数量，如果t->lchild->maxx > k，那么t->lchild和t->rchild中都存在可摘取的苹果，而此时t->rchild已经不受k的影响了，只受t->lchild->maxx的影响，所以可以直接加上t->rchild->num,再加上递归求出的t->lchild中的数量。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int read(){

    int res = 0, w = 0; char ch = 0;

    while(!isdigit(ch)){

        w |= ch == '-', ch = getchar();

    }

    while(isdigit(ch)){

        res = (res << 3) + (res << 1) + (ch ^ 48);

        ch = getchar();

    }

    return w ? -res : res;

}

const int N = 100005;

int v[N];

struct node{

    int l, r;

    int maxx, num;

}tree[N << 2];

int get(int k, int x)  //递归过程

{

    if(tree[k].num == 1){

        return tree[k].maxx > x;

    }

    if(tree[2*k].maxx > x)

        return get(2*k, x) + (tree[k].num - tree[2*k].num);

    else if(tree[2*k].maxx == x)

        return tree[k].num - tree[2*k].num;

    else

        return get(2*k+1, x);

}

void pushup(int k)  //合并

{

    tree[k].maxx = max(tree[2*k].maxx, tree[2*k+1].maxx);

    tree[k].num = tree[2*k].num;

    if(tree[2*k+1].maxx > tree[2*k].maxx)

        tree[k].num += get(2*k+1, tree[2*k].maxx);

}

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

{

    tree[k].l = l, tree[k].r = r;

    if(l == r){

        tree[k].maxx = v[l];

        tree[k].num = 1;

        return;

    }

    int mid = (l + r) / 2;

    build(2*k, l, mid);

    build(2*k+1, mid+1, r);

    pushup(k);

}

void update(int k, int p, int q)

{

    if(tree[k].l == tree[k].r){

        tree[k].maxx = q;

        return;

    }

    int mid = (tree[k].l + tree[k].r) / 2;

    if(p <= mid)

        update(2*k, p, q);

    else

        update(2*k+1, p, q);

    pushup(k);

}

inline int query()

{

    return tree[1].num;

}

int main()

{

    int t;

    cin >> t;

    while(t --){

        int n, m;

        n = read(), m = read();

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

            v[i] = read();

        build(1, 1, n);

        for(int i = 1; i <= m; i ++){

            int p, q;

            p = read(), q = read();

            update(1, p, q);

            printf("%d\n", query());

            update(1, p, v[p]);

        }

    }

    return 0;

}