题意 给出一个n位序列 a 有m个询问 l r 问在al -ar 之间能选取的最大周长的三角形
比赛的时候 用莫队算法 但是一直超时 （感觉时间复杂度不是特别高呀。。。）
可以用主席树遍历区间最大到最小来找三角形
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(ll i=(a);i<=(b);i++) #define repp(i,a,b) for(ll i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define inf 0x3f3f3f3f #define pb push_back #define CLR(A,v) memset(A,v,sizeof A) #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 ////////////////////////////////// const ll N=1e5+56; ll a[N],b[N],T[N<<5],L[N<<5],R[N<<5],t[N<<5],cnt; ll build(ll l,ll r) { ll rt=++cnt; t[rt]=0; if(l<r) { ll m=(l+r)>>1; L[rt]=build(l,m); R[rt]=build(m+1,r); } return rt; } ll upnode(ll pre,ll x,ll l,ll r) { ll rt=++cnt; L[rt]=L[pre];R[rt]=R[pre];t[rt]=t[pre]+1; if(l<r) { ll m=(l+r)>>1; if(x<=m)L[rt]=upnode(L[pre],x,l,m); else R[rt]=upnode(R[pre],x,m+1,r); } return rt; } ll qsum(ll u,ll v,ll k,ll l,ll r) { if(l>=r)return l; ll x=t[L[v]]-t[L[u]];ll m=(l+r)>>1; if(x>=k)return qsum(L[u],L[v],k,l,m); else return qsum(R[u],R[v],k-x,m+1,r); } ll n,q; int main() { while(cin>>n>>q) { CLR(t,0);CLR(T,0);cnt=0; rep(i,1,n)scanf("%lld",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); ll m=unique(b+1,b+1+n)-b-1; T[0]=build(1,m); rep(i,1,n) { ll t=lower_bound(b+1,b+1+m,a[i])-b; T[i]=upnode(T[i-1],t,1,m); } ll x,y,aa,bb,cc; while(q--) { scanf("%lld%lld",&x,&y); if(y-x<2){printf("-1 ");continue;} aa=b[qsum(T[x-1],T[y], y-x+1 ,1,m)]; bb=b[qsum(T[x-1],T[y], y-x ,1,m)]; cc=b[qsum(T[x-1],T[y], y-x-1 ,1,m)]; ll k=y-x-2; while(bb+cc<=aa&&k>0) { aa=bb; bb=cc; cc=b[qsum(T[x-1],T[y],k,1,m)]; k--; } if(bb+cc<=aa) printf("-1 "); else printf("%lld ",aa+bb+cc); } } return 0; }