题目大意

给定一个长度为 n 的序列a和 m 个操作，每个操作将[L,R]的元素加上 d 。 每次操作完后询问序列a中最长的连续子序列满足 al<al+1<...<ax>...>ar−1>ar 的长度是多少。

Data Constraint n,m≤3×105

题解

因为只有区间加操作，所以可以考虑先差分一下。 然后区间加就转化为单点修改操作。询问就是找最长的一段满足前面连续一段是负的，剩余全是正的。这个可以用线段树维护区间信息（维护区间前缀答案和后缀答案然后Merge）来解决。

时间复杂度： O(mlogn)

SRC

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std ; #define N 300000 + 10 typedef long long ll ; struct Note { int Pre , Las , lans , rans , ans , len ; } T[4*N] ; ll a[N] , b[N] ; int n , m ; Note Merge( Note a , Note b ) { Note ret ; ret.len = a.len + b.len ; ret.Pre = a.Pre ; if ( a.Pre == a.len ) ret.Pre += b.Pre ; ret.Las = b.Las ; if ( b.Las == b.len ) ret.Las += a.Las ; ret.lans = a.lans ; if ( a.lans == a.len ) { if ( a.Las == a.len ) ret.lans += max( b.lans , b.Pre ) ; else ret.lans += b.Pre ; } ret.rans = b.rans ; if ( b.rans == b.len ) { if ( b.Pre == b.len ) ret.rans += max( a.rans , a.Las ) ; else ret.rans += a.Las ; } ret.ans = max( a.ans , b.ans ) ; ret.ans = max( ret.ans , max( ret.lans , ret.rans ) ) ; ret.ans = max( ret.ans , max( a.rans + ( a.Las ? max( b.lans , b.Pre ) : b.Pre ) , b.lans + ( b.Pre ? max( a.rans , a.Las ) : a.Las ) ) ) ; return ret ; } void Update( int v ) { int ls = v + v , rs = v + v + 1 ; T[v] = Merge( T[ls] , T[rs] ) ; return ; } void Build( int v , int l , int r ) { if ( l == r ) { if ( b[l] < 0 ) T[v].Pre = 1 ; else if ( b[l] > 0 ) T[v].Las = 1 ; if ( b[l] != 0 ) T[v].lans = T[v].rans = T[v].ans = 1 ; T[v].len = 1 ; return ; } int mid = (l + r) / 2 ; Build( v + v , l , mid ) ; Build( v + v + 1 , mid + 1 , r ) ; Update( v ) ; } void Modify( int v , int l , int r , int x , int del ) { if ( l == x && r == x ) { b[x] += del ; T[v].Pre = T[v].Las = T[v].lans = T[v].rans = T[v].ans = 0 ; if ( b[l] < 0 ) T[v].Pre = 1 ; else if ( b[l] > 0 ) T[v].Las = 1 ; if ( b[l] != 0 ) T[v].lans = T[v].rans = T[v].ans = 1 ; return ; } int mid = (l + r) / 2 ; if ( x <= mid ) Modify( v + v , l , mid , x , del ) ; else Modify( v + v + 1 , mid + 1 , r , x , del ) ; Update( v ) ; } int main() { scanf( "%d" , &n ) ; for (int i = 1 ; i <= n ; i ++ ) cin >> a[i] ; a[0] = a[1] ; for (int i = 1 ; i <= n ; i ++ ) b[i] = a[i] - a[i-1] ; Build( 1 , 1 , n ) ; scanf( "%d" , &m ) ; for (int i = 1 ; i <= m ; i ++ ) { int l , r , del ; scanf( "%d%d%d" , &l , &r , &del ) ; if ( l > 1 ) Modify( 1 , 1 , n , l , del ) ; if ( r < n ) Modify( 1 , 1 , n , r + 1 , -del ) ; printf( "%d\n" , T[1].ans + 1 ) ; } return 0 ; }

以上.