bzoj4970 [ioi2004]empodia 障碍段

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define N (2000005)
 6 
 7 using namespace std;
 8 
 9 struct data{ int x,y; }ans[N];
10 struct edge{ int nt,to; }g[N];
11 
12 int head[N],lim1[N],lim2[N],st[N],a[N],p[N],n,num,tot,top,Ans;
13 
14 il int gi(){
15   RG int x=0,q=1; RG char ch=getchar();
16   while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();
17   if (ch==‘-‘) q=-1,ch=getchar();
18   while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();
19   return q*x;
20 }
21 
22 il void insert(RG int from,RG int to){
23   g[++num]=(edge){head[from],to},head[from]=num; return;
24 }
25 
26 il void solve(){
27   for (RG int i=1;i<=tot;++i){
28     while (top && lim1[st[top]]<p[i]) --top;
29     if (top && lim2[p[i]]<=st[top]) ans[++Ans]=(data){st[top],p[i]};
30     while (top && lim1[st[top]]<=lim1[p[i]]) --top; st[++top]=p[i];
31   }
32   return;
33 }
34 
35 il int cmp(const data &a,const data &b){
36   if (a.x==b.x) return a.y<b.y; return a.x<b.x;
37 }
38 
39 int main(){
40 #ifndef ONLINE_JUDGE
41   freopen("empodia.in","r",stdin);
42   freopen("empodia.out","w",stdout);
43 #endif
44   n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi()+1;
45   for (RG int i=n;i;--i) insert(n+a[i]-i,i);
46   for (RG int i=1;i<=n;++i){
47     while (top && a[st[top]]<a[i]) --top;
48     lim2[i]=st[top]+1,st[++top]=i;
49   }
50   st[top=0]=n+1;
51   for (RG int i=n;i;--i){
52     while (top && a[st[top]]>a[i]) --top;
53     lim1[i]=st[top]-1,st[++top]=i;
54   }
55   for (RG int i=0,j;i<=(n<<1);++i){
56     for (tot=top=0,j=head[i];j;j=g[j].nt) p[++tot]=g[j].to;
57     if (tot>=2) solve();
58   }
59   sort(ans+1,ans+Ans+1,cmp),top=0;
60   for (RG int i=1;i<=Ans;++i){
61     while (top && ans[st[top]].y>=ans[i].y) --top;
62     if (top && ans[st[top]].x==ans[i].x) continue; st[++top]=i;
63   }
64   cout<<top<<endl;
65   for (RG int i=1;i<=top;++i) printf("%d %d\n",ans[st[i]].x,ans[st[i]].y);
66   return 0;
67 }