FHQ_Treap 트 리 (회전 없 는 Treap 트 리) 템 플 릿 방향

이 나 무 는 회전 조작 이 필요 없 는 Treap 나무 로 FHQ (범 호 강) 사내 가 발명 하여 신 급 데이터 구조 라 고 할 수 있 습 니 다!그 는 짧 고 간결 하 며 배우 기 쉬 우 며, 그 사상의 우아 함 은 수많은 OIer / ACmer 와 프로그래머 들 을 매 료 시 켰 다!
이 모든 것 은 이 ppt 에서 기원 되 었 습 니 다. 범 호 강 은 데이터 구 조 를 말 합 니 다.
이 데이터 구 조 를 이해 하기 전에 treap 나무 와 피리 칼 나 무 를 알 아 보 는 것 이 좋 습 니 다. 이 두 나 무 는 그 자체 가 어느 정도 유사 성 을 가지 고 있 습 니 다. FHQ 입 니 다.Treap 은 사상 연신 의 출발점 을 제공 했다.
FHQ_회전 작업 을 대체 하 는 Treap 의 핵심 은 나무의 분리 (split) 와 합병 (merge) 두 가지 작업 입 니 다. 우 리 는 원래 의 나 무 를 값 / 위치 (아래 표) 에 따라 두 그루 의 나무 로 분해 하고 두 그루 의 나 무 를 균형 있 는 나무 로 합 칠 수 있 습 니 다. 나머지 모든 작업 은 이 두 가지 작업 을 바탕 으로 합 니 다!
값 의 split:

void split(int x ,int k, int &l, int &r)
{
    if(!x) {l=r=0;return;}//      0
    pushdown(x);
    if(val[x]<=k){l=x;split(rs[l],rs[l],r,k); pushup(l);}//x    ,   x    
    else{r=x;split(ls[r],l,ls[r],k);pushup(r);}//x    ,   x    
}

가중치 분할 에 따라 질서 있 는 순 서 를 유지 할 때 (STL 의 set 또는 더미 와 유사) kth 대 등 을 조회 할 수 있 습 니 다.
아래 표 시 된 split 를 누 르 십시오:

void split(int x, int k, int &l, int &r)
{
    if(!x) {l=r=0;return;}
    pushdown(x);
    if(sz[ls[x]]+1<=k){l=x;split(rs[l],rs[l],r,k-sz[ls[x]]-1);pushup(l);}//    k
    else{r=x;split(ls[r],l,ls[r],k);pushup(r);}
}

아래 표 에 따라 일반 서열 을 유지 하 는 데 사용 되 며 노드, 구간 과 조회, RMQ, 구간 수정 등 을 삽입 할 수 있 습 니 다.
병합 (merge):

int merge(int x, int y)//    
{
 	if(!x || !y) return x+y;// x y       0
 	if(pri[x] < pri[y])//  x        
 	{
 		pushdown(x);
 	    rs[x] = merge(rs[x],y);
 	    pushup(x);
 	    return x;
 	} 
    else
 	{
 		pushdown(y);
 	    ls[y] = merge(x, ls[y]);
	    pushup(y);
 	    return y;
	}
}

split 와 merge 의 pushup 과 pushdown 은 구체 적 인 상황 에 따라 스스로 삭제 하고 수정 하면 됩 니 다.
이 게시 물이 템 플 릿 방향 임 을 감안 하여 그 배후 원 리 를 상세 하 게 설명 하지 않 습 니 다.
로 곡 P3369 일반 밸 런 스 트 리

#include 
using namespace std;
typedef long long ll;
typedef unsigned long long usi;
const ll MOD = 998244353;
const int MAXN = 1e5 + 7;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-12;

int ch[MAXN][3], val[MAXN], pri[MAXN], sz[MAXN];

class FHQ_Treap
{
public:
	int size = 0;

	bool empty() {return size == 0;}

	void insert(int a)
	{
		split(root, a, x, y);
		root = merge(merge(x, newnode(a)), y);
	}

	void erase(int a)
	{
		split(root, a, x, z);
		split(x, a-1, x, y);
		y = merge(ch[y][0], ch[y][1]);
		root = merge(merge(x, y), z);
	}

	int numrank(int a)
	{
		split(root, a-1, x, y);
		int res = sz[x] + 1;
		root = merge(x, y);
		return res;
	}

	int kth(int k)
	{
		return val[myrank(root, k)];
	}

	int pre(int a)
	{
		split(root, a-1, x, y);
		int res = val[myrank(x, sz[x])];
		root = merge(x, y);
		return res;
	}

	int next(int a)
	{
		split(root, a, x, y);
		int res = val[myrank(y, 1)];
		root = merge(x, y);
		return res;
	}

private:
	int root = 0, x, y, z;

	void update(int x)
	{
		sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
	}

	int newnode(int v)
	{
		sz[++size] = 1;
		val[size] = v;
		pri[size] = rand();
		return size;
	}

	int merge(int x, int y) 
	{
 	    if(!x || !y) return x + y;
 	    if(pri[x] < pri[y])
 	    {
 	        ch[x][1] = merge(ch[x][1],y);
 	        update(x);
 	        return x;
 	    } 
 	    else
 	    {
 	        ch[y][0] = merge(x, ch[y][0]);
	        update(y);
 	        return y;
	    }
	}

	void split(int now, int k, int &x, int &y)
	{
		if(!now) x = y = 0;
		else
		{
			if(val[now] <= k) x = now, split(ch[now][1], k, ch[now][1], y);
			else y = now, split(ch[now][0], k, x, ch[now][0]);
			update(now);
		}
	}

	int myrank(int now, int a)
	{
		while(true)
		{
			if(a < sz[ch[now][0]]) now = ch[now][0];
			else if(a == sz[ch[now][0]] + 1) return now;
			else a -= sz[ch[now][0]] + 1, now = ch[now][1];
		}
	}
};

FHQ_Treap mytree;

int main()
{
	srand((unsigned)time(NULL));
	int n, opt, a;
	cin >> n;
	while(n--)
	{
		scanf("%d%d", &opt, &a);
		if(opt == 1) mytree.insert(a);
		else if(opt == 2) mytree.erase(a);
		else if(opt == 3) printf("%d
", mytree.numrank(a));
		else if(opt == 4) printf("%d
", mytree.kth(a));
		else if(opt == 5) printf("%d
", mytree.pre(a));
		else if(opt == 6) printf("%d
", mytree.next(a));
	}
    return 0;
}

소 손님 1221 E Forsaken 의 수열
이 문 제 는 피리 칼 나 무 를 만 드 는 방법 을 사용 하여 나 무 를 O (n) 로 최적화 시 켰 다.

#include
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;

struct FHQ_Treap
{
    int size = 0, root = 0;
    struct node
    {
        int ls, rs, rnd, siz;
        ll val, sum, lazy;
        node() {}
        node(int LS, int RS, int RND, int SIZ, ll VAL, ll SUM, ll LAZY):
            ls(LS), rs(RS), rnd(RND), siz(SIZ), val(VAL), sum(SUM), lazy(LAZY) {}
    }tree[MAXN];

    inline void pushUp(int p)
    {
        tree[p].siz = tree[tree[p].ls].siz + tree[tree[p].rs].siz + 1;
        tree[p].sum = tree[tree[p].ls].sum + tree[tree[p].rs].sum + tree[p].val;
    }

    inline void pushDown(int p)
    {
        if(tree[p].lazy)
        {
            tree[tree[p].ls].sum += 1ll * tree[tree[p].ls].siz * tree[p].lazy;
            tree[tree[p].ls].lazy += tree[p].lazy;
            tree[tree[p].ls].val += tree[p].lazy;
            tree[tree[p].rs].sum += 1ll * tree[tree[p].rs].siz * tree[p].lazy;
            tree[tree[p].rs].lazy += tree[p].lazy;
            tree[tree[p].rs].val += tree[p].lazy;
            tree[p].lazy = 0;
        }
    }

    void split(int p, int rk, int &x, int &y)
    {
        if(!p) {x = y = 0; return;}
        pushDown(p);
        if(rk <= tree[tree[p].ls].siz)
        {
            y = p;
            split(tree[p].ls, rk, x, tree[p].ls);
            pushUp(y);
        }
        else
        {
            x = p;
            split(tree[p].rs, rk-tree[tree[p].ls].siz-1, tree[p].rs, y);
            pushUp(x);
        }
    }

    int merge(int x, int y)
    {
        if(!x || !y) return x | y;
        if(tree[x].rnd < tree[y].rnd)
        {
            pushDown(x);
            tree[x].rs = merge(tree[x].rs, y);
            pushUp(x);
            return x;
        }
        else
        {
            pushDown(y);
            tree[y].ls = merge(x, tree[y].ls);
            pushUp(y);
            return y;
        }
    }

    int newnode(ll v)
    {
        int p = ++size;
        tree[p] = node(0, 0, rand(), 1, v, v, 0);
        return p;
    }

    void insert(ll val, int p)
    {
        int x, y;
        split(root, p - 1, x, y);
        root = merge(merge(x, newnode(val)), y);
    }

    void add(int l, int r, ll v)
    {
        int x, y, z;
        split(root, l - 1, x, y);
        split(y, r + 1 - l, y, z);
        tree[y].sum += 1ll * tree[y].siz * v;
        tree[y].lazy += v;
        tree[y].val += v;
        root = merge(merge(x, y), z);
    }

    void query(int l, int r)
    {
        int x, y, z;
        split(root, l - 1, x, y);
        split(y, r + 1 - l, y, z);
        printf("%lld
", tree[y].sum);
        root = merge(merge(x, y), z);
    }

    int st[MAXN], top;
    inline void build(int n)
    //         O(n)  ，st  ，      
    {
        top = 0;
        for(int i = 0; i < n; ++i)
        {
            ll val;
            scanf("%lld", &val);
            int tmp = newnode(val), last = 0;
            while(top && tree[st[top]].rnd > tree[tmp].rnd)
            {
                last = st[top];
                pushUp(last);
                st[top--] = 0;
            }
            if(top) tree[st[top]].rs = tmp;
            tree[tmp].ls = last;
            st[++top] = tmp;
        }
        while(top) pushUp(st[top--]);
        root = st[1];
    }
} mytree;

int main()
{
    int n, m, op, pos, l, r;
    ll v;
    scanf("%d", &n);
    mytree.build(n);
    scanf("%d", &m);
    while(m--)
    {
        scanf("%d", &op);
        if(op == 1) scanf("%d", &pos), mytree.insert(0, pos);
        else if(op == 2) scanf("%d%d%lld", &l, &r, &v), mytree.add(l, r, v);
        else scanf("%d%d", &l, &r), mytree.query(l, r);
    }
    return 0;
}

낙 곡 P3391 문예 평형 수

#include 
#include 
#include 
#define N 100005

int Root;
int lazy[N];
int n,m,cnt;
int val[N],sze[N];
int ch[N][2],prio[N];

void pushup(int o){
    sze[o]=sze[ch[o][0]]+sze[ch[o][1]]+1;
}

void pushdown(int o){
    if(!lazy[o] or !o) return;
    ch[o][0]^=ch[o][1]^=ch[o][0]^=ch[o][1];
    lazy[ch[o][0]]^=1;
    lazy[ch[o][1]]^=1;
    lazy[o]=0;
}

void split(int o,int k,int &x,int &y){
    if(!o) x=y=0;
    else{
        pushdown(o);
        if(k>sze[ch[o][0]]) x=o,split(ch[o][1],k-sze[ch[o][0]]-1,ch[o][1],y);
        else y=o,split(ch[o][0],k,x,ch[o][0]);
        pushup(o);
    }
}

int merge(int x,int y){
    if(!x or !y) return x+y;
    pushdown(x); pushdown(y);
    if(prio[x]<prio[y]){
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);
        return x;
    }
    else{
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);
        return y;
    }
}

int newnode(int v){
    val[++cnt]=v;
    sze[cnt]=1;
    prio[cnt]=rand();
    return cnt;
}

void res(int l,int r){
    int a,b,c,d;
    split(Root,r,a,b);
    split(a,l-1,c,d);
    lazy[d]^=1;
    Root=merge(merge(c,d),b);
}

void dfs(int now){
    if(!now) return;
    pushdown(now);
    dfs(ch[now][0]);
    printf("%d ",val[now]);
    dfs(ch[now][1]);
}

signed main(){
    srand(time(0));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        Root=merge(Root,newnode(i));
    //printf("Root=%d
",Root);
    for(int x,y,i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        res(x,y);
        //printf("i=%d
",i);
        //dfs(Root);
    }
    //printf("Root=%d
",Root);
    dfs(Root);
    return 0;
}