G. Sequence Number
In Linear algebra, we have learned the definition of inversion number: Assuming A is a ordered set with n numbers ( n > 1 ) which are different from each other. If exist positive integers i , j, ( 1 ≤ i ＜ j ≤ n and A[i] ＞ A[j]), <a[i], a[j]=""> is regarded as one of A’s inversions. The number of inversions is regarded as inversion number. Such as, inversions of array <2,3,8,6,1> are <2,1>, <3,1>, <8,1>, <8,6>, <6,1>,and the inversion number is 5. Similarly, we define a new notion —— sequence number, If exist positive integers i, j, ( 1 ≤ i ≤ j ≤ n and A[i] <= A[j], <a[i], a[j]=""> is regarded as one of A’s sequence pair. The number of sequence pairs is regarded as sequence number. Define j – i as the length of the sequence pair. Now, we wonder that the largest length S of all sequence pairs for a given array A.
Input
There are multiply test cases. In each case, the first line is a number N(1<=N<=50000 ), indicates the size of the array, the 2th ~n+1th line are one number per line, indicates the element Ai （1<=Ai<=10^9） of the array.
Output
Output the answer S in one line for each case.
Sample Input
5 2 3 8 6 1
Sample Output
3
题意：找出最远的i<=j&&a[i]<=a[j]的长度；
思路：这是一道排序可以过的题，也可以rmq+二分 最快的写法可以用单调栈做到O(n)
我是求后面的最大值后缀，二分后缀；
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<stack> 9 #include<cstring> 10 #include<vector> 11 #include<list> 12 #include<set> 13 #include<map> 14 using namespace std; 15 #define ll long long 16 #define pi (4*atan(1.0)) 17 #define eps 1e-4 18 #define bug(x) cout<<"bug"<<x<<endl; 19 const int N=1e5+10,M=1e6+10,inf=2147483647; 20 const ll INF=1e18+10,mod=2147493647; 21 22 int a[N],nex[N]; 23 int main() 24 { 25 int n; 26 while(~scanf("%d",&n)) 27 { 28 memset(nex,0,sizeof(nex)); 29 for(int i=1;i<=n;i++) 30 scanf("%d",&a[i]); 31 for(int j=n;j>=1;j--) 32 nex[j]=max(a[j],nex[j+1]); 33 int ans=0; 34 for(int i=1;i<=n;i++) 35 { 36 int s=i,e=n,pos=-1; 37 while(s<=e) 38 { 39 int mid=(s+e)>>1; 40 if(nex[mid]>=a[i]) 41 pos=mid,s=mid+1; 42 else e=mid-1; 43 } 44 ans=max(ans,pos-i); 45 } 46 printf("%d ",ans); 47 } 48 return 0; 49 }
单调栈做法，如果当前元素小于栈顶元素入栈，否则依次和栈中元素计算相对距离且取最长的那一个。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 struct jj 5 { 6 int pos,x; 7 }a[50000]; 8 int main() 9 { 10 int n,i,i1,x,top,maxnum; 11 while(scanf("%d",&n)!=EOF) 12 { 13 top=0; 14 maxnum=0; 15 for(i=0;n>i;i++) 16 { 17 scanf("%d",&x); 18 if(top==0||a[top-1].x>x) 19 { 20 a[top].x=x; 21 a[top].pos=i; 22 top++; 23 } 24 else 25 { 26 for(i1=top-1;i1>=0&&a[i1].x<=x;i1--) 27 { 28 maxnum=max(maxnum,i-a[i1].pos); 29 } 30 } 31 } 32 printf("%d ",maxnum); 33 } 34 return 0; 35 }
双指针做法，维护左指针和右指针，使左指针的值小于等于右指针的值
1 #include <cstdio> 2 #include <vector> 3 #include <cstring> 4 #include <string> 5 #include <cstdlib> 6 #include <iostream> 7 #include <map> 8 #include <cmath> 9 #include <algorithm> 10 using namespace std; 11 typedef long long LL; 12 typedef pair<int,int>pii; 13 const int N = 1e5+5; 14 const double eps = 1e-8; 15 int T,n,w[N],sum[N<<2],p[N<<2],cnt,m,ret[N]; 16 int k,a[N],mi[N]; 17 int main() { 18 while(~scanf("%d",&n)){ 19 20 int ans=0; 21 mi[0]=1e9+10; 22 for(int i=1;i<=n;i++){ 23 scanf("%d",&a[i]); 24 mi[i]=1e9+10; 25 } 26 for(int i=1;i<=n;i++){ 27 mi[i]=min(mi[i-1],a[i]); 28 } 29 for(int l=n,r=n;l>=1;l--){ 30 if(mi[l]>a[r]){ 31 while(a[r]<mi[l]){ 32 r--; 33 } 34 ans=max(ans,r-l); 35 } 36 else { 37 ans=max(ans,r-l); 38 } 39 } 40 printf("%d ",ans); 41 } 42 return 0; 43 }