题解 CF900C 【Remove Extra One】

题目描述
You are given a permutation p of length n . Remove one element from permutation to make the number of records the maximum possible.

We remind that in a sequence of numbers
​
the element is a record if for every integer j ( 1<=j<=i ) the following holds: aj<=ai .

输入格式
The first line contains the only integer — the length of the permutation.

The second line contains n n integers — the permutation. All the integers are distinct.

输出格式
Print the only integer — the element that should be removed to make the number of records the maximum possible. If there are multiple such elements, print the smallest one.

输入输出样例
输入 #1
1
1
输出 #1
1
输入 #2
5
5 1 2 3 4
输出 #2
5
说明/提示
In the first example the only element can be removed.

题解：
首先把一个数p分解成几个数成组成的序列有2^p−1，用组合的隔板法轻易可证。x能整除y说明存在这样的序列，反之不存在。然后d=y/x，将d分解成质数乘积，算算不同质数的个数以及具体是哪些质数，容斥一下就能求出答案了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int bits[N];
int num[N];
int n,m,T,k,p;
set<int> pt;
set<int>::iterator it;
void add(int i,int x)
{
    while(i<=n)
    {
        bits[i]+=x;
        i+=(i &(-i));
    }
    return ;
}
int sum(int i)
{
    int res=0;
    while(i>0)
    {
        res+=bits[i];
        i-=(i &(-i));
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if((p-1>0 && sum(p-1)==i-2) || (p-1==0 && i==2))
        {
            it=pt.lower_bound(p);
            num[*it]++;
        }
        if((p-1>0 && sum(p-1)==i-1) || (p-1==0 && i==1))
            num[p]--;
        pt.insert(p);
        add(p,1);
    }
    int maxn=num[1];
    k=1;
    for(int i=2;i<=n;i++)
    {
        if(maxn<num[i])
        {
            maxn=num[i];
            k=i;
        }
    }
    cout<<k<<endl;
    return 0;
}