http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1011&cid=849 就会俩题。。。10题水题不写了，今天还做了两道主席树板题也不写了。。。 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
给一个数组，每次查询l到r区间能组成的最大周长三角形 在区间内从大到小遍历一次即可 比赛的时候感觉主席树时空复杂度太大就没写。。。然后就白给了 重新开数组或者用优先队列每次查询都是O（nlogn） 主席树也是，但是查询时不一定遍历完所以时间复杂度会更小
#include<stdio.h> #include<queue> #include<algorithm> #define maxl 100005 using namespace std; int n,q; int nn,tot; int rt[maxl]; long long a[maxl],b[maxl]; struct node { int ls,rs,sum; }tree[maxl*30]; void insert(int num,int &x,int l,int r) { tree[++tot]=tree[x]; x=tot; ++tree[x].sum; if(l==r) return; int mid=(l+r)>>1; if(num<=mid) insert(num,tree[x].ls,l,mid); else insert(num,tree[x].rs,mid+1,r); } void prework() { tree[0].ls=tree[0].rs=tree[0].sum=0; rt[0]=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); b[i]=a[i]; } sort(b+1,b+1+n); nn=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+nn+1,a[i])-b; tot=0; for(int i=1;i<=n;i++) { rt[i]=rt[i-1]; insert(a[i],rt[i],1,nn); } } int query(int i,int j,int k,int l,int r) { if(l==r) return l; int tp=tree[tree[j].ls].sum-tree[tree[i].ls].sum; int mid=(l+r)>>1; if(k<=tp) return query(tree[i].ls,tree[j].ls,k,l,mid); else return query(tree[i].rs,tree[j].rs,k-tp,mid+1,r); } int main() { while(~scanf("%d%d",&n,&q)) { tot=0; prework(); while(q--) { int L,R; scanf("%d%d",&L,&R); if(R-L<2) { printf("-1\n"); continue; } long long a1,a2,a3; a1=b[query(rt[L-1],rt[R],R-L+1,1,nn)]; a2=b[query(rt[L-1],rt[R],R-L,1,nn)]; long long ans=-1; for(int i=R-L-1;i>=1;i--) { a3=b[query(rt[L-1],rt[R],i,1,nn)]; if(a1<(a2+a3)) { ans=a1+a2+a3; break; } a1=a2; a2=a3; } printf("%lld\n",ans); } } }