JZOJ4975. 区间

2019-11-08 02:03:11

字体：大中小

来源：转载

供稿：网友

题目大意

给定一个长度为n $n$ 的排列。求有多少个连续的数字区间[l,r] $[l,r]$ 可以拆成排列中的两个不同区间内的权值并。

Data Constraint n≤3×105 $n/leq3/times10^5$

题解

设f[i][j] $f[i][j]$ 表示权值区间为[i,j] $[i,j]$ 在原序列中至少要拆多少个区间。考虑从小到大枚举j $j$ ，设j $j$ 在P $P$ 中的位置为x $x$ ，那么当前对于i≤P[x−1]且i≤P[x+1] $i/leq P[x-1]且i/leq P[x+1]$ 的f $f$ 都要-1，只小于其中一个的f $f$ 不变，其余f $f$ +1。线段树维护即可。

时间复杂度：O(nlogn) $O(nlogn)$

SRC

#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std ;#define N 300000 + 10typedef long long ll ;struct Tree { int tag ; int Min1 , Min2 ; int Num1 , Num2 ;} T[4*N] ;int P[N] , Q[N] ;int n ;ll ans , ret ;int min( int x , int y ) { return x < y ? x : y ; }int max( int x , int y ) { return x > y ? x : y ; }void Update( int v ) { if ( !T[v].tag ) return ; int lv = v + v , rv = v + v + 1 ; T[lv].Min1 += T[v].tag ; T[lv].Min2 += T[v].tag ; T[rv].Min1 += T[v].tag ; T[rv].Min2 += T[v].tag ; T[lv].tag += T[v].tag ; T[rv].tag += T[v].tag ; T[v].tag = 0 ;}void Merge( int v ) { int lv = v + v , rv = v + v + 1 ; T[v].Min1 = min( T[lv].Min1 , T[rv].Min1 ) ; int tp = 0x7FFFFFFF ; if ( T[lv].Min1 > T[v].Min1 ) tp = min( tp , T[lv].Min1 ) ; if ( T[lv].Min2 > T[v].Min1 ) tp = min( tp , T[lv].Min2 ) ; if ( T[rv].Min1 > T[v].Min1 ) tp = min( tp , T[rv].Min1 ) ; if ( T[rv].Min2 > T[v].Min1 ) tp = min( tp , T[rv].Min2 ) ; T[v].Min2 = tp ; T[v].Num1 = T[v].Num2 = 0 ; T[v].Num1 += T[lv].Min1 == T[v].Min1 ? T[lv].Num1 : 0 ; T[v].Num1 += T[rv].Min1 == T[v].Min1 ? T[rv].Num1 : 0 ; T[v].Num2 += T[lv].Min1 == T[v].Min2 ? T[lv].Num1 : 0 ; T[v].Num2 += T[lv].Min2 == T[v].Min2 ? T[lv].Num2 : 0 ; T[v].Num2 += T[rv].Min1 == T[v].Min2 ? T[rv].Num1 : 0 ; T[v].Num2 += T[rv].Min2 == T[v].Min2 ? T[rv].Num2 : 0 ;}void Modify( int v , int l , int r , int x , int y , int del ) { if ( x > y ) return ; if ( l == x && r == y ) { T[v].Min1 += del , T[v].Min2 += del ; T[v].tag += del ; return ; } Update(v) ; int mid = (l + r) >> 1 ; if ( y <= mid ) Modify( v + v , l , mid , x , y , del ) ; else if ( x > mid ) Modify( v + v + 1 , mid + 1 , r , x , y , del ) ; else { Modify( v + v , l , mid , x , mid , del ) ; Modify( v + v + 1 , mid + 1 , r , mid + 1 , y , del ) ; } Merge(v) ;}void Search( int v , int l , int r , int x , int y ) { if ( l == x && r == y ) { ret += T[v].Min1 <= 2 ? T[v].Num1 : 0 ; ret += T[v].Min2 <= 2 ? T[v].Num2 : 0 ; return ; } Update(v) ; int mid = (l + r) >> 1 ; if ( y <= mid ) Search( v + v , l , mid , x , y ) ; else if ( x > mid ) Search( v + v + 1 , mid + 1 , r , x , y ) ; else { Search( v + v , l , mid , x , mid ) ; Search( v + v + 1 , mid + 1 , r , mid + 1 , y ) ; } Merge(v) ;}void MakeTree( int v , int l , int r ) { T[v].Num1 = r - l + 1 ; if ( l == r ) return ; int mid = (l + r) >> 1 ; MakeTree( v + v , l , mid ) ; MakeTree( v + v + 1 , mid + 1 , r ) ;}int main() { scanf( "%d" , &n ) ; for (int i = 1 ; i <= n ; i ++ ) { scanf( "%d" , &P[i] ) ; Q[P[i]] = i ; } P[0] = P[n+1] = n + 1 ; MakeTree( 1 , 1 , n ) ; for (int i = 1 ; i <= n ; ++ i ) { int x = Q[i] ; Modify( 1 , 1 , n , 1 , i , 1 ) ; if ( P[x-1] < i ) Modify( 1 , 1 , n , 1 , P[x-1] , -1 ) ; if ( P[x+1] < i ) Modify( 1 , 1 , n , 1 , P[x+1] , -1 ) ; ret = 0 ; Search( 1 , 1 , n , 1 , i ) ; ans += ret ; } PRintf( "%lld/n" , ans - n ) ; return 0 ;}

以上.

上一篇：取bei16倍数字节方法

下一篇：非常好的在网页中显示pdf的方法