CodeForces - 597 C. Subsequences(dp+ 세그먼트 트리 or 트리 배열 최적화)

8190 단어 dp라인 트리 & 트리 그룹 & 주석 트리
For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·1018.
Input First line contain two integer values n and k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.
Next n lines contains one integer ai (1 ≤ ai ≤ n) each — elements of sequence. All values ai are different.
Output Print one integer — the answer to the problem.
Examples input 5 2 1 2 3 5 4 output 7
대체적인 제목: n개의 다른 수 범위 1에서 n을 알려주고 몇 개의 길이가 k+1의 증가 수열인지 통계해 보세요.
사고방식: 쉽게 생각할 수 있는 dp방정식: dp[num[i][len]=sum(dp[num[j]][len-1])(jnum[j], 1<=len<=k+1)이지만 이런 이동 시간은 O(n)이고 전체 시간 복잡도는 O(k*n^2)로 gg를 긍정한다.그래서 우리는 어떻게 이동을 최적화시킬 것인가를 고려한다.여기는 교묘하게 라인 트리를 사용했다.우리는 이 n개의 수를 아래로 표시하여 k+1개의 라인 트리를 만들고 입력의 선후 순서에 따라 num을 입력할 때우리는logn의 시간 내에 dp{num][len]의 값을 구할 수 있다. 즉,len-1그루의 나무에서 구간 1에서num-1의 합을 조회한 다음에 구한 값으로 제len그루의 나무 위아래에서num의 위치의 값을 업데이트할 수 있다. 마지막으로 k+1그루의 나무 중 구간 1에서 n의 합을 조회하면 된다. 이렇게 하면 시간의 복잡도는 O(k*nlogn)로 떨어진다.
코드는 다음과 같다.
코드 1.
/*
   
*/
#include 
#include   
#define ll long long int  
#define lson l,m,rt<<1  
#define rson m+1,r,rt<<1|1  
using namespace std;
const int M=1e5+5; 
ll dp[M<<2][15];  
int f;
inline void PushPlus(int rt)  
{   
    dp[rt][f] = dp[rt<<1][f]+dp[rt<<1|1][f]; 
}  
void Updata(int p,ll change, int l, int r, int rt)//    ,p        change 
{  

    if( l == r )  
    {   
        dp[rt][f]=change;
        return ;  
    }  

    int m = ( l + r ) >> 1;  
    if(p <= m)  
        Updata(p, change, lson);  
    else  
        Updata(p, change, rson);  

    PushPlus(rt);  
}  

ll Query(int L,int R,int l,int r,int rt)  
{  
    if(L>R)
    return 0;
    if( L <= l && r <= R )  
    {  
        return dp[rt][f];  
    }  
    int m = ( l + r ) >> 1;  

    ll ans=0;  
    if(L<=m )  
        ans+=Query(L,R,lson);  
    if(R>m)  
        ans+=Query(L,R,rson);  
    return ans;  
}  

int main()  
{     
        int n,k; 
        int A;
        scanf("%d%d",&n,&k);
        k++;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&A);
            for(int j=1;j<=k;j++)
            {

                f=j;
                f--;
                ll ans;
                if(f==0)
                ans=1;
                else 
                ans=Query(1,A-1,1,n,1); 
                f++;
                Updata(A,ans,1,n,1);//    ,A      ans
            }
        }
        f=k;
        printf("%I64d
",Query(1,n,1,n,1));

    return 0;  
}

코드 2.
/*
    
emmm      ，        ，             
*/
#include 
#include 
#include   
#include   
#define ll long long int  
using namespace std;  
const int N=100005;
ll dp[N][15];
int f;
int n,k;
int lowbit(int x)
{
    return x&-x;
}

ll sum(int x)
{
    ll s=0;
    while(x>0)
    {
        s+=dp[x][f];
        x=x-lowbit(x);
    }
    return s;
}

void add(int x,ll date)
{
    while(x<=n)
    {
        dp[x][f]+=date;
        x=x+lowbit(x);
    }
}

int main()  
{
    int A;
    scanf("%d%d",&n,&k);
    k++;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&A);
        for(int j=1;j<=k;j++)
        {
            ll ans;
            f=j;
            f--;
            if(f==0)
                ans=1;
            else 
                ans=sum(A-1);
            f++;    
            add(A,ans);

        }   
    }

    f=k;
    printf("%I64d
",sum(n));
    return 0;  
}
최근 화제가 된 분산형 대장 Scar DLT(기초편)를 조사했습니다.
부족 한 js 예 를 찾 습 니 다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage