hdu 6601 区间条件极值 - 区间 最大 三角形周长
2024-09-05 08:02:24
题目传送门//res tp hdu
目的
对长度为n的区间，给定q个子区间，求其元素能构成三角形的最大周长。有多组测试。
n 1e5
q 1e5
ai [1,1e9] (i∈[1,n]);
数据结构
划分树
分析
需在不超过O（logn）的时间内完成一次查询
若一个数列不能构成三角形，则其为斐波那契数列。斐列不超过50项即可达到1e9，故每次只需查询区间的前k大即可，不超过50次询问，即可得到该数列是否能构成三角形
划分树的单次询问第k小/大为logn
#include<iostream>
#include<algorithm>
#include<cmath>
typedef long long ll;
using namespace std;
const int MAXN = 100000+50;
const int DEEP = 20;
ll tree[DEEP][MAXN];
int cnt[DEEP][MAXN];
ll sorted[MAXN];
void build(int deep,int lft,int rht)
{
if(lft == rht) return;
int mid = (lft + rht)>>1;
int scnt = mid - lft + 1;
ll M = sorted[mid];
for(int i = lft;i<=rht;++i){
if(tree[deep][i] < M) scnt--;
}
int p = lft, r = mid + 1;
for(int i = lft,cnt_in_left = 0;i<=rht;++i){
ll num = tree[deep][i];
if(num < M || (num == M && scnt)){
if(num == M) scnt--;
cnt_in_left++;
tree[deep + 1][p++] = num;
}
else tree[deep + 1][r++] = num;
cnt[deep][i] = cnt_in_left;
}
build(deep + 1,lft,mid);
build(deep + 1,mid + 1,rht);
}
ll query(int deep, int lft, int rht, int qlft, int qrht, int k){
if(lft == rht) return tree[deep][lft];
int mid = (lft + rht)>>1;
int left = 0,sum_in_left = cnt[deep][qrht];
if(qlft != lft){
left = cnt[deep][qlft-1];
sum_in_left-=left;
}
if(sum_in_left >= k){
int new_qlft = lft + left;
int new_qrht = new_qlft + sum_in_left - 1;
return query(deep + 1,lft,mid,new_qlft,new_qrht,k);
}
else{
int a = qlft - lft - left;
int b = qrht - qlft - sum_in_left;
int new_qlft = (mid + 1) + a;
int new_qrht = new_qlft + b;
return query(deep+1,mid+1,rht,new_qlft,new_qrht,k - sum_in_left);
}
}
int main()
{
int n,q,l,r;
while(scanf(" %d %d",&n,&q)!=EOF){
for(int i = 1;i<=n;++i) {
scanf(" %lld",&sorted[i]);
tree[0][i] = sorted[i];
}
sort(sorted+1,sorted+1+n);
build(0,1,n);
while(q--){
scanf(" %d %d",&l,&r);
if(r - l + 1 < 3) printf("-1\n");
else{
int len = r - l + 1;
long long a,b,c,ans = -1;
a = query(0,1,n,l,r,len);
b = query(0,1,n,l,r,len-1);
for(int i = len-2;i>=1;--i){
c = query(0,1,n,l,r,i);
if(b + c > a){
ans = a + b + c;break;
}
a= b;b = c;
}
printf("%lld\n",ans);
}
}
}
}
最新文章
- php简单实现socket通信
- Bulk_Collect 调用方式集锦
- git的基础介绍和使用
- java 实现多个文件的Zip包的生成
- Rhino 是一个完全使用Java语言编写的开源JavaScript实现。Rhino通常用于在Java程序中，为最终用户提供脚本化能力。它被作为J2SE 6上的默认Java脚本化引擎。
- 关于ui修改的若干想法
- python异常处理、反射、socket
- 生成二维码 打上自定义logo
- 数组（Array）的使用方法
- ThreadLocal使用和原理
- BZOJ 无数据题集合
- Reorder List [leetcode] 这两种思路
- web跨域问题
- 【原创】JQWidgets-TreeGrid 1、快速入门
- webuploader插件，我踩得坑
- Redis的并发竞争问题的解决方案总结
- python_web框架
- shell的打印菜单
- Python socket之tftp协议
- Nginx的进程模型及高可用方案(OpenResty)