一些模板

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define rg register
#define l() i&-i
using namespace std;

int n,m,a[500010],tree[500010],c,x,y;

inline int lowbit(int x)
{
    return x&(-x);
}

inline void updata(int x,int k)
{
    for(int i=x;i<=n;i+=lowbit(x))
        tree[i]+=k;
}

inline int query(int x)
{
    int ans=0;
    for(int i=x;i;i-=lowbit(x))
        ans+=tree[i];
    return ans;
}
inline int read()
{
    int x=0,f=1;
    char ch;
    while (ch < ‘0‘ || ch > ‘9‘)  {if (ch==‘-‘)f = -1;ch = getchar();}
    while (ch >= ‘0‘ && ch <= ‘9‘){x = x*10+ch-‘0‘;ch = getchar();}
    return f*x;
}

int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        updata(i,a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        c=read();
        if(c==1)
        {
            x=read();
            y=read();
            updata(x,y);
        }
        else
        {
            x=read();
            y=read();
            cout<<query(y)-query(x-1)<<endl;
        }
    }
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define rg register
#define l() i&-i
using namespace std;

int n,x,y,z,k,tree[500010],a,m,last=0;
inline int read()
{
    int x=0,f=1;
    char ch;
    while (ch < ‘0‘ || ch > ‘9‘)  {if (ch==‘-‘)f = -1;ch = getchar();}
    while (ch >= ‘0‘ && ch <= ‘9‘){x = x*10+ch-‘0‘;ch = getchar();}
    return f*x;
}

inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int x,int k)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tree[i]+=k;
}

inline long long query(int x)
{
    long long ans=0;
    for(int i=x;i;i-=lowbit(i))
        ans+=tree[i];
    return ans;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        a=read();
        add(i,a-last);
        last=a;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x;
        if(x==1)
        {
            cin>>y>>z>>k;
            add(y,k);
            add(z+1,-k);
        }
        if(x==2)
        {
            cin>>y;
            cout<<query(y)<<endl;
        }
    }
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define rg register
using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch;
    while (ch < ‘0‘ || ch > ‘9‘)  {if (ch==‘-‘)f = -1;ch = getchar();}
    while (ch >= ‘0‘ && ch <= ‘9‘){x = x*10+ch-‘0‘;ch = getchar();}
    return f*x;
}

int n,q,m,T[200001],tot,a[200001],b[200001];
struct cym{
    int l,r,val;
}tree[8000001];

inline int bulid(int l,int r)// 建树操作 
{
    int bj=++tot;
    tree[bj].val=0;
    int mid=(l+r)>>1;
    if(l>r)
    {
        tree[bj].l=bulid(l,mid);
        tree[bj].r=bulid(mid+1,r);
    }
    return bj;
}

inline int change(int pre,int l,int r,int zone)// 修改 
{
    int bj=++tot;
    tree[bj].l=tree[pre].l;
    tree[bj].r=tree[pre].r;
    tree[bj].val=tree[pre].val+1;
    int mid=(l+r)>>1;
    if(l<r)
    {
        if(zone<=mid)
            tree[bj].l=change(tree[pre].l,l,mid,zone);
        else
            tree[bj].r=change(tree[pre].r,mid+1,r,zone);
    }
    return bj;
}

inline int cx(int from,int to,int l,int r,int k)// 查询 
{
    if(l==r)
        return l;
    int x=tree[tree[to].l].val-tree[tree[from].l].val;
    int mid=(l+r)>>1;
    if(x>=k)
        return cx(tree[from].l,tree[to].l,l,mid,k);
    else
        return cx(tree[from].r,tree[to].r,mid+1,r,k-x);
}
int main()
{
    n=read(),q=read();
    for(rg int i=1;i<=n;i++)
    {
        a[i]=read();
        b[i]=a[i];
    }
    sort(b+1,b+n+1);// 排序 
    m=unique(b+1,b+n+1)-b-1;// 看一共有多少个不重复的元素 
    T[0]=bulid(1,m);// 把最后一个点建在 主席树数组T[0]的位置  
    for(rg int i=1;i<=n;i++)
    {
        int t=lower_bound(b+1,b+m+1,a[i])-b;// 第一个比a[i] 大的树的位置 
        T[i]=change(T[i-1],1,m,t);
    }
    for(rg int i=1;i<=q;i++)
    {
        int l=read(),r=read(),k=read();
        int anss=cx(T[l-1],T[r],1,m,k);
        printf("%d\n",b[anss]);
    }
}