这题 很多人直接用的一个for循环。。解决的。我不怎么理解。这题我是用的树状数组。
统计两个东西。 1 统计a[i]左边，比a[i]小的和比a[i]大的个数。 2统计a[i]右边，比a[i]小 和比a[i]大的个数。
然后根据题意。任意选择一组合适得到解即可。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define eps 10e-9
#define inf 0x3f3f3f3f
const int maxn = 100000+100;
int a[maxn],c1[2001000],c2[2001000];
int lowbit(int x) { return x&-x;}
void add(int x,int add,int c[]){
while(x<2000000){
c[x]+=add; x+=lowbit(x);
}
}
int sum(int x,int c[]){
int ret=0;
while(x>0){
ret+=c[x]; x-=lowbit(x);
}
return ret;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i
for(int i=0;i
add(a[i],1,c2);
}
int flag1=0,flag2=0;
int a1,a2,a3;
for(int i=0;i
int s1=sum(a[i]-1,c1);
int s2=sum(a[i]-1,c2);
// printf("%d %d\n",s1,s2);
if(s1>0&&s2>0){
flag1=1;a2=i; break;
}
s1=sum(a[i],c1); s2=sum(a[i],c2);
s1=i-s1; s2=n-i-s2;
add(a[i],-1,c2);
add(a[i],1,c1);
// printf("%d %d\n",s1,s2);
if(s1>0&&s2>0){
flag2=1;a2=i; break;
}
}
if(flag1){
for(int i=0;i
if(a[i]
a1=i; break;
}
}
for(int i=a2+1;i
if(a[i]
a3=i; break;
}
}
printf("3\n");
printf("%d %d %d\n",a1+1,a2+1,a3+1);
}
else if(flag2){
for(int i=0;i
if(a[i]>a[a2]){
a1=i; break;
}
}
for(int i=a2+1;i
if(a[i]>a[a2]){
a3=i; break;
}
}
printf("3\n");
printf("%d %d %d\n",a1+1,a2+1,a3+1);
}
else printf("0\n");
return 0;
}