题目大意:

给出1~n个一个排列,定义ai为record，满足所有的j<i 都满足aj<ai

现在要删除一个元素，使得删除后的序列record数最多

题目思路：

没想出来..一直考虑树状数组维护，看了题解才发现 真的妙！

从1~n遍历，记录i之前的最大值与次大值

维护一个数组cnt代表删除这个数后的影响，首先确定删除该数后，该数前面的绝对不会有影响，后面的record数也不会减少，只会增加。

所以讨论当前a[i] 与 之前最大值与次大值的关系

1.a[i] > 最大值，此时a[i]是record数，删除a[i]之后会减少1

2. 次大值 < a[i] <最大值,此时a[i]不是record数，删除没影响但是可以发现，删除最大值之后，a[i]便成为record数，所以最大值删除后record++

3.a[i] < 次大值，此时没有任何影响。

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e18;
const int maxn=1e6+6;
const int mod=1e9+7;
const double eps=1e-15;
inline bool read(ll &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m;
int cnt[maxn];
int main(){read(n);ll max1 = 0 ,max2 = 0;for(int i=1;i<=n;i++){ll x;read(x);if(x>max1) cnt[x]--;else if(x>max2) cnt[max1]++;if(x>max1){max2 = max1;max1 = x;}else if(x>max2) max2 = x;}ll maxl = cnt[1],pos = 1;for(int i=2;i<=n;i++){if(maxl<cnt[i]){maxl = cnt[i];pos = i;}}printf("%d\n",pos);return 0;
}
/**
3 1 5 4 2
0 0 2 2 1**/