专栏首页wym2019HDU多校赛第二场 HDU 6601 Keen On Everything But Triangle( 主席树求区间第k大)

2019HDU多校赛第二场 HDU 6601 Keen On Everything But Triangle( 主席树求区间第k大)

题意:求区间[ 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2038:[2009国家集训队]小Z的袜子(hose)

    用户2965768
  • P3834 【模板】可持久化线段树 1(主席树) (多次查询第k大或第k小)

    用户2965768
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • 2020-10-22在线识图搜索引擎

    最近在逛淘宝时发现了淘宝的图片搜索功能,可能是我太Low了这个技术点已经实现很长时间了。想想自己能不能实现这个功能,起初我是这么想的,对两张图片从左上角的第一个...

    爱笑的架构师
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • 【2020HBU天梯赛训练】7-41 互评成绩

    学生互评作业的简单规则是这样定的:每个人的作业会被k个同学评审,得到k个成绩。系统需要去掉一个最高分和一个最低分,将剩下的分数取平均,就得到这个学生的最后成绩。...

    韩旭051
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    提莫队长
  • 洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

    小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。

    attack
  • hdu1025

    @坤的

扫码关注云+社区

领取腾讯云代金券