這題 很多人直接用的一個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){ 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 printf("0\n"); return 0; }
