HDU 6406 Taotao Picks Apples (线段树)

题目链接 给出一个数列，要求每次单点更新后查询从1开始的严格上升子序列长度。

考虑到严格上升子序列所具有的单调性，我们可以用一棵线段树来维护区间最大值，然后通过相邻区间的最大值关系来确定严格递增序列的长度。

在维护一个区间的时候，显然它的左儿子和右儿子都有一个贡献。如果前一个数比后一个数要大，后一个数显然是不会产生贡献的。因此，一个区间的贡献应该至少是它左儿子的贡献。而对于右儿子产生的贡献，可以分类讨论。

设v为查询时的最大值，如果左儿子区间的最大值不超过v，那么整个区间的贡献就只需要查询右儿子的贡献。否则，就直接在右儿子贡献的基础上再递归地查询此状态下左儿子的贡献。

注意每次更新查询后，要将数组恢复原状。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 100050;
const ll INF = (1LL << 62) - 1;
const double eps = 1e-8;

int t, n, m, p, x, w[maxn];
struct node
{
    int cnt;
    int val;
}tree[maxn << 2];

int query(int root, int l, int r, int v)
{
    if(l == r) return (tree[root].val > v);
    if(tree[root].val <= v) return 0;
    int mid = (l + r) >> 1;
    if(tree[root*2].val <= v) return query(root*2 + 1, mid + 1, r, v);
    else return tree[root].cnt - tree[root*2].cnt + query(root*2, l, mid, v);
}

void build(int root, int l, int r)
{
    if(l == r)
    {
        tree[root].cnt = 1;
        tree[root].val = w[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(root*2, l, mid);
    build(roort*2 + 1, mid + 1, r);
    tree[root].cnt = tree[root*2].cnt + query(root*2 + 1, mid + 1, r, tree[root*2].val);
    tree[root].val = max(tree[root*2].val, tree[root*2 + 1].val);
}

void update(int root, int l, int r, int aim, int x)
{
    if(l == r)
    {
        tree[root].cnt = 1;
        tree[root].val = x;
        return;
    }
    int mid = (l + r) >> 1;
    if(aim <= mid) update(root*2, l, mid, aim, x);
    else update(root*2 + 1, mid + 1, r, aim, x);
    tree[root].cnt = tree[root*2].cnt + query(root*2 + 1, mid + 1, r, tree[root*2].val);
    tree[root].val = max(tree[root*2].val, tree[root*2 + 1].val);
}

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1;i <= n;i++)
            scanf("%d", &w[i]);
        build(1, 1, n);
        for(int i = 1;i <= m;i++)
        {
            scanf("%d%d", &p, &x);
            update(1, 1, n, p, x);
            printf("%d\n", tree[1].cnt);
            update(1, 1, n, p, w[p]);
        }
    }
    return 0;
}