CF 27C

这题很多人直接用的一个for循环。。解决的。我不怎么理解。这题我是用的树状数组。

统计两个东西。 1 统计a[i]左边，比a[i]小的和比a[i]大的个数。 2统计a[i]右边，比a[i]小和比a[i]大的个数。

然后根据题意。任意选择一组合适得到解即可。

[cpp]

#include <cmath>

#include <ctime>

#include <iostream>

#include <string>

#include <vector>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

#include <stack>

#include <deque>

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<n;i++) scanf("%d",&a[i]),a[i]+=1000000;

for(int i=0;i<n;i++){

add(a[i],1,c2);

}

int flag1=0,flag2=0;

int a1,a2,a3;

for(int i=0;i<n;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<a2;i++){

if(a[i]<a[a2]){

a1=i; break;

}

for(int i=a2+1;i<n;i++){

if(a[i]<a[a2]){

a3=i; break;

}

printf("3\n");

printf("%d %d %d\n",a1+1,a2+1,a3+1);

}

else if(flag2){