栈

单调栈

[BZOJ 1012] JSOI2008 最大数

[Description]

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

[Solution]

我们知道，若所有L一样，就是一个经典的单调队列模型。
然而L并不一样啊，这时队列的一边并不能随随便便弹出元素，因为以后可能还会用到。
所以这一边就不弹元素了，只要保持单调，我们就可以二分出询问位置的答案。
然后就退化成单调栈了，复杂度O(n⋅log n)O(n\cdot log\ 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
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⋅n(n≤2000)n⋅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(n2)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");
}

队列

优先队列

三题都差不多，具体可见 >> 链表 | Linked List

[BZOJ 1150] 数据备份

[BZOJ 2151] 种树

[BZOJ 2288] 生日礼物

单调队列

（很多POI的题？！）

[BZOJ 1047] HAOI2007 理想的正方形

[Description]

有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
其中a,b≤2000,n≤100a,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⋅106,k≤2⋅109n≤3⋅10^6,k≤2⋅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≤106)n(n≤10^6)天的温度测量，测量存在误差，测量结果是第i天温度在[li,ri][l_i,r_i]范围内。
求最长的连续的一段，满足该段内可能温度不降。

[Solution]

单调队列维护极大的连续序列，保存编号。
保持队列中l的单调不降，且队中所有的r大于队首的l，这样，以当前对队尾结尾的合法区间中，l最小为最后一个在队首被弹出的元素+1。
复杂度O(n)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≤106)n(n≤10^6)的序列a，提供两种操作：
1.将某一位取反，花销为x
2.将最后一位移动到前一位，花销为y
sum[i]=∑i=1ia[i]，经过若干此操作后，最终sum[i]=\sum_{i=1}^ia[i]，经过若干此操作后，最终p+sum[n]=q$，且0≤p+sum[i](1≤i≤n)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)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;
}