hdu 6406 Taotao Picks Apples 线段树单点更新 Taotao Picks Apples

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2506 Accepted Submission(s): 786

Problem Description

There is an apple tree in front of Taotao's house. When autumn comes,

). Can you answer all these queries?

Input

The first line of input is a single line of integer

, as described in the problem statement.

Output

For each query, display the answer in a single line.

给你长度为n的序列，然后从位置1，寻找单调栈的最大长度

然后修改 v[pos] = val, 再求单调栈的最大长度

但是队友说是单调栈，我就用线段树维护了个单调栈，但是我维护的好像有些SB，就是每次左区间的最大值+（用单调栈跑一次最大长度）

然后完美的T了，然后就没管这道题了

后来看了一个人的题解，是这样子分析的

对于每一个区间，贡献只能从左区间 + 右区间的部分选择

然后考虑：两种情况，如果右区间的最大值 <= 左区间最大值，那么右区间肯定没有贡献，为0

然后考虑：如果右区间的最大值 > 左区间最大值,那么问题可以递归右区间的左儿子和右儿子的情况

这样的复杂度大概是T*m*logn*logn （单点更新val值一个log 然后每次合并区间的时候又要一个log）

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
#define ls rt<<1
#define rs rt<<1|1

int mx[N<<2],cnt[N<<2];

int query(int rt,int l,int r,int v) {
    if(l==r) return mx[rt] > v;
    if(mx[rt] <= v) return 0;
    int m = (l+r)>>1;
    if(mx[ls] <= v) return query(rs,m+1,r,v);
    else return cnt[rt]-cnt[ls]+query(ls,l,m,v);
}
int n,m,v[N];
void build(int rt,int l,int r) {
    mx[rt] = cnt[rt] =0;
    if(l == r) {
        mx[rt]=v[l]; cnt[rt]=1;
        return ;
    }
    int m=(l+r)>>1;
    build(ls,l,m);
    build(rs,m+1,r);
    mx[rt]=max(mx[ls], mx[rs]);
    cnt[rt] = cnt[ls] + query(rs,m+1,r,mx[ls]);
}

void update(int rt,int l,int r,int pos,int val) {
    if(l==r && l == pos) {
        mx[rt]=val;
        cnt[rt] = 1;
        return ;
    }
    int m = (l+r)>>1;
    if(pos <= m)
        update(ls,l,m,pos,val);
    else
        update(rs,m+1,r,pos,val);
    mx[rt]=max(mx[ls], mx[rs]);
    cnt[rt] = cnt[ls] + query(rs,m+1,r,mx[ls]);
}

int main() {
    //freopen("in.txt","r",stdin);
    int T; scanf("%d",&T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for(int i=1;i<=n;i++)
            scanf("%d",&v[i]);
        build(1,1,n);
        while (m--) {
            int pos, val;
            scanf("%d %d",&pos,&val);
            //pos位置 更新成val
            update(1,1,n,pos,val);
            printf("%d
",cnt[1]);
            //还原
            update(1,1,n,pos,v[pos]);
        }
    }
    return 0;
}

hdu 6406 Taotao Picks Apples 线段树 单点更新 Taotao Picks Apples

相关推荐

hdu 6406 Taotao Picks Apples 线段树单点更新 Taotao Picks Apples