这题有两种写法，而且是完全（几乎？）不一样的写法...并不是换了个方法来维护而已
单调队列O(N):用一个队列维护a[]的单调递减，对于每个i满足a[队头]<=b[i]，然后就可以算出以每一位为结尾的最大答案了
#include<stdio.h> #include<cstring> #include<iostream> #include<cstdlib> using namespace std; const int maxn=1000010,inf=1e9; int n,fir,ans; int a[maxn],b[maxn],q[maxn]; inline void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int main() { read(n); for(int i=1;i<=n;i++)read(a[i]),read(b[i]); int l=1,r=0;fir=1; for(int i=1;i<=n;i++) { while(l<=r&&a[q[l]]>b[i])fir=max(fir,q[l++]+1); ans=max(ans,i-fir+1); while(l<=r&&a[q[r]]<=a[i])r--; q[++r]=i; } printf("%d ",ans); }
堆O(Nlogn):
比赛时候的写法...实在没想到单调队列
用two pointers，从l,r要扩展到l,r+1的时候只需要判断l~r里最大的a[]是不是<=b[r+1]就可以扩展了，这个可以用堆维护，左指针移动的时候删去堆中左指针的数。
#include<stdio.h> #include<cstring> #include<iostream> #include<cstdlib> #include<queue> using namespace std; const int maxn=1000010,inf=1e9; struct poi{int sum,pos;}; priority_queue<poi>q; bool operator<(poi a,poi b){return a.sum<b.sum;} int n,ans; int a[maxn],b[maxn]; bool v[maxn]; inline void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } inline int find() { if(q.empty())return -inf; poi t;for(t=q.top();v[t.pos]&&(!q.empty());q.pop(),t=q.top()); return q.empty()?-inf:t.sum; } int main() { read(n); for(int i=1;i<=n;i++)read(a[i]),read(b[i]); for(int i=1,j=1;j<=n;i++) { j=max(i,j); for(int t=find();j<=n;j++,t=find()) { if(t>b[j])break; q.push((poi){a[j],j}); ans=max(ans,j-i+1); } v[i]=1; } printf("%d ",ans); }
这个其实也是可以用单调队列来维护的...之前想错导致我LOJ D2 T2被坑了T T
单调队列可以兹磁找到队列中最值和删去最早的值两种操作...
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int maxn=1000010, inf=1e9; int n, L, R, ans; int l[maxn], r[maxn], q[maxn]; void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline int max(int a, int b){return a>b?a:b;} inline void qpush(int x) { while(L<=R &&l[q[R]]<=l[x]) R--; q[++R]=x; } int main() { read(n); for(int i=1;i<=n;i++) read(l[i]), read(r[i]); L=1; R=0; for(int i=1, j=1;i<=n;i++) { j=max(i, j); while(j<=n && ((L<=R)?l[q[L]]:-inf)<=r[j]) qpush(j++); ans=max(ans, j-i); if(q[L]==i) L++; } printf("%d ", ans); }