議長木(修正なし)小結

この名前を聞くとこんなに覇気があって、勉強する前に慌てていた.ネット上の多くのチュートリアルは本当にはっきり言えません(私が愚かだと思います)ε=(´ο｀*)))ああ.推薦:説明の良い:(https://www.cnblogs.com/Empress/p/4652449.html)コードが良い:(http://blog.csdn.net/creatorx/article/details/75446472)水ですね....%%%%%%%o(╥﹏╥)o
本題
主席樹は、関数式線分樹とも呼ばれ、この主席がどのように取ってきたのか分からない、という...実は「追加のみ、変更しない」という原則に従って、未修正の情報を保持し、すべて持続化することができます...しかし、まだ修正はありません...
議長ツリーは区間k番目の大きな(小さい)問題を解決することができ,修正を持たないことが基礎であり,修正を伴うには(木状配列)を加えなければならない.
タイトル
区間を与えて、k番目の小さい値を求めます.
構想
1回ごとに1つの区間を並べ替えて、k番目の小さい値を求めます...
はい、議長の木です.の
解法
まずk番目の小さい木を求めて、私たちは線分の木を使うことができます.例を挙げると(上の大物の例を用いた):1 2 5 1 3 2 2 5 1 2 この課権値線分ツリーの葉ノードはこの数の数を表す.非リーフノード(ルートを除く)は、数とを表します.例えば、5番目の小さな値を要求します.まず、根から見ると、左に8つ、5<8があり、5番目の小さな値が左にあることを説明します.次の階の後、左側には7つ、5<7があり、まだ左側にあります.次の階では、左側に3つ、5>3があります.5番目の小さいものは右側にあることを説明します.私たちは今、右側の5-3番目の小さいものを探す必要があります.最終的に見つけたのは2です.
ツリーの複雑さはO(nlogn)であり、クエリーの複雑さはO(logn)である(ここでのNは異なる数の数である)クエリーごとにツリーを構築しても、複雑さは少しも低下しない(かえって向上した).
接頭辞と思想を用いて,区間[l,r]を求め,[1,r]-[1,l-1]を用いればよい.これは[1,1],[1,2]......[1,n]共n本の線分樹を建てたことに相当する.上記の例では、例えば[5,10]のk番目の小値を求める.それぞれ[1,4],[1,10]の,減算すればよい. 上記のクエリの操作を行います.
しかし:n本の線分の木を建てます.......痴人说梦的吧.....空間が爆発しないのはおかしい.これに対して,[1,n−1]と[1,n]の線分木の違いは,a[n]番目の数にすぎず,前のn−1の情報を用いて,このn番目の数を加えればよく,log(n)個を超えないノードを新たに加えることができることが分かった.このように似ています.これはコードの中で自分でどうやって打つかを見たほうがいいです.
hdu2665,poj2104,2761
区間の第kが小さいことを求めます

#include
#include
#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=1e5+5;
struct cy{
    int val,id;
}a[maxn];
struct tre{
    int l,r;
    int sum;
}tree[maxn*20];
int rank[maxn],root[maxn],n,m,cnt;

bool cmp(cy a,cy b)
{
    return a.valvoid add(int &now,int l,int r,int x)
{
    tree[++cnt]=tree[now];
    now=cnt;
    tree[now].sum++;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (x<=mid) add(tree[now].l,l,mid,x);
    else add(tree[now].r,mid+1,r,x);
}
int getans(int L,int R,int sum,int l,int r)
{
    int k=tree[tree[R].l].sum-tree[tree[L].l].sum;
    if (l==r) return l;
    int mid=(l+r)>>1;
    if (sum<=k) return getans(tree[L].l,tree[R].l,sum,l,mid);
    else return getans(tree[L].r,tree[R].r,sum-k,mid+1,r);
}
int main()
{
    freopen("T.in","r",stdin);
//  freopen("T.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,1,n) scanf("%d",&a[i].val),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    fo(i,1,n) rank[a[i].id]=i;
    fo(i,1,n){
        root[i]=root[i-1];
        add(root[i],1,n,rank[i]);
    }
    int l,r,w,ans;
    fo(i,1,m){
        scanf("%d%d%d",&l,&r,&w);
        ans=getans(root[l-1],root[r],w,1,n);
        printf("%d
",a[ans].val);
    }
}