آرایه a a شامل اعداد a 1 , a 2 , . . . , a n a 1 ,a 2 ,...,a n را در نظر بگیرید،…
- 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++
- Assistant
برای حل مسئله، نیاز داریم تعداد دنبالههای تورجپسند را که به انتهای هر اندیس ختم میشوند، محاسبه کنیم. به طور خلاصه مراحل زیر را دنبال میکنیم:
تعریف داینامیکپروگرامینگ:
- dp[i]: تعداد دنبالههای تورجپسند که به اندیس i ختم میشوند.
مراحل حل مسئله:
-
مقداردهی اولیه:
- برای هر اندیس i، مقدار اولیه dp[i] برابر 1 است، زیرا هر اندیس میتواند به تنهایی یک دنباله تورجپسند تشکیل دهد.
-
پیدا کردن لبههای معتبر:
- برای هر اندیس i، باید مکانهای قبلی j را پیدا کنیم که دنبالههای تورجپسند میتوانند از آنها به i ختم شوند.
- شرایط لبههای معتبر (j به i):
- عنصر a[j] کمترین مقدار در بازه [j, i] باشد.
- عنصر a[i] بیشترین مقدار در بازه [j, i] باشد.
-
استفاده از پشتههای مونوتونیک:
- پشته حداقل (Min Stack): برای پیدا کردن مکانهای قبلی j که a[j] کمترین مقدار در بازه [j, i] است.
- پشته حداکثر (Max Stack): برای اطمینان از اینکه در بازه [j, i] بیشترین مقدار a[i] است.
-
پیشمحاسبه جداول اسپارس برای کمترین و بیشترین مقادیر:
- از جدول اسپارس (Sparse Table) برای پاسخگویی به پرسوجوهای حداقل و حداکثر در بازهها استفاده میکنیم. این جداول به ما امکان میدهند که به طور مؤثری مقادیر حداقل و حداکثر در هر بازه را بیابیم.
-
تخصیص مقادیر dp[i]:
- برای هر اندیس i، تمامی jهای معتبر را بررسی کرده و dp[j] را به dp[i] اضافه میکنیم.
- این بررسی شامل این است که آیا a[j] کمترین و a[i] بیشترین مقدار در بازه [j, i] است یا خیر.
-
جمعبندی نتایج:
- پس از پردازش تمام اندیسها، جواب نهایی جمع مقادیر 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.
توضیح نمونهها:
-
نمونه اول:
- ورودی:
3و1 2 3 - خروجی:
7 - تمام زیر مجموعهها به دلیل افزایش یافته بودن عناصر معتبر هستند.
- ورودی:
-
نمونه دوم:
- ورودی:
4و5 2 1 6 - خروجی:
5 - تنها زیر مجموعههایی که در آنها شرایط کمینه و بیشینه برقرار است معتبر هستند.
- ورودی:
نتیجهگیری:
با استفاده از داینامیکپروگرامینگ و پشتههای مونوتونیک همراه با جداول اسپارس، میتوان تعداد دنبالههای تورجپسند را به صورت بهینه محاسبه کرد. این روش تضمین میکند که زمان اجرای الگوریتم به طور مؤثری O(n log n) باشد که برای مقادیر بزرگ n پشتیبانی میشود.