单点时限: 5.0 sec
内存限制: 512 MB
QQ小方以前不会翻转数列，现在他会了，所以他急切的想教会你。
翻转数列指的是，把一个数列倒置。具体来说，如果一个数列是 a1,a2,a3⋯an ，那么翻转以后的数列是 a′1,a′2,a′3⋯a′n=an,an−1,an−2⋯a1 。
单单讲给你听肯定是不够的，为了表现自己，QQ小方现在要考考你。
现在QQ小方有一个数列 a1,a2,a3⋯an 。他想要翻转数列中的其中一个子数列（一个数列的子数列指的是任意个连续的数组成的子序列，子序列可以为空）。而且他希望在翻转以后有尽量多的位置满足 i=a′i 。QQ小方想知道，经过一次翻转操作，数列中最多能有多少位置满足 i=a′i 。
输入数据第一行包含一个整数 n （ 1≤n≤5⋅106 ） ，表示数列的长度。
接下来的一行包含 n 个用空格隔开的整数，分别表示 a1,a2,a3⋯an （ 1≤ai≤n ） ，表示初始的数列。
输出一行包含一个整数，表示答案。
Input
4 3 4 1 2Output
2可以选择翻转 [1,3] 子数列，变成 1,4,3,2 ，则位置 1 和 3 满足要求了。
也可以选择翻转 [2,4] 子数列，变成 3,2,1,4 ，则位置 2 和 4 满足要求了。
没有更优的翻转方案了。
思路：这个题目的话，比赛的时候没做出来，当时想的是，如果他有5e6个点，全都有互相匹配的的话，就只有2.5e3个匹配点了，然后后续暴力就行了，但是但是没做出来，没考虑到那种两边的情况，一开始搞的那个最大值也是不对的，因为一开始就有放好了的，这是我昨天犯的错误，
---------下面是思路-----------------
就是给出的点，有的是本来的位置就是对应的，也就是说我不给他翻转他的位置就是有贡献的，这一点要考虑到，昨天也是错误在这个地方，
下面就是对于每一个本来位置不对应的点的处理，我们把每一个位置不对应的点处理，我们知道，每一个位置不对应的点都会产生一个可能可行的翻转区间，那么我们把这个翻转区间的翻转轴保存，翻转的两端也保存，然后处理每一个翻转轴就可以了，
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int maxn=5e6+10; int n; int a[maxn],pre[maxn]; struct Node //左右端点和长度 { int l,r,len; Node(){} Node(int x,int y,int z):l(x),r(y),len(z){} }; int cmp(Node a,Node b) { return a.len<b.len; } vector<Node >G[maxn*2];//长度乘二 int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); pre[i]=pre[i-1]+(a[i]==i);//记录前缀的本来位置对应好了的数量 if(a[i]>i) { G[a[i]+i].push_back(Node(i,a[i],a[i]-i+1)); } else if(a[i]<i) { G[a[i]+i].push_back(Node(a[i],i,i-a[i]+1)); } else G[a[i]+i].push_back(Node(a[i],i,0)); } int maxx=pre[n]; for(int i=1;i<=2*n;i++) { sort(G[i].begin(),G[i].end(),cmp); } for(int i=1;i<=2*n;i++) { for(int j=0;j<G[i].size();j++) { Node tmp=G[i][j]; int qans=pre[n]-pre[tmp.r]+pre[tmp.l-1];//处理本来就对应好了的 qans+=(j+1);//加上在这个区间内可行的对应端点 maxx=max(maxx,qans); } } printf("%d\n",maxx); }
