Teleport

Teleport

题意

给定一个长度为 $n$ 的序列 $\{a\}$，$q$ 次询问。每次查询区间 $[l,r]$，若能选出 1 个三元组 $(a_i,a_j,a_k)$ 使得能够构成三角形，输出 Triangle，否则输出 Not triangle。注意 $i\ne j,j\ne k$，$n\leq 2\times 10^5,a_i\leq10^9$。

Sol

考虑判断序列完全非法的情况：首先我们将整个序列 $\{a\}$ 按照从小到大排序，如果对于所有的 $i\in(l,r)$ 使得 $a_{i-1}+a_{i}\leq a_{i+1}$，那么序列完全非法。

考虑构造 $n$ 尽可能大的完全非法序列，那么一定是形如 $1,1,2,3,5,8,13,\cdots$ 的斐波那契数列。我们知道斐波那契数列的通项公式为

$f_n = \frac{1}{ \sqrt{5} }(\frac{ 1 + \sqrt{5} }{2})^n - \frac{1}{ \sqrt{5} }(\frac{ 1 - \sqrt{5} }{2})^n$

呈指数级别增长。那么意味着，当 $n$ 大于某一定值时，序列一定不是非法序列。那么当询问区间长度大于某一定值时，我们可以直接判定合法，否则我们通过上述操作暴力判断序列是否合法。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=4e5+1e1;
const lint INF=1e18+1e9;

lint a[MAXN],b[MAXN];
int n,q;

int main(void){

	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) a[i]=readlint;
	while(q--){
		int l=readint,r=readint,flag=1;
		if(r-l+1<=100){//brute
			bool vis=0;
			for(int i=l;i<=r;i++) b[i]=a[i];
			sort(b+l,b+r+1);
			for(int i=l+2;i<=r;i++) if(b[i-1]+b[i-2]>b[i]) vis=1;
			flag=vis;
		}
		puts(!flag ? "Not triangle" : "Triangle");
	}

	return 0;
}