HDU – 6319 Ascending Rating 【單調佇列 逆向思維】

NO IMAGE

傳送門
題目大意: 給定一個序列 a[1..n],對於每個長度為 m 的連續子區間,求出區間 a 的最大值以及從左往右掃描該區間時 a 的最大值的變化次數

思路: 首先最大值很好維護, 主要是count是難點, 所以我們考慮下逆向做, 那麼對於一個區間的開始. 後面比它小的都被剔除了. 所以剩下的就是從左往右掃的最大值變化次數,,,, 這樣做以後就非常簡單了, 複雜度O(n)

AC Code

const int maxn = 1e7 5;
int n, m, k, p, q, r, md;
ll ans1, ans2;
int a[maxn], que[maxn];
int head, tail;
void solve() {
scanf("%d%d%d%d%d%d%d", &n, &m, &k, &p, &q, &r, &md);
for (int i = 1 ; i <= k ; i   ) scanf("%d", a i);
for (int i = k   1 ; i <= n ; i   ) {
a[i] = (1ll*p*a[i-1]   1ll*q*i   1ll*r) % md;
}
ans1 = ans2 = tail = 0; head = 1;
for (int i = n ; i >= 1 ; i --) {
while(head <= tail && a[que[tail]] <= a[i]) --tail;
que[  tail] = i;  // 維護一個單減區間
if (i <= n - m   1) {
while(que[head] >= i   m)   head;  // 剔除不屬於這個區間的.
ans1  = (a[que[head]] ^ i);
ans2  = ((tail - head   1) ^ i);
}
}
printf("%lld %lld\n", ans1, ans2);
}