传送门 http://acm.hdu.edu.cn/showproblem.php?pid=6601
题意:
给你一个长度为 \(n\) 的序列, 有 \(q\) 个询问, 每个询问给你一个区间 \([l,r]\), 每次询问问你在区间 \([l,r]\) 中, 能够组成的最大的三角形的周长.
分析:
因为三角形具有两边之和大于第三边的性质, 即 \(a+b>c\) 的性质. 而倘若有若干个数都符合条件, 则倘若我们将不等号改成等号, 这就形成了一个斐波那契数列. 而根据斐波那契数列的性质, 值域在 \([1,a]\) 的斐波那契数列最多会有 \(log2(a)\) 项.
而在这里可以利用这个性质, 每个询问我们贪心的去取第 \(k\) 大, 第 \(k+1\) 大, 第 \(k+3\) 大的数进行比较, 如果不符合条件则继续向后找第 \(k+4\) 项直到找到答案为止. 因为值域上限为 \(10^9\), 故最大只需要枚举大概 \(44\) 次. 而每次寻找第 \(k\) 大, 我们可以用主席树在 \(\mathcal{O}(logn)\) 的时间复杂度下进行查询第 \(k\) 大. 故整体的时间复杂度为:\(\mathcal{O}(44qlogn)\)
代码:
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int MAXN = 100010;
- const int M = MAXN * 30;
- int n,q,m,tot;
- int a[MAXN], t[MAXN];
- int T[M], lson[M], rson[M], c[M];
- void Init_hash()
- {
- for(int i = 1; i <= n;i++)
- t[i] = a[i];
- sort(t+1,t+1+n);
- m = unique(t+1,t+1+n)-t-1;
- }
- int build(int l,int r)
- {
- int root = tot++;
- c[root] = 0;
- if(l != r)
- {
- int mid = (l+r)>>1;
- lson[root] = build(l,mid);
- rson[root] = build(mid+1,r);
- }
- return root;
- }
- int Hash(int x)
- {
- return lower_bound(t+1,t+1+m,x) - t;
- }
- int update(int root,int pos,int val)
- {
- int newroot = tot++, tmp = newroot;
- c[newroot] = c[root] + val;
- int l = 1, r = m;
- while(l <r)
- {
- int mid = (l+r)>>1;
- if(pos <= mid)
- {
- lson[newroot] = tot++; rson[newroot] = rson[root];
- newroot = lson[newroot]; root = lson[root];
- r = mid;
- }
- else
- {
- rson[newroot] = tot++; lson[newroot] = lson[root];
- newroot = rson[newroot]; root = rson[root];
- l = mid+1;
- }
- c[newroot] = c[root] + val;
- }
- return tmp;
- }
- int query(int left_root,int right_root,int k)
- {
- int l = 1, r = m;
- while( l <r)
- {
- int mid = (l+r)>>1;
- if(c[lson[left_root]]-c[lson[right_root]]>= k )
- {
- r = mid;
- left_root = lson[left_root];
- right_root = lson[right_root];
- }
- else
- {
- l = mid + 1;
- k -= c[lson[left_root]] - c[lson[right_root]];
- left_root = rson[left_root];
- right_root = rson[right_root];
- }
- }
- return l;
- }
- void read(int &ret){
- ret=0;
- char ch=getchar();
- int flag=1;
- while(ch>'9'||ch<'0'){if(ch=='-') flag=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){
- ret=ret*10+ch-'0';
- ch=getchar();
- }
- ret*=flag;
- }
- int main(){
- while(~scanf("%d%d",&n,&q)){
- for (int i = 1; i <= n; i++) read(a[i]);
- tot=0;
- Init_hash();
- T[n + 1] = build(1, m);
- for (int i = n; i; i--) {
- int pos = Hash(a[i]);
- T[i] = update(T[i + 1], pos, 1);
- }
- while (q--) {
- int l, r;
- read(l), read(r);
- int len = (r - l + 1);
- ll ans = -1;
- while (len>= 3) {
- ll x1 = t[query(T[l], T[r + 1], len)];
- ll x2 = t[query(T[l], T[r + 1], len - 1)];
- ll x3 = t[query(T[l], T[r + 1], len - 2)];
- if (x1 < x2 + x3) {
- ans = 1LL * x1 + 1LL * x2 + 1LL * x3;
- break;
- }
- len--;
- }
- printf("%lld\n", ans);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3133512.html