1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| struct Deque {
int head, tail, n, m, q[MAXN], a[MAXN], p;
Deque(){}
Deque(int n, int m, int head, int tail, int p) : n(n), m(m), head(head), tail(tail), p(p){};
int get(int id) {
int res = a[q[head]];
while (id - q[head] >= m && head <= tail) head++;
while (a[id] <= a[q[tail]] && head <= tail) tail--;
q[++tail] = id;
return res * p;
}
void scan() {
for (int i = 1; i <= n; i++) scanf ("%d", &a[i]), a[i] *= p;
}
}
|