栈和队列

以BZOJ例题为主。

单调栈

[BZOJ 1012] JSOI2008 最大数

[Description]

长度为$n(n≤2\cdot 10^5)$的序列,有一些查询表示为(pos,L),询问区间[L-pos+1,L]的最大值,强制在线。

[Solution]

我们知道,若所有L一样,就是一个经典的单调队列模型。
然而L并不一样啊,这时队列的一边并不能随随便便弹出元素,因为以后可能还会用到。
所以这一边就不弹元素了,只要保持单调,我们就可以二分出询问位置的答案。
然后就退化成单调栈了,复杂度$O(nlogn)$.

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;

inline int read(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x;
}
inline char getc(){
char c=getchar();
while(!isalpha(c)) c=getchar();
return c;
}

const int maxn=2e5;
int a[maxn],cnt;
struct stack{
int seq[maxn],p;
stack(){ p=0; }
int top(){ return seq[p-1]; }
void pop(){ p--; }
void push(int x){ seq[p++]=x; }
bool empty(){ return !p; }
}s;

int query(int pos){
int t=*(lower_bound(s.seq,s.seq+s.p,pos));
return a[t];
}

int main(){
int q=read(),d=read(),t=0;
s.p=0;
while(q--){
int kase=getc()=='A'?1:2;
if(kase==1){
a[cnt]=(read()+t)%d;
while(!s.empty() && a[s.top()]<=a[cnt]) s.pop();
s.push(cnt++);
}
else printf("%d\n",t=query(cnt-read()));
}
return 0;
}

[BZOJ 1127] POI2008 KUP

[Description]

给一个$n\cdot n(n≤2000)$的地图,每个格子有一个价格。要求找一个矩形区域,使其价格总和位于[k,2k].
输出矩形左上角和右下角的坐标。
注意的数据范围题目写错了

[Solution]

考虑一维也就是单行的情况,若这个序列中存在[k,2k]之间的点,则直接输出。
否则若找到一个区间满足,所有的元素都小于k,且区间和大于2k,这个区间一定包含一个答案区间。
在否则就无解了。
推广到二维也是一样,找到一个矩阵满足,所有的元素都小于k,矩阵和大于2k,这个矩阵一定包含一个答案矩阵。
将小于k的元素标记为1,利用单调栈找到一些最大全1子矩阵,若找到一个和大于2k的全1子阵,我们可以直接寻找答案。
注意到满足要求的子矩阵和是大于等于2*k的,我们考虑子矩阵的第一行和最后一行,一定有一行不超过矩阵和/2,将它删除,再重复删除操作直至矩阵和位于[k,2k]为止,输出答案。
这样做为什么一定能达到[k,2k]呢?想到,每次矩阵的缩减不超过一半,所以一定有一时刻减到[k,2k].
总复杂度为$O(n^2)$.

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<stack>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<algorithm>
using namespace std;

inline int read(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}

typedef long long ll;
const int maxn=2e3+1;
int k,n;
int a[maxn][maxn];
ll sum[maxn][maxn];

stack<int> s,w;
int b[maxn][maxn];
ll area(int x1,int y1,int x2,int y2){
return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
bool check(int x1,int y1,int x2,int y2){
ll x=area(x1,y1,x2,y2);
if(x<k) return false;
while(x>2*k && x1<x2){
ll u=area(x1,y1,x1,y2),v=area(x2,y1,x2,y2);
if(u<v) x-=u,x1++;
else x-=v,x2--;
}
if(x<=2*k){ printf("%d %d %d %d",y1,x1,y2,x2); return true; }
return false;
}
void work(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
while(!s.empty() && b[i][s.top()]>=b[i][j]){
int t1=s.top(),t2=w.top(); s.pop(),w.pop();
int x1=i-b[i][t1]+1,y1=t2,x2=i,y2=j-1;
if(check(x1,y1,x2,y2)) exit(0);
}
w.push(w.empty()?1:s.top()+1),s.push(j);
}
while(!s.empty()){
int t1=s.top(),t2=w.top(); s.pop(),w.pop();
int x1=i-b[i][t1]+1,y1=t2,x2=i,y2=n;
if(check(x1,y1,x2,y2)) exit(0);
}
}
}

int main(){
k=read(),n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();

for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];

for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]<k) b[i][j]=true;
else if(a[i][j]<=2*k){ printf("%d %d %d %d",j,i,j,i); return 0; }
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=b[i][j]?(b[i-1][j]+b[i][j]):0;

work();
printf("NIE");
}

队列

优先队列

三题都差不多,具体可见 >> 《链表小结》

[BZOJ 1150] 数据备份

[BZOJ 2151] 种树

[BZOJ 2288] 生日礼物

单调队列

(很多POI的题?!)

[BZOJ 1047] HAOI2007 理想的正方形

[Description]

有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。
其中$a,b≤2000,n≤100$.

[Solution]

二维单调队列(感觉某些数据结构从一维拓展到二维非常好脑补)。

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<deque>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;

inline int read(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}

const int maxn=1e3;
int a,b,n;
int matrix[maxn][maxn];

deque<int> q1,q2;
void clear(){
while(!q1.empty()) q1.pop_front();
while(!q2.empty()) q2.pop_front();
}
int Min[maxn][maxn],Max[maxn][maxn];
void work_1D(int k){
clear();
for(int i=0;i<b;i++){
while(!q1.empty() && i-q1.front()>=n) q1.pop_front();
while(!q1.empty() && matrix[k][q1.back()]>=matrix[k][i]) q1.pop_back();
q1.push_back(i); Min[k][i]=matrix[k][q1.front()];
while(!q2.empty() && i-q2.front()>=n) q2.pop_front();
while(!q2.empty() && matrix[k][q2.back()]<=matrix[k][i]) q2.pop_back();
q2.push_back(i); Max[k][i]=matrix[k][q2.front()];
}
}
int ans=~0u>>1;
void work_2D(int k){
clear();
int MIN,MAX;
for(int i=0;i<a;i++){
while(!q1.empty() && i-q1.front()>=n) q1.pop_front();
while(!q1.empty() && Min[q1.back()][k]>=Min[i][k]) q1.pop_back();
q1.push_back(i); MIN=Min[q1.front()][k];
while(!q2.empty() && i-q2.front()>=n) q2.pop_front();
while(!q2.empty() && Max[q2.back()][k]<=Max[i][k]) q2.pop_back();
q2.push_back(i); MAX=Max[q2.front()][k];
if(i>=n-1) ans=min(ans,MAX-MIN);
}
}

int main(){
a=read(),b=read(),n=read();
for(int i=0;i<a;i++)
for(int j=0;j<b;j++)
matrix[i][j]=read();
for(int i=0;i<a;i++) work_1D(i);
for(int i=n-1;i<b;i++) work_2D(i);
printf("%d",ans);
return 0;
}

[BZOJ 2096] POI2010 Pilots

[Description]

在长度为n的找到一个最长的连续子串,最大值和最小值的差不超过k.

[Hint]

$n≤3\cdot 10^6,k≤2\cdot 10^9$.

[Solution]

l随r增大而不减。
维护递增递减两个队列,弹出最左元素来维护要求。

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<queue>
#include<cstdio>
#include<cctype>
using namespace std;

inline int read(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
inline int max(int x,int y){ return x>y?x:y; }

const int maxn=3e6;
int a[maxn];

deque<int> q1,q2;

int main(){
int k=read(),n=read(),ans=0;
for(int i=0;i<n;i++) a[i]=read();
for(int i=0,now=-1;i<n;i++){
while(!q1.empty() && a[q1.back()]<=a[i]) q1.pop_back();
while(!q2.empty() && a[q2.back()]>=a[i]) q2.pop_back();
q1.push_back(i),q2.push_back(i);
while(true){
if(q1.empty() || q2.empty()) break;
int x=q1.front(),y=q2.front();
if(a[x]-a[y]>k)
if(x<y) q1.pop_front(),now=x;
else q2.pop_front(),now=y;
else break;
}
ans=max(ans,i-now);
}
printf("%d",ans);
return 0;
}

[BZOJ 2276] POI2011 Temperature

[Description]

某国进行了连续$n(n≤10^6)$天的温度测量,测量存在误差,测量结果是第i天温度在[li,ri]范围内。
求最长的连续的一段,满足该段内可能温度不降。

[Solution]

单调队列维护极大的连续序列,保存编号。
保持队列中l的单调不降,且队中所有的r大于队首的l,这样,以当前对队尾结尾的合法区间中,l最小为最后一个在队首被弹出的元素+1。
复杂度$O(n)$.

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<deque>
#include<cstdio>
#include<cctype>
using namespace std;

inline int read(){
int x=0; char c=getchar(); bool minu=false;
while(!isdigit(c) && c-'-') c=getchar();
if(c=='-') minu=true,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return minu?-x:x;
}

const int maxn=1e6;
int l[maxn],r[maxn];

deque<int> q;

int main(){
int n=read(),ans=0;
for(int i=0,now=-1;i<n;i++){
l[i]=read(),r[i]=read();
while(!q.empty() && r[i]<l[q.front()]) now=q.front(),q.pop_front();
while(!q.empty() && l[q.back()]<=l[i]) q.pop_back();
q.push_back(i);
ans=max(ans,i-now);
}
printf("%d",ans);
return 0;
}

[BZOJ 1122] POI2008 账本BBB

[Description]

给定一个由+1和−1构成的长度为$n(n≤10^6)$的序列a,提供两种操作:
1.将某一位取反,花销为x
2.将最后一位移动到前一位,花销为y
sum[i]=∑(i=1 to i)a[i],经过若干此操作后,最终p+sum[n]=q,且0≤p+sum[i] (1≤i≤n),求最小花销。
输入保证有解

[Solution]

枚举序列从那一段开始(意味着先统计完第二种操作的数量),下面考虑只进行第一种操作的次数。
为了使影响尽量“有用”,我们将所有-1->1的操作从前往后进行,1->-1的操作从后往前进行。
首先为了满足最终sum=q-p,我们需要先进行abs(q-p-sum)/2次操作时sum合法。
设前缀和最低值为mini,若q-p-sum>0,它首先变成了mini+(q-p-sum),记为新mini。
再要满足所有前缀和都大于等于0,所以要使得mini大于等于0。
使mini大于等于0需要在mini的为之前进行(1-mini)/2次-1->1操作(而且显然有足够的可以操作),为了保持前缀和的值,mini之后再进行这么多次-1->1的操作(同样不会影响最低点)。
然后就可以统计第一种操作的数量了。
所以需要用单调队列预处理出对于每个位置前缀和最小的那个位置。
复杂度$O(n)$.

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<deque>
#include<cstdio>
using namespace std;

inline int abs(int x){ return x<0?-x:x; }

typedef long long ll;
const int maxn=1e6+1;
char s[2*maxn];
int sum[2*maxn],lowest[2*maxn];

deque<int> d;

int main(){
int n; ll p,q,x,y; scanf("%d%lld%lld%lld%lld",&n,&p,&q,&x,&y);
scanf("%s",s);
for(int i=0;i<n;i++) s[i+n]=s[i];
for(int i=(n<<1)-1;i>=0;i--) sum[i]=sum[i+1]+(s[i]=='-'?-1:1);
for(int i=(n<<1)-1;i>=0;i--){
while(!d.empty() && d.back()-i>=n) d.pop_back();
while(!d.empty() && sum[d.front()]<=sum[i]) d.pop_front();
d.push_front(i); lowest[i]=sum[i]-sum[d.back()];
}
ll ans=~0ull>>1;
int t=(q-p-sum[n])/2;
if((q-p-sum[n])&1){ printf("-1"); return 0; }
for(int i=0;i<n;i++){
ll res=x*abs(t)+y*((n-i)%n);
lowest[i]+=p+(t>0?2*t:0);
if(lowest[i]<0) res+=2*x*((1-lowest[i])>>1);
ans=min(ans,res);
}
printf("%lld",ans);
return 0;
}