被安利了一道题QAQ一开始还说错题意了QAQ

题意：

　　 

　　

　　　题意可以解释为，给你一个1~n的排列a[]，求一个i，使xi=(∑(j<i&&a[j]>a[i]) 1)最大，要求O(n)

sol：

　　　我这么蒟蒻显然想不出来啊，还说标程就10几行什么的QAQ，果断请教大爷去了

　　　首先对于该排列建立一个二维矩阵如图所示，横坐标为i，纵坐标为a[i]

　　　那么答案即为一个点左上方点的个数

　　　

 

　　　因为一个点如果右下方有点，则不可能作为答案，所以蓝线上的点为可能被选到作为答案的点

　　　首先先暴力求出第一个点的ans，考虑如何更新到下一个点

　　　

　　　我们发现ans的差值即为黄色部分和紫色部分的差，所以减去紫色部分再加上黄色部分即可

　　　加的时候横坐标单调递增，减的时候纵坐标单调递增，因为是排列所以直接计算即可，复杂度为O(n)

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int Mx=30000010;struct Node { int x,y; } stk[Mx];int n,ans,a[Mx],top;void pre(){    int s,b,c,d;    scanf("%d%d%d%d",&s,&b,&c,&d);    for(int i=1;i<=n;i++)        a[i]=i,s=(s*b+c)%d,swap(a[i],a[(s%i)+1]);}int main(){    scanf("%d",&n);    pre();    for(int i=1;i<=n;i++)    {        while(a[i]
        
       
      
     

　　　继续思考，发现一件神奇的性质：答案为max(i-a[i])

　　　给出证明：首先我们知道ans>=((i-1)-(a[i]=1))，即(i-a[i])为点i的ans的下界

　　　　　　　　然后，考虑对于点i满足max(i-a[i])，我们可以知道在该点的右面不存在点j使a[j]<a[i]

　　　　　　　　所以点i右面的点全部满足a[j]>a[i]，也就是说后面比a[i]大的点有n-i个，所以前面就有i-a[i]个

　　　　　　　　下面要证明该点在全局最大，可以尝试用数学归纳法证明

　　　　　　　　　　假设前n个点(n>1)已经满足，当插入第n+1个点(值为n+1)至位置pos时，首先xpos不可能为答案

　　　　　　　　　　∀j<pos，xj不变 ； ∀pos<k<=n+1，xk+1

　　　　　　　　　　对应到i-a[i]中，我们发现，所以位于pos右面的i都+1，满足性质

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int Mx=30000010;int n,s,b,c,d,ans,a[Mx],top;int main(){    scanf("%d%d%d%d%d",&n,&s,&b,&c,&d);    for(int i=1;i<=n;i++)        a[i]=i,s=(s*b+c)%d,swap(a[i],a[(s%i)+1]),ans=max(ans,i-a[i]);    cout<
         
          <