luogu3380 【模板】二逼平衡树（树套树）

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <ctime>

using namespace std;

int n, m, a[50005], opt, uu, vv, ww, ans;

const int oo=2147483647;

namespace treap{

	struct Node{

		int l, r, siz, val, hav, rnd;

	}nd[5000005];

	int tot;

	void upd(int k){

		nd[k].siz = nd[nd[k].l].siz + nd[nd[k].r].siz + nd[k].hav;

	}

	void lRotate(int &k){

		int t=nd[k].r; nd[k].r = nd[t].l; nd[t].l = k;

		nd[t].siz = nd[k].siz; upd(k); k = t;

	}

	void rRotate(int &k){

		int t=nd[k].l; nd[k].l = nd[t].r; nd[t].r = k;

		nd[t].siz = nd[k].siz; upd(k); k = t;

	}

	void insert(int &k, int x){

		if(!k){

			k = ++tot; nd[k].siz = nd[k].hav = 1;

			nd[k].val = x; nd[k].rnd = rand();

			return ;

		}

		nd[k].siz++;

		if(nd[k].val==x)	nd[k].hav++;

		else if(nd[k].val>x){

			insert(nd[k].l, x);

			if(nd[nd[k].l].rnd<nd[k].rnd)	rRotate(k);

		}

		else{

			insert(nd[k].r, x);

			if(nd[nd[k].r].rnd<nd[k].rnd)	lRotate(k);

		}

	}

	void shanchu(int &k, int x){

		if(!k)	return ;

		if(nd[k].val==x){

			if(nd[k].hav>1){

				nd[k].hav--;

				nd[k].siz--;

				return ;

			}

			if(nd[k].l*nd[k].r==0)	k = nd[k].l + nd[k].r;

			else if(nd[nd[k].l].rnd<nd[nd[k].r].rnd)	rRotate(k), shanchu(k, x);

			else	lRotate(k), shanchu(k, x);

		}

		else if(nd[k].val>x)

			nd[k].siz--, shanchu(nd[k].l, x);

		else

			nd[k].siz--, shanchu(nd[k].r, x);

	}

	int queryRank(int k, int x){

		if(!k)	return 0;

		if(nd[k].val>x)	return queryRank(nd[k].l, x);

		else if(nd[k].val<x)	return queryRank(nd[k].r, x)+nd[nd[k].l].siz+nd[k].hav;

		else	return nd[nd[k].l].siz;

	}

	void queryPre(int k, int x){

		if(!k)	return ;

		if(nd[k].val<x)	ans = max(ans, nd[k].val), queryPre(nd[k].r, x);

		else	queryPre(nd[k].l, x);

	}

	void queryNxt(int k, int x){

		if(!k)	return ;

		if(nd[k].val>x)	ans = min(ans, nd[k].val), queryNxt(nd[k].l, x);

		else	queryNxt(nd[k].r, x);

	}

}

namespace sgt{

	int rot[200005];

	void insert(int o, int l, int r, int x, int k){

		treap::insert(rot[o], k);

		if(l==r)	;

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(x<=mid)	insert(lson, l, mid, x, k);

			if(mid<x)	insert(rson, mid+1, r, x, k);

		}

	}

	void shanchu(int o, int l, int r, int x, int k){

		treap::shanchu(rot[o], k);

		if(l==r)	;

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(x<=mid)	shanchu(lson, l, mid, x, k);

			if(mid<x)	shanchu(rson, mid+1, r, x, k);

		}

	}

	int queryRank(int o, int l, int r, int x, int y, int k){

		if(l>=x && r<=y)	return treap::queryRank(rot[o], k);

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			int re=0;

			if(x<=mid)	re += queryRank(lson, l, mid, x, y, k);

			if(mid<y)	re += queryRank(rson, mid+1, r, x, y, k);

			return re;

		}

	}

	void queryPre(int o, int l, int r, int x, int y, int k){

		if(l>=x && r<=y)	treap::queryPre(rot[o], k);

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(x<=mid)	queryPre(lson, l, mid, x, y, k);

			if(mid<y)	queryPre(rson, mid+1, r, x, y, k);

		}

	}

	void queryNxt(int o, int l, int r, int x, int y, int k){

		if(l>=x && r<=y)	treap::queryNxt(rot[o], k);

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(x<=mid)	queryNxt(lson, l, mid, x, y, k);

			if(mid<y)	queryNxt(rson, mid+1, r, x, y, k);

		}

	}

}

int queryNum(int uu, int vv, int ww){

	int l=0, r=1e8, mid, re;

	while(l<=r){

		mid = (l + r) >> 1;

		if(sgt::queryRank(1, 1, n, uu, vv, mid)+1<=ww)	re = mid, l = mid + 1;

		else	r = mid - 1;

	}

	return re;

}

int main(){

	srand(time(NULL));

	cin>>n>>m;

	for(int i=1; i<=n; i++){

		scanf("%d", &a[i]);

		sgt::insert(1, 1, n, i, a[i]);

	}

	while(m--){

		scanf("%d", &opt);

		if(opt==1){

			scanf("%d %d %d", &uu, &vv, &ww);

			printf("%d\n", sgt::queryRank(1, 1, n, uu, vv, ww)+1);

		}

		if(opt==2){

			scanf("%d %d %d", &uu, &vv, &ww);

			printf("%d\n", queryNum(uu, vv, ww));

		}

		if(opt==3){

			scanf("%d %d", &uu, &vv);

			sgt::shanchu(1, 1, n, uu, a[uu]);

			a[uu] = vv;

			sgt::insert(1, 1, n, uu, a[uu]);

		}

		if(opt==4){

			scanf("%d %d %d", &uu, &vv, &ww);

			ans = -oo;

			sgt::queryPre(1, 1, n, uu, vv, ww);

			printf("%d\n", ans);

		}

		if(opt==5){

			scanf("%d %d %d", &uu, &vv, &ww);

			ans = oo;

			sgt::queryNxt(1, 1, n, uu, vv, ww);

			printf("%d\n", ans);

		}

	}

	return 0;

}
巴特西

luogu3380 【模板】二逼平衡树（树套树）

最新文章

热门文章
