B.Little Sub and Triples

Description

Little Sub has learned a new word ’Triple’, which usually means a group with three elements in it. Now he comes up with an interesting problem for you.
Define F(a,b,c) = e^a∗eb / e^c
Given an positive integer sequence A and some queries. In each query, you have to tell if there exists a triple T = (x, y, z) such that:
1.x, y, z are unique integers.
2.l ≤ x, y, z ≤ r.
3.Ax ≤ Ay ≤ Az.
4.F(Ax,Ay,Az) > 1.

Input

The first line contains two positive integers n, q(1 ≤ n, q ≤ 200000).
The second line contains n positive integers, indicating the integer sequence. The next q lines describe each query by giving two integer l, r(1 ≤ l ≤ r ≤ n). All given integers will not exceed 2^31 − 1.
Due to some reasons, when l>r, please consider it as an empty interval. Sorry for it.

Output

For each query, print YES if it exists any legal triple or NO otherwise.

Author
CHEN, Jingbang

题解:求区间内的是否有三个数符合三角形法则,常规的办法是把区间内的数排序后暴力求解,会超时.但是如果区间的数符合斐波那契数列的话,不会超过60项.

所以如果区间超过60,直接输出yes,不然的话就直接暴力求解.

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
const int N=2e5+5;
using namespace std;
typedef long long ll;
ll a[N];
ll b[N];
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);
    while(q--){
        int l,r;
        scanf("%d%d",&l,&r);
        if(r-l>60) printf("YES
");
        else{
            int m=0;
            for(int i=l;i<=r;i++) b[++m]=a[i];
            sort(b+1,b+1+m);
            int f=0;
            for(int i=1;i<=m-2;i++) if(b[i]+b[i+1]>b[i+2]){
                                        f=1;;
                                        break;
            }
            if(f) printf("YES
"); else printf("NO
");
        }
    }
    //cout << "Hello world!" << endl;
    return 0;
}