題目：

?

這個題目竟然叫中國好區(qū)間，要不要臉。欸，不得不說還蠻順口的，哈哈哈。

?

首先我們有一個數(shù)組a。可以遞推得來，O(n)時間復(fù)雜度。

?

定義left（有效區(qū)間的左端點(diǎn)），bigger（有效區(qū)間中大于等于T的數(shù)的數(shù)量）。

有效區(qū)間：a[left]~a[i]，好區(qū)間：保持區(qū)間中有k個 >= T 的值。

好區(qū)間的數(shù)量：ans。

?

思路：

如果現(xiàn)在到了第i個值a[i]。

可能有以下四種情況。

1.bigger >= k && a[i] >= T

　　　　　　bigger++，將left右移至有效區(qū)間中只有k個>=T的數(shù)，且a[left] >= T 。ans += left。（因為a[j]~a[i]( 1 <= j <= left)共left個全是好區(qū)間）

2.bigger >= k && a[i] < T　　

　　　　　　ans += left。理由同上。

3.bigger < k && a[i] >= T　　

　　　　　　bigger++，{如果bigger==k(有效區(qū)間中大于等于T數(shù)量為k，正好成為好區(qū)間)，將left右移至a[left] >= T。 ans+= left。理由同上。}

4.bigger < k && a[i] < T

　　　　　　不做處理，因為bigger,left,ans都沒變。

?

?

代碼：

#include <bits\stdc++.h> using namespace std; typedef long long ll;ll n,k,T,b,c,p; ll a[10000001]; int main(){cin >> n >> k >> T >> a[0] >> b >> c >> p;int bigger = 0;int left = 1;ll ans = 0;for(int i = 1;i <= n; i++){a[i] = (a[i-1]*b+c)%p; // cout << a[i] << " ";if(bigger >= k){if(a[i] >= T){bigger++;int c = 1; for(int j = left;j <= i; j++){if(a[j] < T){ left++;continue;}else if(c > 0){ left++,c--;continue; }break;}ans += left;}else{ans += left;} }else{if(a[i] >= T){bigger++;if(bigger == k){for(int j = left;j <= i; j++){if(a[j] < T){ left++;continue;}break;}ans += left;}}} // cout << ans << endl; }cout << ans << endl;return 0; } //writed by zhangjiuding

?

總結(jié)

以上是生活随笔為你收集整理的51 nod 1495 中国好区间 奇葩卡时间题 700ms 卡O(n*log(n)), 思路：O(n)尺取法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。