NOIP考前复习模板

2018-11-09 14:08:46


#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int inf=1<<30;
////////////////////////////////
////////////////////////////////
//读入优化整数 
inline long long Read(){
    long long x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
//读入优化实数 
inline double READ(){
    double x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    if(c=='.'){
        double a=0.1;
        c=getchar();
        while(c>='0'&&c<='9')x+=a*(c-'0'),c=getchar(),a*=0.1;
    }
    return x*f;
}
///////////////////////////////////
///////////////////////////////////
const int mx=101010;//数组大小 
const int N=101100;//点数
const int M=205050;//边数 
///////////////////////////////////////////
///////////////////////////////////////////
//树状数组 
struct TREE{
#define lowbit(i) i&-i
long long tree[mx]; 
int n;
inline void add(int i,int x,long long a[]){
    while(i<=n){
        a[i]+=x;
        i+=lowbit(i);
    }
}//单点更新 
inline long long querysum(int i,long long a[]){
    long long ans=0;
    while(i>0){
        ans+=a[i];
        i-=lowbit(i);
    }
    return ans;
}
long long c1[mx],c2[mx];//差分数组,差分的差分数组 
inline void LRupdate(int l,int r,int x){
    add(l,x,c1),add(r+1,-x,c1);
    add(l,(l-1)*x,c2),add(r+1,-r*x,c2);
}//区间更新
inline long long queryLR(int l,int r){
    long long s1=r*querysum(r,c1)-querysum(r,c2);
    long long s2=(l-1)*querysum(l-1,c1)-querysum(l-1,c2);
    return s1-s2;
} //区间查询    
}T1;
///////////////////////////////////////////
///////////////////////////////////////////
//线段树
struct T{//对应数组 
    long long val;
    long long add;
    int l;
    int r;
};
struct SegTree{
T tr[mx<<2];
inline void pushdown(int i){
    if(tr[i].add){
        tr[i<<1].val+=(tr[i<<1].r-tr[i<<1].l+1)*tr[i].add;
        tr[i<<1].add+=tr[i].add;
        tr[i<<1|1].val+=(tr[i<<1|1].r-tr[i<<1|1].l+1)*tr[i].add;
        tr[i<<1|1].add+=tr[i].add;
        tr[i].add=0;
    }
}
long long a[mx];//原数组 
void build(int i,int l,int r){
    tr[i].l=l,tr[i].r=r;
    if(l==r){
        tr[i].val=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tr[i].val=tr[i<<1].val+tr[i<<1|1].val;
}
void update(int i,int l,int r,long long x){
    if(tr[i].l>r||l>tr[i].r)return;
    if(l<=tr[i].l&&tr[i].r<=r){
        tr[i].val+=(tr[i].r-tr[i].l+1)*x;
        tr[i].add+=x;
        return;
    }
    pushdown(i);
    update(i<<1,l,r,x);
    update(i<<1|1,l,r,x);
    tr[i].val=tr[i<<1].val+tr[i<<1|1].val;
}//[l,r]更新 
long long query(int i,int l,int r){
    if(tr[i].l>r||l>tr[i].r)return 0;
    if(l<=tr[i].l&&tr[i].r<=r)return tr[i].val;
    pushdown(i);
    return query(i<<1,l,r)+query(i<<1|1,l,r);
}//区间查询 
}T2;
////////////////////////////////////////////////////
///////////////////////////////////////////////////
//二叉堆 
struct HHeap{//每个堆内的元素 
    int h;//优先级
    int pos;//位置等信息 
    bool operator > (const HHeap &x){
        return h<x.h;//因为后面要写dijstra,所以就用小根堆了
//      return h>x.h;//大根堆 
    } 
};
struct Heap{
#define swap(x,y) x^=y^=x^=y
int siz;
HHeap heap[mx];
inline void sswap(HHeap &a,HHeap &b){
    swap(a.h,b.h);
    swap(a.pos,b.pos);
}
void insert(HHeap a){
    heap[++siz]=a;
    int fa,now;
    now=siz;
    while(now){
        fa=now>>1;
        if(heap[now]>heap[fa])sswap(heap[now],heap[fa]),now=fa;
        else break;
    }
}//插入x 
void pop(){
    sswap(heap[siz],heap[1]);
    siz--;
    int now=1,son;
    while((now<<1)<=siz){
        son=now<<1;
        if(son<siz&&heap[son|1]>heap[son])son|=1;
        if(heap[son]>heap[now])sswap(heap[son],heap[now]),now=son;
        else break;
    }
}
}H;
/////////////////////////////////////
//////////////////////////////////////
////dijstra 
struct Dijstra{
int n,m;
int dist[N],vis[N];
int s;//起点 
struct Node{
    int v;
    int val;
    int next;
}node[M];
int top,head[N];
Heap h;//堆
inline void addedge(int u,int v,int val){
    node[++top].v=v;
    node[top].val=val;
    node[top].next=head[u];
    head[u]=top;
}
void dijstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    HHeap now;
    now.pos=s,now.h=0;
    h.insert(now);
    while(h.siz){
        int u=h.heap[1].pos;
        h.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=node[i].next){
            int d=node[i].v;
            if(dist[d]>dist[u]+node[i].val){
                dist[d]=dist[u]+node[i].val;
                now.pos=d,now.h=dist[d];
                h.insert(now);//入堆 
            }
        }
    }
} 
}D;
/////////////////////////////////////
////////////////////////////////////////
//树链剖分//由于不想写取模,所以过不了板子 
struct  SLPF{
int n,m;
struct Node{
    int v;
    int next;
}node[N<<1];
int cnt,head[N];
inline void addedge(int u,int v){
    node[++cnt].v=v;
    node[cnt].next=head[u];
    head[u]=cnt;
}
inline void add(int u,int v){
    addedge(u,v);
    addedge(v,u);
}
int dep[N],siz[N],fa[N],son[N],top[N];
int T,dfn[N],real[N];
int a[N];
void dfs1(int u){
    siz[u]=1;
    for(int i=head[u];i;i=node[i].next){
        int d=node[i].v;
        if(fa[u]!=d){
            fa[d]=u;
            dep[d]=dep[u]+1;
            dfs1(d);
            siz[u]+=siz[d];
            if(siz[d]>siz[son[u]])son[u]=d;
        }
    }
}
void dfs2(int u,int tp){
    dfn[u]=++T;
    real[dfn[u]]=u;
    top[u]=tp;
    if(son[u])dfs2(son[u],tp);
    for(int i=head[u];i;i=node[i].next){
        int d=node[i].v;
        if(fa[u]!=d&&son[u]!=d)dfs2(d,d);
    }
}
void changepath(int u,int v,int x){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]])swap(u,v);
        T2.update(1,dfn[top[v]],dfn[v],x);
        v=fa[top[v]];
    }
    if(dep[u]>dep[v])swap(u,v);
    T2.update(1,dfn[u],dfn[v],x);
}
long long querypath(int u,int v){
    long long ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]])swap(u,v);
        ans+=T2.query(1,dfn[top[v]],dfn[v]);
        v=fa[top[v]];
    }
    if(dep[u]>dep[v])swap(u,v);
    ans+=T2.query(1,dfn[u],dfn[v]);
    return ans;
}
void changetree(int u,int x){
    int l=dfn[u];
    int r=dfn[u]+siz[u]-1;
    T2.update(1,l,r,x);
}
long long querytree(int u){
    int l=dfn[u];
    int r=dfn[u]+siz[u]-1;
    return T2.query(1,l,r);
} 
void init(){
    n=Read();
    register int i;
    for(i=1;i<=n;i++) a[i]=Read();
    for(i=1;i<n;i++) add(Read(),Read());
    dfs1(1);
    dfs2(1,1);
    for(i=1;i<=n;i++)T2.a[i]=a[real[i]];
    T2.build(1,1,n);
}//初始化 
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]])swap(u,v);
        v=fa[top[v]];
    }
    return dep[u]<dep[v]?u:v;
}
}slpf;
//////////////////////////////////////
//////////////////////////////////////
//左偏树(小根堆) 
struct LPT{
struct Tree{
    int len;//距离 
    int h;//优先级
    int f;//父亲 
    int ls,rs;//左右儿子 
}t[N];
int merge(int a,int b){
    if(a==0||b==0)return a+b;//有一个为空 
    if(t[a].h>t[b].h)swap(a,b);//小根堆
    t[a].rs=merge(t[a].rs,b);
    t[t[a].rs].f=a;
    if(t[t[a].rs].len>t[t[a].ls].len)swap(t[a].ls,t[a].rs);
    t[a].len=t[t[a].rs].len+1;
    return a; 
}//合并两个堆 
void pop(int x){
    t[t[x].ls].f=t[t[x].rs].f=0;
    merge(t[x].ls,t[x].rs);//合并左右儿子 
}//堆顶出堆
int find(int x){
    while(t[x].f)x=t[x].f;
    return x;
}//查找堆顶 
}H2;
//////////////////////////////////
/////////////////////////////////
//线性基
struct Line{
long long b[65];//线性基数组
bool insert(long long val){
    register int i;
    for(i=63;i>=0;i--){
        if((val&((long long)1<<i))!=0){
            if(b[i]==0){//最高位为该位的数还没有 
                b[i]=val;
                return 1;
            }
            val^=b[i];
        }
    }
    return 0;//插入失败 
}//插入val    
Line merge(const Line &a,const Line &b){
    Line s=a;
    for(register int i=63;i>=0;i--){
        if(b.b[i]){//把一个线性基暴力地插入另一个中 
            s.insert(b.b[i]);
        }
    }
    return s;
}//合并两个线性基
bool find(long long val){
    return !insert(val);
}//val是否在线性基内
long long query_max(){
    long long ans=0;
    for(int i=63;i>=0;i--){
        if((ans^b[i])>ans)ans^=b[i];
    }
    return ans;
}//查询最大异或和
long long query_min(){
    for(int i=0;i<=63;i++)if(b[i])return b[i];
    return 0;
}//查询最小异或和
long long query_maxn(long long x){
    long long ans=x;
    for(int i=63;i>=0;i--){
        if((ans^b[i])>ans)ans^=b[i];
    }
    return ans;
}//查询包含x的最大异或和 (x不在线性基内)
long long query_minn(long long x){
    long long ans=x;
    for(int i=0;i<=63;i++){
        if((ans^b[i])<ans)ans^=b[i];
    }
    return ans;
}//查询包含x的最小异或和(x不在线性基内) 
}L; 
///////////////////////////////////////////
//////////////////////////////////////////
//字典树 
const int len=1001010;//所有单词包含字母的总数 
struct Tire{
int cnt;//字母数
int son[len][26];//以只有小写字母为例 
bool end[len];
void insert(char s[]){
    int now=0;
    int a;
    int l=strlen(s);
    for(int i=0;i<l;i++){
        a=s[i]-'a';
        if(son[now][a])now=son[now][a];
        else son[now][a]=++cnt,now=cnt;
    }
    end[now]=1;//标记该单词出现了 
}//插入单词 
bool find(char s[]){
    int now=0;
    int a;
    int l=strlen(s);
    for(int i=0;i<l;i++){
        a=s[i]-'a';
        if(son[now][a])now=son[now][a];
        else return 0;
    }
    if(end[now])return 1;
    return 0;
}//查找某个单词是否出现过 
};
////////////////////////////////
////////////////////////////////
//(带修改)莫队
//由于涉及排序,好像不资瓷结构体 
int cnt[mx];
int a[mx];//原数组
int ansk[mx];//答案 
int cntq,cntc;//询问和修改的次数 
int ans;
int n;
int now;//当前处理到了第几个询问 
int st;//块的大小 
int l,r;//当前询问的左右端点 
inline void del(int x){
    cnt[a[x]]--;
    if(cnt[a[x]]==0)ans--;
}   
inline void add(int x){
    cnt[a[x]]++;
    if(cnt[a[x]]==1)ans++;
}
struct Qu{//询问 
    int l,r;//每个询问左右端点 
    int pos;//每个询问位置 
    int pre;//每个询问最近的修改位置 
}qu[mx];
struct C{//修改 
    int pos;
    int color;
}c[mx];
bool cmp(Qu a,Qu b){
    if(a.l/st!=b.l/st)return a.l/st<b.l/st;
    if(a.r/st!=b.r/st){
        if((a.l/st)&1)return a.r<b.r;
        else return a.r>b.r;
    }
    return a.pre<b.pre;
}//带修改莫队排序方式
//bool cmp(Qu a,Qu b){
//  if(a.l/st!=b.l/st)return a.l<b.l;
//  if((a.l/st)&1)return a.r<b.r;
//  return a.r>b.r;
//}//不带修改的莫队排序方式
void change(int i){//第i个询问需要的修改 
    if(qu[i].r>=c[now].pos&&qu[i].l<=c[now].pos){//本次修改会产生影响
        if(--cnt[a[c[now].pos]]==0)ans--;//把该颜色的最后一个拿掉了
        if(++cnt[c[now].color]==1)ans++;//第一次出现该颜色 
    }
    swap(a[c[now].pos],c[now].color); 
}
int query(int i){//处理第i个询问
    while(l<qu[i].l)del(l++);
    while(l>qu[i].l)add(--l);
    while(r<qu[i].r)add(++r);
    while(r>qu[i].r)del(r--);//不带修改的莫队只有前四排
    while(now<qu[i].pre)change(++now);
    while(now>qu[i].pre)change(now--);
    return ans; 
}
void init(){
    //根据题目描述输入询问和修改 
//  st=n/sqrt(cntq*2/3);//不带修改的快的大小
    st=exp((log(n)+log(cntq))/3);//带修改的块的大小
    sort(qu+1,qu+1+cntq,cmp);
    for(int i=1;i<=cntq;i++)ansk[qu[i].pos]=query(i);
} 
/////////////////////////////////////////////
/////////////////////////////////////////////
//tarjan(缩点与2-sat)
struct Tarjan{
    int n,m;
int top,head[N];
struct Node{
    int v;
    int next;
}node[M];
inline void addedge(int u,int v){
    node[++top].v=v;
    node[top].next=head[u];
    head[u]=top;
}
int Belong[N];//每个点属于哪个强连通分量 
int dfn[N],T,low[N];
int st[N];//栈 
bool instack[N];//是否在栈中 
int sttop;//栈顶
int taj;//强连通分量数 
void dfs(int u){
    dfn[u]=low[u]=++T;
    st[++sttop]=u;
    instack[u]=1;
    for(int i=head[u];i;i=node[i].next){
        int d=node[i].v;
        if(dfn[d]==0){
            dfs(d);
            low[u]=min(low[u],low[d]);
        }else if(instack[d])low[u]=min(low[u],low[d]);
    }
    if(low[u]==dfn[u]){
        int now;
        taj++;
        do{
            now=st[sttop--];
            instack[now]=0;
            Belong[now]=taj;
            //在此可以进行累加点权等操作 
        }while(now!=u);
    }
}
Node newnode[M];
int newtop;
int newhead[N];
inline void newaddedge(int u,int v){
    newnode[++newtop].v=v;
    newnode[newtop].next=newhead[u];
    newhead[u]=newtop;
} 
void suodian(){
    for(int i=1;i<=n;i++)if(dfn[i]==0)dfs(i);
    for(int i=1;i<=n;i++){
        int u=Belong[i];
        for(int j=head[i];j;j=node[j].next){
            int d=node[j].v;
            int v=Belong[d];
            if(u!=v)newaddedge(u,v);
        }
    }
}
void Two_SAT(){
    n=Read(),m=Read();
    //[1,n]表示真,[n+1,2n]表示假 
    for(int i=1;i<=m;i++){
        int a,fa,b,fb;
        a=Read(),fa=Read(),b=Read(),fb=Read();
        addedge(a+(fa^1)*n,b+fb*n);
        addedge(b+(fb^1)*n,a+fa*n);
    }
    for(int i=1;i<=2*n;i++)if(dfn[i]==0)dfs(i);
    bool f=1;
    for(int i=1;i<=n;i++)if(Belong[i]==Belong[i+n])f=0;
    if(f)printf("POSSIBLE\n");
    else printf("IMPOSSIBLE\n");
    if(f)for(int i=1;i<=n;i++)printf("%d ",Belong[i]>Belong[i+n]);
}
}TJ;
//////////////////////////////////
///////////////////////////////////
//splay
struct Splay{
int son[mx][2],f[mx],siz[mx],key[mx],cnt[mx],root;
int n,sz;//点数,当前有多少数在splay内
inline void update(int x){
    if(x)siz[x]=cnt[x]+(son[x][0]?siz[son[x][0]]:0)+(son[x][1]?siz[son[x][1]]:0);
} 
inline void clear(int x){siz[x]=key[x]=cnt[x]=son[x][0]=son[x][1]=f[x]=0;}
inline bool get(int x){return son[f[x]][1]==x;}
inline void rotate(int x){
    int F=f[x],FF=f[F],WF=get(x),WFF=get(F);
    int other=son[x][WF^1];
    f[x]=FF;
    if(F)son[FF][WFF]=x;
    f[F]=x;
    son[x][WF^1]=F;
    f[other]=F;
    son[F][WF]=other;
    update(F);
    update(x);
}
inline void splay(int x){
    for(int F=f[x];(f[x]);rotate(x),F=f[x]){
        if(f[F])rotate(get(x)==get(F)?F:x);
    }
    root=x;
}
void insert(int v){
    if(root==0){
        sz++;
        cnt[sz]=siz[sz]=1;
        son[sz][0]=son[sz][1]=f[sz]=0;
        key[sz]=v;
        root=sz;
        return;
    }
    int now=root,F=0;
    while(1){
        if(key[now]==v){//已经插入过了
            cnt[now]++;
            update(now);
            update(F);
            splay(now); 
            return;
        }
        F=now;
        now=son[now][key[now]<v];
        if(now==0){
            ++sz;
            cnt[sz]=siz[sz]=1;
            son[sz][0]=son[sz][1]=0;
            f[sz]=F;
            son[F][key[F]<v]=sz;
            key[sz]=v;
            update(F);
            splay(sz);
            return;
        }
    }
}//删除v 
int find(int v){
    int ans=0,now=root;
    while(1){
        if(key[now]>v)now=son[now][0];
        else {
            ans+=(son[now][0]?siz[son[now][0]]:0);
            if(v==key[now]){
                splay(now);
                return ans+1;
            }
            ans+=cnt[now];
            now=son[now][1];
        }
    } 
}//查v的排名 
int findx(int x){
    int now=root;
    while(1){
        if(son[now][0]&&x<=siz[son[now][0]])now=son[now][0];
        else{
            int temp=(son[now][0]?siz[son[now][0]]:0)+cnt[now];
            if(x<=temp)return key[now];
            now=son[now][1];
            x-=temp;
        }
    }
}//查找排名为x的值
//注意查前驱之前要先插入v,查完之后要删除v 
inline int query_pre(){
    int now=son[root][0];
    while(son[now][1])now=son[now][1];
    return now;
}//查前驱 
inline int query_aft(){
    int now=son[root][1];
    while(son[now][0])now=son[now][0];
    return now;
}//查后继 
inline void del(int v){
    find(v);//把v旋转到根 
    if(cnt[root]>1){//不止一个点 
        cnt[root]--;
        update(root);
        return;
    }
    if(son[root][0]==0&&son[root][1]==0){//只有根节点一个点 
        clear(root);
        root=0;
        return;
    }
    if(son[root][0]==0){//只有右子树 
        int oldroot=root;
        root=son[root][1];
        f[root]=0;
        clear(oldroot);
        return;
    }
    if(son[root][1]==0){//只有左子树
    int oldroot=root;
    root=son[root][0];
    f[root]=0;
    clear(oldroot);
    return; 
    }
    //有两个子树时:
    int newroot=query_pre(),oldroot=root;//用前驱做新根
    splay(newroot);//把前驱旋转到根 
    f[son[oldroot][1]]=root;//经过旋转root==newroot
    son[root][1]=son[oldroot][1];
    clear(oldroot);
    update(root); 
}//删除v 
}SPLAY;
////////////////////////////////
////////////////////////////////
//LCT
struct LCT{
int n,m;
struct Lct{
    int son[2];
    int f;//父亲 
    bool t;//翻转标记 
}lct[N];
#define swap(x,y) x^=y^=x^=y
inline void pushdown(int x){
    if(lct[x].t){
        swap(lct[x].son[0],lct[x].son[1]);
        lct[lct[x].son[0]].t^=1;
        lct[lct[x].son[1]].t^=1;
        lct[x].t=0;
    }
}
inline void update(int x){
//视题目而定 
}   
inline bool get(int x){return lct[lct[x].f].son[1]==x;}
inline bool isroot(int x){return lct[lct[x].f].son[1]!=x&&lct[lct[x].f].son[0]!=x;}
inline void rotate(int x){
    int F=lct[x].f,FF=lct[F].f,WF=get(x),WFF=get(F);
    int other=lct[x].son[WF^1];
    lct[x].f=FF;
    if(!isroot(F))lct[FF].son[WFF]=x;
    lct[other].f=F;
    lct[F].son[WF]=other;
    lct[x].son[WF^1]=F;
    lct[F].f=x;
    update(F);
    update(x);
}
int st[mx];//栈 
inline void splay(int x){
    int top=0,now=x;
    st[++top]=now;
    while(!isroot(now))now=lct[now].f,st[++top]=now;
    while(top)pushdown(st[top--]);
    for(int F=lct[x].f;!isroot(x);rotate(x),F=lct[x].f){
        if(!isroot(F))rotate(get(x)==get(F)?F:x);
    }
}
inline void access(int x){//把x到根的路径改为实链 
    int pre=0;
    while(x){
        splay(x);
        lct[x].son[1]=pre;
        pre=x;
        update(x);
        x=lct[x].f;
    }   
}
inline void makeroot(int x){//把x改为根 
    access(x);
    splay(x);
    lct[x].t^=1;
}
inline int findroot(int x){//找到x的根 
    access(x);
    splay(x);
    pushdown(x);
    while(lct[x].son[0])x=lct[x].son[0];//根节点一定是最浅的 
    return x;
}
inline void spilt(int x,int y){//把x到y的路径放在一根实链上 
    makeroot(x);
    access(y);
    splay(y);
}
inline void link(int x,int y){//x与y加边
    makeroot(x);
    if(findroot(y)!=x)//已经连通就不用加边了 
    lct[x].f=x;//findroot过程中已经把y旋转到根了 
}
inline void cut(int x,int y){//x与y删边
    makeroot(x);
    if(findroot(y)!=x)return;//不连通就不用删边了
    if(lct[x].f!=y||lct[y].son[0]!=x)return;//经过findroot,y成为了根 
    if(lct[x].son[1])return;//x的右儿子一定是比x深又比y浅的,即在他们之间,他们之间没有边
    lct[x].f=0;
    lct[y].son[0]=0; 
    update(y);
}
}LCT_Tree;
//////////////////////////////////
//////////////////////////////////
//线性筛素数
struct Line_Prime{
int Prime[mx];
int o;//当前晒出了几个素数 
bool chick[mx];
void solve(int n){//从1到n的素数 
    register int i,j;
    chick[1]=1;
    for(i=2;i<=n;i++){
        if(chick[i]==0){
            Prime[++o]=i; 
        }
        for(j=1;j<=o;j++){
            if(i*Prime[j]>n)break;
            chick[i*Prime[j]]=1;
            if(i%Prime[j]==0)break;
        }
    }
}
}LineP;
/////////////////////////////////////
//////////////////////////////////////
//主席树
struct ZXTree{
int cnt;//现在有多少个点
int n,m;//n个数,m个询问 
int q;//去重后后有多少个点 
int l[mx<<5],r[mx<<5],root[mx],siz[mx<<5];
int a[mx],b[mx];//原数组,去重数组 
void build(int &t,int ll,int rr){
    t=++cnt;
    if(ll==rr)return;
    int mid=(ll+rr)>>1;
    build(l[t],ll,mid);
    build(r[t],mid+1,rr);
}//建空树 
int insert(int t,int ll,int rr,int p){
    int o=++cnt;
    l[o]=l[t],r[o]=r[t],siz[o]=siz[t]+1;
    if(ll==rr)return o;
    int mid=(ll+rr)>>1;
    if(p<=mid)l[o]=insert(l[o],ll,mid,p);
    else r[o]=insert(r[o],mid+1,rr,p);
    return o;
}//插入(去重后)第p大的新节点
int query(int u,int v,int ll,int rr,int k){
    if(ll==rr)return ll;
    int mid=(ll+rr)>>1,x=siz[l[v]]-siz[l[u]];
    if(x>k)return query(l[u],l[v],ll,mid,k);
    else return query(r[u],r[v],mid+1,rr,k-x);
}//查询区间[u-1,v]第k小 
int twopoint(int x){
    int ll=1,rr=q;
    int mid;
    while(1){
        mid=(ll+rr)>>1;
        if(b[mid]==x)return mid;
        if(b[mid]>x)rr=mid-1;
        else ll=mid+1;
    }
}//二分出x是去重后第几大(用于插入前的预处理) 
void init(){
    register int i;
    n=Read(),m=Read();
    for(i=1;i<=n;i++)a[i]=Read(),b[i]=a[i];
    sort(b+1,b+1+n);
    q=unique(b+1,b+1+n)-b-1;//去重后一共多少种数 
    build(r[0],1,q);
    for(i=1;i<=n;i++){
        //嫌麻烦不想手写二分可以调用stl
        //p=lower_bound(b+1,b+1+q,a[i])-b; 
        root[i]=insert(root[i-1],1,q,twopoint(a[i]));
    }
    int ll,rr,k;
    for(i=1;i<=m;i++){
    ll=Read(),rr=Read(),k=Read();
    printf("%d\n",b[query(root[ll-1],root[rr],1,q,k)]);
    }
}
};
////////////////////////////////
///////////////////////////////
//最小费用最大流(DInic)
struct MINcostMAXflow{
int n,m,s,t;
int maxflow,cost;
int top;
int head[N];
void init(){top=1;}
struct Node{
    int v;
    int val;
    int next;
    int w;
}node[M];
inline void addedge(int u,int v,int val,int w){
    node[++top].v=v;
    node[top].next=head[u];
    node[top].w=w;
    node[top].val=val;
    head[u]=top;
}
inline void add(int u,int v,int val,int w){
    addedge(u,v,val,w);
    addedge(v,u,0,-w);
}
int inque[N],dist[N],vis[N];
int cur[N];//当前弧 
bool spfa(){
    for(int i=1;i<=t;i++)cur[i]=head[i],dist[i]=inf;
    queue<int>q;
    q.push(s);
    dist[s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(int i=head[u];i;i=node[i].next){
            int d=node[i].v;
            if(dist[d]>dist[u]+node[i].w){
                dist[d]=dist[u]+node[i].w;
                if(!inque[d]){
                    q.push(d);
                    inque[d]=1;
                }
            }
        }
    }
    return dist[t]!=inf;
}
int dfs(int u,int flow){
    if(u==t){
        maxflow+=flow;
        return flow;
    }
    int used=0;
    vis[u]=1;
    for(int i=head[u];i;i=node[i].next){
        int d=node[i].v;
        if((vis[d]==0||d==t)&&dist[d]==dist[u]+node[i].w){
            int mi=dfs(d,min(node[i].val,flow-used));
            if(mi){
                node[i].val-=mi;
                node[i^1].val+=mi;
                cost+=node[i].w*mi;
                used+=mi;
                if(used==flow)break;
            }
        }
    }
    return used;
}
void Dinic(){
    while(spfa()){
        vis[t]=1;
        while(vis[t]){
            memset(vis,0,sizeof(vis));
            dfs(s,inf);
        }
    }
}
};
////////////////////////////////
///////////////////////////////////
//并查集
struct BCJ{
int set[mx];
int n;
void init(){
    for(int i=1;i<=n;i++)set[i]=i;
}
int find(int x){
    return set[x]==x?x:set[x]=find(set[x]);
}   
void merge(int x,int y){
    int sx=find(x),sy=find(y);
    if(sx==sy)return;
    if(sx>sy)swap(sx,sy);
    set[sy]=sx;
}
}; 
/////////////////////////////////
////////////////////////////////
//floyd
struct Floyd{
int go[1010][1010];
int n;
void solve(){
    int i,j,k;
    for(k=1;k<=n;k++){
        for(j=1;j<=n;j++){
            for(i=1;i<=n;i++){
                go[i][j]=min(go[i][j],go[i][k]+go[k][j]);
            }
        }
    }
}   
};
////////////////////////////////////////
////////////////////////////////////////
//vector实现平衡树
struct VSplay{
/*一些关于vector的函数 
定义:vector<int>a; 需<vector>头文件
访问元素:a[x]  取出a中的第(x+1)个数(下标从0开始 O(1)
a.begin():返回起始元素的迭代器 O(1)
a.end():返回终止元素的迭代器 O(1)
a.insert(a.begin()+pos,x):在第pos个数后面插入x O(n)
a.erase(a.begin()+pos):删除pos位置的数 pos之后的数自动补齐 O(n)
lower_bound(a.begin(),a.end(),x)返回第一个大于等于x的位置的迭代器 O(logn)
upper_bound(a.begin(),a.end(),x)返回第一个大于x的位置的迭代器(x的后继或x) O(logn)
*it:取出迭代器it中的值*/
vector<int>v;
void insert(int x){//插入x 
    v.insert(upper_bound(v.begin(),v.end(),x),x);
}   
void del(int x){//删除x
    v.erase(lower_bound(v.begin(),v.end(),x)); 
}  
int find_kth(int x){//查询x的排名
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1; 
}
int find_val(int x){//查询排名为x的数
    return v[x-1]; 
}
int find_pre(int x){//查前驱
    return *--lower_bound(v.begin(),v.end(),x);  
}
int find_aft(int x){//查后继 
    return *upper_bound(v.begin(),v.end(),x);
}
}; 
///////////////////////////////////////////
//////////////////////////////////////////////
//高精度
struct Bign{
    int len,s[mx];;
    Bign(){len=1,memset(s,0,sizeof(s));}
    Bign(int num){*this=num;}
    Bign(const char *num){*this=num;}
    Bign operator = (const int num){
        char st[mx];
        sprintf(st,"%d",num);
        return *this=st;
    }
    Bign operator = (const char *num){
        len=strlen(num);
        for(int i=0;i<len;i++)s[i]=num[len-i-1]-'0';
        return *this;
    }
    void clean(){while(len&&s[len-1]==0)len--;}
    Bign operator + (const Bign &x){
        Bign c;
        int l=max(len,x.len);
        for(int i=0;i<l;i++){
            c.s[i]+=s[i]+x.s[i];
            c.s[i+1]+=c.s[i]/10;
            c.s[i]%=10;
        }
        c.len=l+1;
        c.clean();
        return c;
    }
    Bign operator - (const Bign &x){
        Bign c=*this;
        int l=max(len,x.len);
        for(int i=0;i<l;i++){
            c.s[i]-=x.s[i];
            if(c.s[i]<0){
                c.s[i+1]--;
                c.s[i]+=10;
            }
        }
        c.clean();
        return c;
    }
    Bign operator * (const Bign &b){
        Bign c;
        for(int i=0;i<len;i++){
            for(int j=0;j<b.len;j++){
                c.s[i+j]+=s[i]*b.s[j];
                c.s[i+j+1]+=c.s[i+j]/10;
                c.s[i+j]%10;
            }
        }
        c.len=len+b.len+1;
        c.clean();
        return c;
    }
    bool operator > (const Bign &b){
        if(len!=b.len)return len>b.len;
        for(int i=len-1;i>=0;i--){
            if(s[i]!=b.s[i])return s[i]>b.s[i];
        }
        return 0;//相等 
    }
    string str() const{
        string re="";
        for(int i=0;i<len;i++)re=(char)(s[i]+'0')+re;
        return re;
    }
}; 
istream &operator >> (istream &in,Bign &x){
    string s;
    cin>>s;
    x=s.c_str();
    return in;
}
ostream &operator << (ostream &out,const Bign &x){
    out<<x.str();
    return out;
}
////////////////////////////
////////////////////////////
//矩阵快速幂
const int mod=(1e9)+7;//常见模数 
struct MatMul{
struct Mat{
    long long mat[101][101]; 
    int n,m;//n行m列的矩阵 
    Mat(){memset(mat,0,sizeof(mat));n=m=0;}
};
int n;
Mat e;
void init(){for(int i=0;i<=n;i++)e.mat[i][i]=1;}//预处理出单位矩阵 
Mat Mul(Mat x,Mat y){//x与y相乘
    register int i,j,k1;
    if(x.m!=y.n)return e;//必须满足能相乘的条件 
    Mat out;
    int n=x.n;
    int k=x.m;
    int m=y.m;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            for(k1=1;k1<=k;k1++){
                out.mat[i][j]=(x.mat[i][k1]*y.mat[k1][j]+out.mat[i][j])%mod;
            }
        }
    }
    return out;
}
Mat pow(Mat x,long long k){//x矩阵的k次方
    Mat ans=e;
    Mat base=x;
    while(k){
        if(k&1)ans=Mul(ans,base);
        base=Mul(base,base);
        k>>=1;
    } 
    return ans;
}
}; 
//////////////////////////
//////////////////////////
//背包
struct BackPack{
int dp[101010];//滚动数组 
int n,W;//物品总数,总重量 
int val[101010];//每个物品的价值 
int w[101010];//每个物品的重量 
void solve_01(){//01背包 
    int i,j;
    for(i=0;i<=n;i++){
        for(j=W;j>=w[i];j--){//倒序循环防止多取 
            dp[j]=max(dp[j],dp[j-w[i]]+val[i]);
        }
    }
    printf("%d",dp[W]);
}
void solve_CM(){//完全背包
    int i,j;
    for(i=0;i<=n;i++){
        for(j=w[i];j<=W;j++){//正序循环可以多取 
            dp[j]=max(dp[j],dp[j-w[i]]+val[i]);
        }
    } 
    printf("%d",dp[W]);
}
}; 
////////////////////////////////
///////////////////////////////
//扩展欧几里得
struct EXGCD{
void exgcd(int a,int b,int &d,int &x,int &y){
    if(!b){
        d=a;x=1;y=0;
    }
    else{
        exgcd(b,a%b,d,y,x);//输入时要保证a>b否则会死循环
        y-=x*(a/b); 
    }
}//求解ax+by==gcd(a,b),d为最大公因数,x,y为对应系数 
}; 
////////////////////////////
////////////////////////////
//大概复习完了吧 
int main(){
    int noip_2018_score=0;
    while(noip_2018_score<=600)noip_2018_score++;
    printf("Your will AK noip 2018 TG");
    int noip_2018_rp=0;
    while(1)noip_2018_rp++;
    return 0;
}

学OI以来打过最长的代码(第一个比无限之环还长的代码)