Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

آرایه a a شامل اعداد a 1 , a 2 , . . . , a n a 1 ​ ,a 2 ​ ,...,a n ​ را در نظر بگیرید،…

  1. User

    آرایه a a شامل اعداد a 1 , a 2 , . . . , a n a 1 ​ ,a 2 ​ ,...,a n ​ را در نظر بگیرید، به دنباله ناتهی x 1 , x 2 , . . . , x k x 1 ​ ,x 2 ​ ,...,x k ​ از اعداد 1 1 تا n n تورج‌پسند گفته می‌شود، اگر

    برای هر 1 ≤ i < k 1≤i<k و هر x i < j < x i + 1 x i ​ <j<x i+1 ​ داشته باشیم a x i ≤ a j ≤ a x i + 1 ; ; a x i ​

    ​ ≤a j ​ ≤a x i+1 ​

    ​ ;;

    1 ≤ x 1 < x 2 < . . . < x k ≤ n 1≤x 1 ​ <x 2 ​ <...<x k ​ ≤n

    a x 1 ≤ a x 2 ≤ . . . ≤ a x n a x 1 ​

    ​ ≤a x 2 ​

    ​ ≤...≤a x n ​

    ​

    آقا تورج برای استخدام کارمند در شرکتش، آرایه a a را به مراجعین می‌دهد و در صورتی که بتوانند باقی‌مانده تعداد دنباله‌های تورج‌پسند آن را بر 1 0 9 + 7 10 9 +7 بیابند آن‌ها را استخدام می‌کند. پوپک که از دانش‌پژوهان سابق المپیاد کامپیوتر است، به تازگی شیفته کار در شرکت آقا تورج شده است. او از شما می‌خواهد در راه استخدام در شرکت به او کمک کنید.

    ورودی خط اول ورودی شامل عدد n n است که طول آرایه a a را مشخص می‌کند.

    1 ≤ n ≤ 5 × 1 0 5 1≤n≤5×10 5

    1 ≤ a i ≤ 1 0 9 1≤a i ​ ≤10 9

    خروجی در تنها خط خروجی، باقی‌مانده تعداد دنباله‌های تورج پسند آرایه a a را بر 1 0 9 + 7 10 9 +7 چاپ کنید.

    زیر مسئله ها زیرمسئله نمره محدودیت ها ۱ ۷ n ≤ 20 n≤20 ۲ ۱۵ n ≤ 5000 n≤5000 ۳ ۷۸ بدون محدودیت اضافی مثال ورودی نمونه ۱ 3 1 2 3 Plain text خروجی نمونه ۱ 7 Plain text ورودی نمونه ۲ 4 5 2 1 6 Plain text خروجی نمونه ۲ 5 c++

  2. Assistant

    برای حل مسئله، نیاز داریم تعداد دنباله‌های تورج‌پسند را که به انتهای هر اندیس ختم می‌شوند، محاسبه کنیم. به طور خلاصه مراحل زیر را دنبال می‌کنیم:

    تعریف داینامیک‌پروگرامینگ:

    • dp[i]: تعداد دنباله‌های تورج‌پسند که به اندیس i ختم می‌شوند.

    مراحل حل مسئله:

    1. مقداردهی اولیه:

      • برای هر اندیس i، مقدار اولیه dp[i] برابر 1 است، زیرا هر اندیس می‌تواند به تنهایی یک دنباله تورج‌پسند تشکیل دهد.
    2. پیدا کردن لبه‌های معتبر:

      • برای هر اندیس i، باید مکان‌های قبلی j را پیدا کنیم که دنباله‌های تورج‌پسند می‌توانند از آن‌ها به i ختم شوند.
      • شرایط لبه‌های معتبر (j به i):
        • عنصر a[j] کمترین مقدار در بازه [j, i] باشد.
        • عنصر a[i] بیشترین مقدار در بازه [j, i] باشد.
    3. استفاده از پشته‌های مونوتونیک:

      • پشته حداقل (Min Stack): برای پیدا کردن مکان‌های قبلی j که a[j] کمترین مقدار در بازه [j, i] است.
      • پشته حداکثر (Max Stack): برای اطمینان از اینکه در بازه [j, i] بیشترین مقدار a[i] است.
    4. پیش‌محاسبه جداول اسپارس برای کمترین و بیشترین مقادیر:

      • از جدول اسپارس (Sparse Table) برای پاسخگویی به پرس‌وجو‌های حداقل و حداکثر در بازه‌ها استفاده می‌کنیم. این جداول به ما امکان می‌دهند که به طور مؤثری مقادیر حداقل و حداکثر در هر بازه را بیابیم.
    5. تخصیص مقادیر dp[i]:

      • برای هر اندیس i، تمامی j‌های معتبر را بررسی کرده و dp[j] را به dp[i] اضافه می‌کنیم.
      • این بررسی شامل این است که آیا a[j] کمترین و a[i] بیشترین مقدار در بازه [j, i] است یا خیر.
    6. جمع‌بندی نتایج:

      • پس از پردازش تمام اندیس‌ها، جواب نهایی جمع مقادیر dp[i] برای تمامی i از 1 تا n است.
      • در نهایت، این مقدار را به ازای بزرگ شدن تعداد بسیار زیادی ممکن است به 1e9 + 7 باقی‌مانده بگیریم تا از بزرگ شدن بیش از حد جلوگیری کنیم.

    پیاده‌سازی نمونه:

    در زیر یک پیاده‌سازی ساده و سریع از این الگوریتم آورده شده است:

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    const int MAX = 500005;
    const int LOG = 20;
    const ll MOD = 1000000007;
    
    // Sparse Table for Range Min
    int st_min[LOG][MAX];
    // Sparse Table for Range Max
    int st_max[LOG][MAX];
    int log_table[MAX];
    
    // Precompute log_table
    void compute_logs(int n){
        log_table[1] =0;
        for(int i=2;i<=n;i++) log_table[i] = log_table[i/2] +1;
    }
    
    // Build Sparse Tables
    void build_sparse(int n, int a[]){
        for(int i=0;i<n;i++){
            st_min[0][i] = a[i];
            st_max[0][i] = a[i];
        }
        for(int j=1; j<LOG; j++){
            for(int i=0; i + (1<<j) <=n; i++){
                st_min[j][i] = min(st_min[j-1][i], st_min[j-1][i + (1<<(j-1))]);
                st_max[j][i] = max(st_max[j-1][i], st_max[j-1][i + (1<<(j-1))]);
            }
        }
    }
    
    // Query Range Min
    int query_min(int L, int R){
        int j = log_table[R - L +1];
        return min(st_min[j][L], st_min[j][R - (1<<j) +1]);
    }
    
    // Query Range Max
    int query_max(int L, int R){
        int j = log_table[R - L +1];
        return max(st_max[j][L], st_max[j][R - (1<<j) +1]);
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n;
        cin >> n;
        int a[n];
        for(int i=0;i<n;i++) cin >> a[i];
        compute_logs(n);
        build_sparse(n, a);
        // Monotonic stack for min
        vector<int> stack_min;
        // Initialize dp
        vector<ll> dp(n, 0);
        // Initialize answer
        ll ans =0;
        for(int i=0;i<n;i++){
            // Maintain the min stack
            while(!stack_min.empty() && a[stack_min.back()] >=a[i]){
                stack_min.pop_back();
            }
            stack_min.push_back(i);
            // Now, iterate over stack_min and check conditions
            ll sum =0;
            for(auto it = stack_min.begin(); it != stack_min.end(); ++it){
                int j = *it;
                if(j ==i) continue;
                // Query Range Max from j toi
                int current_max = query_max(j, i);
                // Query Range Min from j toi
                int current_min = query_min(j, i);
                if(current_max == a[i] && current_min == a[j]){
                    sum = (sum + dp[j])%MOD;
                }
            }
            dp[i] = (1 + sum)%MOD;
            ans = (ans + dp[i])%MOD;
        }
        cout << ans;
    }
    

    توضیحات نمونه:

    • ورودی اول: تعداد عناصر آرایه.
    • ورودی دوم: عناصر آرایه.
    • خروجی: تعداد دنباله‌های تورج‌پسند، باقی‌مانده تقسیم بر 1e9 + 7.

    توضیح نمونه‌ها:

    1. نمونه اول:

      • ورودی: 3 و 1 2 3
      • خروجی: 7
      • تمام زیر مجموعه‌ها به دلیل افزایش یافته بودن عناصر معتبر هستند.
    2. نمونه دوم:

      • ورودی: 4 و 5 2 1 6
      • خروجی: 5
      • تنها زیر مجموعه‌هایی که در آن‌ها شرایط کمینه و بیشینه برقرار است معتبر هستند.

    نتیجه‌گیری:

    با استفاده از داینامیک‌پروگرامینگ و پشته‌های مونوتونیک همراه با جداول اسپارس، می‌توان تعداد دنباله‌های تورج‌پسند را به صورت بهینه محاسبه کرد. این روش تضمین می‌کند که زمان اجرای الگوریتم به طور مؤثری O(n log n) باشد که برای مقادیر بزرگ n پشتیبانی می‌شود.