Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
N sticks are arranged in a row, and their lengths are a1,a2,...,aN. There are Q querys. For i-th of them, you can only use sticks between li-th to ri-th. Please output the maximum circumference of all the triangles that you can make with these sticks, or print −1 denoting no triangles you can make.
Input
There are multiple test cases. Each case starts with a line containing two positive integers N,Q(N,Q≤105). The second line contains N integers, the i-th integer ai(1≤ai≤109) of them showing the length of the i-th stick. Then follow Q lines. i-th of them contains two integers li,ri(1≤li≤ri≤N), meaning that you can only use sticks between li-th to ri-th. It is guaranteed that the sum of Ns and the sum of Qs in all test cases are both no larger than 4×105.
Output
For each test case, output Q lines, each containing an integer denoting the maximum circumference.
Sample Input
5 3 2 5 6 5 2 1 3 2 4 2 5
Sample Output
13 16 16
题意：给定 n 根木棍的长度，然后有 Q 个询问，每一次询问给定 l , r 表示询问从第 l 根木棍到第 r 根木棍中能够组成的 三角形的最大周长。。
思路：关于用木棍组成三角形的问题，你需要知道当木棍数量 >= 47 根时一定能组成三角形（极端情况是 47 根木棍的长度成斐波拉契数，这些数无法构成三角形，且容纳的边数最多。第 47 项超过1e9），所以对于最大周长，一定在前 47 根木棍中构成。。所以每次询问利用主席树暴力 获得 前 47 根木棍长度，然后算周长即可。时间复杂度 Q * 50 * logn
Code:
#include<bits/stdc++.h> #define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl #define pii pair<int,int> #define clr(a,b) memset((a),b,sizeof(a)) #define rep(i,a,b) for(int i = a;i < b;i ++) #define pb push_back #define MP make_pair #define LL long long #define ull unsigned LL #define ls i << 1 #define rs (i << 1) + 1 #define INT(t) int t; scanf("%d",&t) using namespace std; const int maxn = 1e5 + 10; const int M = maxn * 40; int T[maxn];///T[i]表示第i颗线段树的顶结点 int lson[M],rson[M],c[M];///C[i]就代表第i个点的权值,即上述权值线段树的sum int X[maxn],K[maxn]; /// lson[i], rson[i] 表示第 i 个点的左儿子,右儿子是谁 int tot = 0,en; /// tot 用于动态开点 int getId(int x){ return lower_bound(X + 1,X + 1 + en,x) - X; } int build(int l,int r){ int rt = tot ++; c[rt] = 0; if(l != r){ int mid = (l + r) >> 1; lson[rt] = build(l,mid); rson[rt] = build(mid + 1,r); } return rt; } int update(int rt,int pos,int val){ int newrt = tot ++,tmp = newrt; c[newrt] = c[rt] + val; int l = 1,r = en; while(l < r){ int mid = (l + r) >> 1; if(pos <= mid){ lson[newrt] = tot ++; rson[newrt] = rson[rt]; newrt = lson[newrt]; rt = lson[rt]; r = mid; } else { rson[newrt] = tot ++; lson[newrt] = lson[rt]; newrt = rson[newrt]; rt = rson[rt]; l = mid + 1; } c[newrt] = c[rt] + val; } return tmp; } int query(int lrt,int rrt,int k){ int l = 1,r = en; while(l < r){ int mid = (l + r) >> 1; if(c[rson[rrt]] - c[rson[lrt]] >= k){ ///简单画一画就理解了 l = mid + 1; lrt = rson[lrt]; rrt = rson[rrt]; } else { r = mid; k -= c[rson[rrt]] - c[rson[lrt]]; rrt = lson[rrt]; lrt = lson[lrt]; } } return l; } LL LEN[60]; int p = 0; int main() { int n,q; while(~scanf("%d%d",&n,&q)){ en = tot = 0; for(int i = 1;i <= n;++ i){ scanf("%d",&K[i]); X[++ en] = K[i]; } sort(X + 1,X + 1 + en); en = unique(X + 1,X + 1 + en) - X - 1; T[0] = build(1,en); for(int i = 1;i <= n;++ i){ T[i] = update(T[i - 1],getId(K[i]),1); } while(q --){ int l,r; scanf("%d%d",&l,&r); p = 0; for(int j = 1;j <= min(50,r - l + 1);++ j){ LEN[++ p] = X[query(T[l - 1],T[r],j)]; } // for(int j = 1;j <= p;++ j) printf("%lld ",LEN[j]); printf("\n"); LL flag = 0; for(int j = 1;j + 2 <= p;++ j){ if(LEN[j] < LEN[j + 1] + LEN[j + 2]){ flag = LEN[j] + LEN[j + 1] + LEN[j + 2]; break; } } if(!flag) printf("-1\n"); else printf("%lld\n",flag); } } return 0; }
