题意：求区间[ l , r ]能构成三角形周长最大的，不存在就输出-1
解：主席树模版
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 300000; int sum[maxn*20+5];//sum为森林的不同根结点 struct E { ll num; int l,r; } t[maxn*20+5]; //t为tree树 int n,sz,m,cnt; ll a[maxn],b[maxn]; int build(int l,int r) { int now = ++cnt; int mid = (l+r)>>1; if(l<r) { t[now].l = build(l,mid); t[now].r = build(mid+1,r); } return now; } int update(int l,int r,int last,int p) { int now = ++cnt; t[now].num = t[last].num+1; t[now].l = t[last].l; t[now].r = t[last].r; int mid = (l + r)>>1; if(l<r) { if(p<=mid)t[now].l = update(l,mid,t[last].l,p); else t[now].r = update(mid+1,r,t[last].r,p); } return now; } ll query(int u,int v,int l,int r,int k) { if(l==r)return l; // v 左孩子包含点个数减去 u 左孩子包含点的个数 int tmp = t[t[v].l].num - t[t[u].l].num; int mid = (l+r)>>1; if(k<=tmp)return query(t[u].l,t[v].l,l,mid,k); else return query(t[u].r,t[v].r,mid+1,r,k - tmp); } bool judge(ll x,ll y,ll z){ if(y+z>x){ return true; } return false; } int main() { ll t1,t2,t3; while(scanf("%d %d",&n,&m)==2) { for(int i=1; i<=n; i++)scanf("%lld",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); sz = unique(b+1,b+n+1) - (b+1); cnt = 0; sum[0] = build(1,sz);//建立空树 for(int i=1; i<=n; i++) a[i] = lower_bound(b+1,b+sz+1,a[i]) - b; for(int i=1; i<=n; i++) sum[i] = update(1,sz,sum[i-1],a[i]); while(m--) { int u,v,k = 4,flag=0; scanf("%d %d",&u,&v); if(v-u+1<3){ printf("-1\n"); continue; } int len = v - u + 1; t1 = query(sum[u-1],sum[v],1,sz,len-1+1); t1 = b[t1]; t2 = query(sum[u-1],sum[v],1,sz,len - 2+1); t2 = b[t2]; t3 = query(sum[u-1],sum[v],1,sz,len-3+1); t3 = b[t3]; while(1){ if(judge(t1,t2,t3)){ flag = 1; break; } if(k>len)break; t1 = t2; t2 = t3; t3 = query(sum[u-1],sum[v],1,sz,len-k+1); t3 = b[t3]; k++; } if(flag)printf("%lld\n",t1+t2+t3); else printf("-1\n"); } } return 0; }
