本文共 853 字，大约阅读时间需要 2 分钟。
树状数组+离散化
#include #include #include #include #include using namespace std;const int maxn=100000+10;int a[maxn],ans[maxn],c[maxn],b[maxn];int n;map m;int lowbit(int x){ return x&(-x);}void update(int a,int b){ for(int i=a;i<=n;i=i+lowbit(i)) c[i]+=b;}int get(int a){ int res=0; for(int i=a;i>0;i=i-lowbit(i)) res+=c[i]; return res;}void lsh(){ sort(b+1,b+1+n); for(int i=1;i<=n;i++) m[b[i]]=i;}int main(){ scanf("%d",&n); int k=0; memset(c,0,sizeof c); m.clear(); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } lsh(); for(int i=1;i<=n;i++) { if(m[a[i]]==i) { int num=get(m[a[i]]-1); if(num==m[a[i]]-1) ans[k++]=m[a[i]]; } update(m[a[i]],1); } sort(ans,ans+k); printf("%d\n",k); for(int i=0;i
转载于:https://www.cnblogs.com/zufezzt/p/5642292.html