1 条题解

  • 2
    @ 2017-11-07 17:06:51
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <set>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n,m,st_size;
    int a[100000+1];
    int s[100000+1];
    int st_t[2000000+1];
    int st_l[2000000+1];
    int st_r[2000000+1];
    int st_mid[2000000+1];
    int st_lc[2000000+1];
    int st_rc[2000000+1];
    int st_sum[2000000+1];
    
    int cmp_1(int x,int y)
    {
        return x<y;
    }
    
    void build_st_1(int &now,int l,int r)
    {
        now=++st_size;
        st_l[now]=l;
        st_r[now]=r;
        st_mid[now]=(l+r)/2;
        if (l<r)
        {
            if (l<=st_mid[now])
                build_st_1(st_lc[now],l,st_mid[now]);
            if (st_mid[now]+1<=r)
                build_st_1(st_rc[now],st_mid[now]+1,r);
        }
    }
    
    void copy_1(int now,int last)
    {
        st_l[now]=st_l[last];
        st_r[now]=st_r[last];
        st_mid[now]=st_mid[last];
        st_lc[now]=st_lc[last];
        st_rc[now]=st_rc[last];
        st_sum[now]=st_sum[last];
    }
    
    void update_st_1(int &now,int last,int p)
    {
        now=++st_size;
        copy_1(now,last);
        st_sum[now]++;
        if (st_l[now]<st_r[now])
        {
            if (p<=st_mid[now])
                update_st_1(st_lc[now],st_lc[last],p);
            else if (st_mid[now]+1<=p)
                update_st_1(st_rc[now],st_rc[last],p);
        }
    }
    
    int ask_st_sum_1(int now,int last,int th)
    {
        if (st_lc[now]==st_rc[now])
            return s[st_l[now]];
        else
        {
            int temp=st_sum[st_lc[now]]-st_sum[st_lc[last]];
            if (temp>=th)
                return ask_st_sum_1(st_lc[now],st_lc[last],th);
            else if (temp<th)
                return ask_st_sum_1(st_rc[now],st_rc[last],th-temp);
        }
    }
    
    int main()
    {
        while (~scanf("%d%d",&n,&m))
        {
            for (int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            memcpy(s,a,sizeof(s));
            sort(&s[1],&s[n+1],cmp_1);
            st_size=0;
            memset(st_t,0,sizeof(st_t));
            memset(st_l,0,sizeof(st_l));
            memset(st_r,0,sizeof(st_r));
            memset(st_mid,0,sizeof(st_mid));
            memset(st_lc,0,sizeof(st_lc));
            memset(st_rc,0,sizeof(st_rc));
            memset(st_sum,0,sizeof(st_sum));
            build_st_1(st_t[st_size],1,n);
            for (int i=1;i<=n;i++)
            {
                int p=lower_bound(&s[1],&s[n+1],a[i])-(&s[0]);
                update_st_1(st_t[i],st_t[i-1],p);
            }
            for (int i=1;i<=m;i++)
            {
                int l,r,th;
                scanf("%d%d%d",&l,&r,&th);
                printf("%d\n",ask_st_sum_1(st_t[r],st_t[l-1],th));
            }
        }
    }
    
  • 1

K-th Number(题面原来就是英文,不是我改的)

信息

难度
9
分类
数据结构 | 平衡树线段树函数式编程 点击显示
标签
递交数
12
已通过
3
通过率
25%
上传者