CodeForces - 739C Alyona and towers(线段树)

Posted on | In ,

思路

根据题意，我们需要对一个序列执行区间加和计算最长的递增/递减/先增后减序列。对于区间加法，很自然想到线段树，我们考虑线段树维护序列。我们这样考虑，维护一个区间最左端符合条件序列的长度，维护一个区间最右端符合条件序列的长度。push_up的时候用跨过中点的合法序列，左儿子最大值，右儿子最大值一起考虑来更新最大值。在常规序列处理线段树的情况下，我们会发现我们合并时需要左儿子最右端序列的值和右儿子最左端序列的值（合并左右儿子需要比较大小）。注意在这里我们如果用常规的线段树维护序列，这个时候我们要把lazy的值推到最深的儿子，显然这样lazy操作失去了他的意义，在合并时会导致时间复杂度爆炸。因而我们考虑线段树维护差分序列，这样我们每次只要单点更新两个端点。现在我们可以放心合并不需要担心单点查询复杂度的问题。在合并时，我们要考虑这样几种情况：

  1. 不合法情况，无法用跨过中点的左右两个序列合并来更新节点最大值：右端序列和左/右差分序列有一个为0（左右有一段常数列），左边为-1（递减）右边为1（递增），此时节点的左连续序列就是左儿子的左连续序列，右连续序列就是右儿子的右连续序列，直接上传，最大值继承左右儿子的最大值。
  2. 合法情况：我们更新在继承左右儿子的最大值的基础上再用跨过中点的序列来更新节点的最大值。注意此时的左右连续序列不能想都不想像刚刚那样直接继承，我们考虑这样一个例子，如果左儿子的整个覆盖的区间都是连续递增的，就比如为1，2，3，而此时右儿子是4，5，6。我们显然能发现这个时候区间的左连续序列长度是6而不是3。所以我们需要在左右连续序列的计算上分类讨论。具体细节见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define INTINF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1ll)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b);}
//head

const ll MAXN=300005;
ll arr[MAXN],diff[MAXN];
struct node{
    ll l,r,maxs,lmax,rmax;
}tree[MAXN*4];
ll sign(ll n){
    return n>0?1:n<0?-1:0;
}
void push_up(ll root){
    ll mid=(tree[root].l+tree[root].r)>>1;
    tree[root].maxs=max(tree[root*2].maxs,tree[root*2+1].maxs);
    //situation that can't merge
    if(!diff[mid]||!diff[mid+1]||sign(diff[mid])<sign(diff[mid+1])){
        tree[root].lmax=tree[root*2].lmax;
        tree[root].rmax=tree[root*2+1].rmax;
    }
    else{
        tree[root].maxs=max(tree[root].maxs,tree[root*2].rmax+tree[root*2+1].lmax);
        if(tree[root*2].maxs==tree[root*2].r-tree[root*2].l+1){
            tree[root].lmax=tree[root*2].lmax+tree[root*2+1].lmax;
        }
        else{
            tree[root].lmax=tree[root*2].lmax;
        }
        if(tree[root*2+1].maxs==tree[root*2+1].r-tree[root*2+1].l+1){
            tree[root].rmax=tree[root*2].rmax+tree[root*2+1].rmax;
        }
        else{
            tree[root].rmax=tree[root*2+1].rmax;
        }
    }
}
void build(ll l,ll r,ll root){
    tree[root].l=l,tree[root].r=r;
    if(l==r)tree[root].maxs=tree[root].lmax=tree[root].rmax=diff[l]?1:0;
    else{
        ll mid=(l+r)>>1;
        build(l,mid,root*2);
        build(mid+1,r,root*2+1);
        push_up(root);
    }
}
void update(ll pos,ll val,ll root){
    if(tree[root].l==tree[root].r){
        diff[pos]+=val;
        tree[root].maxs=tree[root].lmax=tree[root].rmax=diff[pos]?1:0;
    }
    else{
        ll mid=(tree[root].l+tree[root].r)>>1;
        if(pos<=mid)update(pos,val,root*2);
        else update(pos,val,root*2+1);
        push_up(root);
    }
}


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif // ONLINE_JUDGE
	ll n,m,l,r,d;
	while(~scanf("%I64d",&n)){
        for(ll i=1;i<=n;i++)scanf("%I64d",&arr[i]);
        for(ll i=1;i<n;i++)diff[i]=arr[i+1]-arr[i];
        if(n>1)build(1,n-1,1);
        scanf("%I64d",&m);
        for(int i=0;i<m;i++){
            scanf("%I64d%I64d%I64d",&l,&r,&d);
            if(n==1){
                puts("1");
                continue;
            }
            if(l>1)update(l-1,d,1);
            if(r<n)update(r,-d,1);
            printf("%I64d\n",tree[1].maxs+1);
        }
	}
    return 0;
}