HDU 2836 Traversal Simple DP + 트리 배열

제목: 두 수의 높이 차이와 절대값이 H보다 작은 서열이 몇 개인지 서열을 하나 드릴게요.
dp[i]는 i를 끝으로 하는 하위 서열이 얼마나 되는지 나타낸다. 알기 쉬운 상태 이동 방정식은 dp[i]=sum(dp[j])+1이다.( abs( height[i] - height[j] ) <= H )
abs(height[i] - height[j]) <= H에서 height[i] - H <= height[j] <= height[i] + H
서열의 수를 이산화하고 각 하이라이트는 하나의 id에 대응하며 트리 그룹으로 구간 [height[i]-H의 id, height[i]+H의 id] 내 dp[j]의 합을 구하고 새로 얻은 dp[i]를 트리 그룹에서 하이라이트[i]의 id에 대응하는 위치로 업데이트합니다.
 

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <cstdlib>

 4 #include <algorithm>

 5 

 6 using namespace std;

 7 

 8 const int MAXN = 100100;

 9 const int MOD = 9901;

10 

11 int dp[MAXN];

12 int height[MAXN];

13 int num[MAXN];

14 int C[MAXN];

15 int n, d;

16 

17 int lowbit( int x )

18 {

19     return x & ( -x );

20 }

21 

22 int Query( int x )

23 {

24     int res = 0;

25     while ( x > 0 )

26     {

27         res += C[x];

28         res %= MOD;

29         x -= lowbit(x);

30     }

31     return res;

32 }

33 

34 void Add( int x, int v )

35 {

36     while ( x <= n )

37     {

38         C[x] += v;

39         C[x] %= MOD;

40         x += lowbit(x);

41     }

42     return;

43 }

44 

45 int main()

46 {

47     while ( ~scanf( "%d%d", &n, &d ) )

48     {

49         for ( int i = 1; i <= n; ++i )

50         {

51             scanf( "%d", &height[i] );

52             num[i] = height[i];

53         }

54 

55         sort( num + 1, num + n + 1 );

56         int cnt = unique( num + 1, num + n + 1 ) - num - 1;

57 

58         memset( C, 0, sizeof(C) );

59         int ans = 0;

60         dp[0] = 0;

61         for ( int i = 1; i <= n; ++i )

62         {

63             int id = lower_bound( num + 1, num + cnt + 1, height[i] ) - num;

64             int left = lower_bound( num + 1, num + cnt + 1, height[i] - d ) - num;

65             int right = upper_bound( num + 1, num + cnt + 1, height[i] + d ) - num - 1;

66             dp[i] = ( Query( right ) - Query( left - 1 ) + 1 ) % MOD;

67             ans += dp[i];

68             Add( id, dp[i] );

69         }

70 

71         if ( ans >= n ) ans -= n;

72         else ans = 0;

73         printf("%d
", ans % MOD );

74     }

75     return 0;

76 }