• 莞中 2022暑假训练题02：平衡树

    本文代码全部使用 FHQ-Treap, 不了解 FHQ-treap 的可以参考 我的博客。

    T1 普通平衡树

    板子题，参考上面的博客。

    点击查看代码 
    #include 
using namespace std;

const int N = 1e5 + 10;

struct Node
{
	int l,r;
	int val;// real value
	int key;// for treap
	int size;
}fhq[N];
int root,cnt;

mt19937 rnd(233);

int create(int val)
{
	fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].size = 1;
	return cnt;
}

void pushup(int u)
{
	fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;
}

void split(int u,int val,int &x,int &y)
{
	if(!u) 
	{
		x = y = 0;
		return;
	}
	
	if(fhq[u].val <= val)
	{
		x = u;
		split(fhq[u].r,val,fhq[u].r, y);
	}
	else 
	{
		y = u;
		split(fhq[u].l,val,x,fhq[u].l);
	}
	pushup(u);
}

int merge(int x,int y)
{
	if(!x || !y) return x + y;
	if(fhq[x].key >= fhq[y].key)
	{
		fhq[x].r = merge(fhq[x].r,y);
		pushup(x);
		return x;
	}
	else 
	{
		fhq[y].l = merge(x,fhq[y].l);
		pushup(y);
		return y;
	}
}

int x,y,z;
void insert(int val)
{
	split(root,val,x,y);
	root = merge(merge(x,create(val)), y);
}

void del(int val)
{
	split(root,val,x,z);
	split(x,val-1,x,y);
	y = merge(fhq[y].l,fhq[y].r);
	root = merge(merge(x,y),z);
}

void getrank(int val)
{
	split(root,val-1,x,y);
	printf("%d\n",fhq[x].size);
	root = merge(x,y);
}

void getval(int rank)	
{
	rank++;
	int u = root;
	
	while(u)
	{
		if(fhq[fhq[u].l].size + 1 == rank) break;
		if(fhq[fhq[u].l].size >= rank) u = fhq[u].l;
		else rank -= fhq[fhq[u].l].size + 1, u = fhq[u].r;
	}
	
	printf("%d\n", fhq[u].val);
}

void pre(int val)
{
	split(root,val-1,x,y);
	
	int u = x;
	while(fhq[u].r) u = fhq[u].r;
	
	printf("%d\n",fhq[u].val);
	
	root = merge(x,y);
}

void nxt(int val)
{
	split(root,val,x,y);
	
	int u = y;
	while(fhq[u].l) u = fhq[u].l;

	printf("%d\n",fhq[u].val);
	
	root = merge(x,y);
}

int main()
{
	int n;
	scanf("%d",&n);
	insert(2147483647), insert(-2147483647);
	
	while(n--)
	{
		int opt,val;
		scanf("%d%d",&opt,&val);
		
		if(opt == 1) insert(val);
		if(opt == 2) del(val);
		if(opt == 3) getrank(val);
		if(opt == 4) getval(val);
		if(opt == 5) pre(val);
		if(opt == 6) nxt(val);
	}
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147

    T2 宠物收养所

    ####【题意】
    有一个宠物收容所，宠物和人都有一个值，人来了就会拿走一只和他的值最接近的宠物。

    ####【思路】(按值建立FHQ-treap)
    存一下当前是宠物多还是顾客多，随时在宠物和顾客之间转换。

    每一次加进来一个宠物时，如果是宠物树就直接插入，否则查找当前顾客的期望的前驱和后继（不是严格的），拉出来删除，统计答案，反之如果是顾客树，就反着来做就行了。

    点击查看代码 
    #include 
using namespace std;

typedef long long LL;

const LL N = 80005, Mod = 1000000;

struct Node
{
	int l,r;
	LL val,key;
	LL size;
}fhq[N];
int root,cnt;
int kind; // ¨º¡Â¨¤?¡Á¡ã¦Ì?¨º?¨¨??1¨º?1¡¤ 
int n;
int x,y,z;

void pushup(int u)
{
	fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;
}

void split(int u,LL val,int &x,int &y)
{
	if(!u) 
	{
		x = y = 0;
		return ;
	}
	
	if(fhq[u].val <= val) 
	{
		x = u;
		split(fhq[u].r,val,fhq[u].r,y);
	}
	else 
	{
		y = u;
		split(fhq[u].l,val,x,fhq[u].l);
	}
	
	pushup(u);
}

int merge(int x,int y)
{
	if(!x || !y) return x | y;
	
	if(fhq[x].key >= fhq[y].key)
	{
		fhq[x].r = merge(fhq[x].r,y);
		pushup(x);
		return x;
	}
	else
	{
		fhq[y].l = merge(x,fhq[y].l);
		pushup(y);
		return y;
	}
}

mt19937 rnd(233);
int intree = 0;
int create(LL val)
{
	fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].size = 1;
	return cnt;
}

void insert(LL val)
{
	split(root,val,x,y);
	root = merge(merge(x,create(val)),y);
}

void del(LL val)
{
//	intree --;
	split(root,val,x,z);
	split(x,val-1,x,y);
	y = merge(fhq[y].l,fhq[y].r);
	root = merge(x,merge(y,z));
//	cnt --;
}

LL pre(LL val)
{
	split(root,val-1,x,y);
	
	int u = x;
	while(fhq[u].r) u = fhq[u].r;
	
	LL res = fhq[u].val;
	
	root = merge(x,y);
	
	return res;
}

LL nxt(LL val)
{
	split(root,val,x,y);
	
	int u = y;
	while(fhq[u].l) u = fhq[u].l;

	LL res = fhq[u].val;
	
	root = merge(x,y);
	
	return res;
}

int main()
{
//	freopen("input.txt","r",stdin);
	
	scanf("%d",&n);

	insert(-1e10),insert(1e10);
	
	long long ans = 0;
	while(n --)
	{
		LL opt, val;
		scanf("%lld%lld",&opt,&val);
						
		if(!intree || opt == kind)
		{
			intree ++;
			insert(val);
			kind = opt;
		}
		else
		{			
			intree --;
			LL val1 = pre(val);			
			LL val2 = nxt(val);
						
			if(abs(val-val1) < abs(val-val2)) del(val1),ans = (ans + abs(val-val1)) % Mod;
			else del(val2),ans = (ans + abs(val-val2)) % Mod;
		}
	}	
	
	printf("%lld",ans);
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150

    T3 郁闷的出纳员

    ####【题意】
    有一些询问，每一次询问可以加入一个员工，给所有员工加工资和减工资，查询第k大的工资是多少。
    减工资时可能会使得一些员工的工资小于一个工资下限 m i n n minn minn，那他们就会离开公司。

    ####【思路】(按值建立FHQ-treap)
    维护一个变量 d e l t a delta delta,表示集体加了多少工资和减了多少工资。
    加入员工时要将员工的初始工资减去 d e l t a delta delta，再插入到平衡树中。
    加工资的时候就更新一下 d e l t a delta delta 即可。
    减工资的时候要更新 d e l t a delta delta，并将小于 m i n n − d e l t a minn - delta minn−delta 的员工删掉。

    点击查看代码 
    #include 
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

struct Node
{
	int l,r;
	int val;// real value
	int key;// for treap
	int siz;
}fhq[N];
int root,cnt;

mt19937 rnd(233);

int create(int val)
{
	fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].siz = 1;
	return cnt;
}

void pushup(int u)
{
	fhq[u].siz = fhq[fhq[u].l].siz + fhq[fhq[u].r].siz + 1;
}

void split(int u,int val,int &x,int &y)
{
	if(!u) 
	{
		x = y = 0;
		return;
	}
	
	if(fhq[u].val <= val)
	{
		x = u;
		split(fhq[u].r,val,fhq[u].r, y);
	}
	else 
	{
		y = u;
		split(fhq[u].l,val,x,fhq[u].l);
	}
	pushup(u);
}

int merge(int x,int y) 
{
	if(!x || !y) return x + y;
	if(fhq[x].key >= fhq[y].key)
	{
		fhq[x].r = merge(fhq[x].r,y);
		pushup(x);
		return x;
	}
	else 
	{
		fhq[y].l = merge(x,fhq[y].l);
		pushup(y);
		return y;
	}
}

int x,y,z;
void insert(int val)
{
	split(root,val,x,y);
	root = merge(merge(x,create(val)), y);
}

void del(int val)
{
	split(root,val,x,z);	
	split(x,val-1,x,y);
	y = merge(fhq[y].l,fhq[y].r);
	root = merge(merge(x,y),z);
}

void getrank(int val)
{
	split(root,val-1,x,y);
	printf("%d\n",fhq[x].siz);
	root = merge(x,y);
}

int getval(int rank)	
{
	int u = root;
	
	while(u)
	{
		if(fhq[fhq[u].l].siz + 1 == rank) break;
		if(fhq[fhq[u].l].siz >= rank) u = fhq[u].l;
		else rank -= fhq[fhq[u].l].siz + 1, u = fhq[u].r;
	}
	
	return fhq[u].val;
}

void pre(int val)
{
	split(root,val-1,x,y);
	
	int u = x;
	while(fhq[u].r) u = fhq[u].r;
	
	printf("%d\n",fhq[u].val);
	
	root = merge(x,y);
}

void nxt(int val)
{
	split(root,val,x,y);
	
	int u = y;
	while(fhq[u].l) u = fhq[u].l;

	printf("%d\n",fhq[u].val);
	
	root = merge(x,y);
}

int main()
{
	int n, minn;
	scanf("%d%d",&n,&minn);
	
	int x,delta=0,leave=0;
	while(n --)
	{
		char opt[2];
		scanf("%s%d",opt,&x);
		
		if(opt[0] == 'I' && x >= minn) insert(x - delta);
		else if(opt[0] == 'A') delta += x;
		else if(opt[0] == 'S')
		{
			delta -= x;
			split(root,minn - delta - 1,x,y);
			leave += fhq[x].siz;
			root = y;
		}
		else if(opt[0] == 'F')
		{
			if(fhq[root].siz < x) puts("-1");
			else printf("%d\n",getval(fhq[root].siz-x+1)+delta);
		}
	}
	
	printf("%d\n",leave);

	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156

    T4 营业额统计

    【题意】

    给出一个长为 n n n 的序列 a a a， 定义 f i = m i n { ∣ a i − a j ∣ }    ( 1 ≤ j < i ≤ n ) f_i = min\{ |a_i - a_j| \}\; (1 \le j < i \le n) fi​=min{∣ai​−aj​∣}(1≤j<i≤n)。
    求 ∑ f i \sum f_i ∑fi​。

    【思路】(按值建立FHQ-treap)

    依次插入 a i a_i ai​，插入后查找 a i a_i ai​ 的前驱和后继，取它们减去 a i a_i ai​ 的绝对值的较小值。

    点击查看代码 
    #include 
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

struct Node
{
	int l,r;
	int val;// real value
	int key;// for treap
	int size;
}fhq[N];
int root,cnt;

mt19937 rnd(233);

int create(int val)
{
	fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].size = 1;
	return cnt;
}

void pushup(int u)
{
	fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;
}

void split(int u,int val,int &x,int &y)
{
	if(!u) 
	{
		x = y = 0;
		return;
	}
	
	if(fhq[u].val <= val)
	{
		x = u;
		split(fhq[u].r,val,fhq[u].r, y);
	}
	else 
	{
		y = u;
		split(fhq[u].l,val,x,fhq[u].l);
	}
	pushup(u);
}

int merge(int x,int y) // ±??¤x?Dµ?è?òa?a??µ?val??±èy?Dµ?è?òa?a??D? 
{
	if(!x || !y) return x + y;
	if(fhq[x].key >= fhq[y].key)
	{
		fhq[x].r = merge(fhq[x].r,y);
		pushup(x);
		return x;
	}
	else 
	{
		fhq[y].l = merge(x,fhq[y].l);
		pushup(y);
		return y;
	}
}

int x,y,z;
void insert(int val)
{
	split(root,val,x,y);
	root = merge(merge(x,create(val)), y);
}

void del(int val)
{
	split(root,val,x,z);	
	split(x,val-1,x,y);
	y = merge(fhq[y].l,fhq[y].r);
	root = merge(merge(x,y),z);
}

void getrank(int val)
{
	split(root,val-1,x,y);
	printf("%d\n",fhq[x].size);
	root = merge(x,y);
}

void getval(int rank)	
{
	rank++;
	int u = root;
	
	while(u)
	{
		if(fhq[fhq[u].l].size + 1 == rank) break;
		if(fhq[fhq[u].l].size >= rank) u = fhq[u].l;
		else rank -= fhq[fhq[u].l].size + 1, u = fhq[u].r;
	}
	
	printf("%d\n", fhq[u].val);
}

int pre(int val)
{
	split(root,val-1,x,y);
	
	int u = x;
	while(fhq[u].r) u = fhq[u].r;
	
	int ans = fhq[u].val;
	
	root = merge(x,y);
	return ans;
}

int nxt(int val)
{
	split(root,val,x,y);
	
	int u = y;
	while(fhq[u].l) u = fhq[u].l;

	int ans = fhq[u].val;
	
	root = merge(x,y);
	
	return ans;
}

unordered_map<int,int> h;

int main()
{
	int n;
	scanf("%d",&n);
	insert(INF), insert(-INF);
	
	int ans = 0, x;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		h[x] ++;
		insert(x);
		if(i == 1) ans += x;
		else if(h[x] <= 1) ans += min(abs(x - pre(x)), abs(x - nxt(x)));
	}
	
	cout<<ans;
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151

    T5 Double Queue

    【题意】

    有若干次操作，每次操作可以将一个人 k k k，按优先级 p p p 插入一条等待队列中，可以询问队列中的最大（或最小）优先级的人，并将其从队列中删除。
    保证所有的 k k k 和所有的 p p p 互不相同。

    【思路】(按值建立FHQ-treap)

    建立一个 k k k 和 p p p 的映射关系。
    先在平衡树中插入哨兵 -INF \text{-INF} -INF 和 INF \text{INF} INF。
    加入一个人的时候将其的 p p p 插入平衡树中。
    询问最大的时候就输出 INF \text{INF} INF 的前驱对应的 k k k。
    询问最小的时候就输出 -INF \text{-INF} -INF 的后继对应的 k k k。

    点击查看代码 
    #include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

struct Node
{
	int l,r;
	int val;// real value
	int key;// for treap
	int size;
}fhq[N];
int root,cnt;

//mt19937 rand(233);

int create(int val)
{
	fhq[++cnt].val = val,fhq[cnt].key = rand(),fhq[cnt].size = 1;
	return cnt;
}

void pushup(int u)
{
	fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;
}

void split(int u,int val,int &x,int &y)
{
	if(!u) 
	{
		x = y = 0;
		return;
	}
	
	if(fhq[u].val <= val)
	{
		x = u;
		split(fhq[u].r,val,fhq[u].r, y);
	}
	else 
	{
		y = u;
		split(fhq[u].l,val,x,fhq[u].l);
	}
	pushup(u);
}

int merge(int x,int y) 
{
	if(!x || !y) return x + y;
	if(fhq[x].key >= fhq[y].key)
	{
		fhq[x].r = merge(fhq[x].r,y);
		pushup(x);
		return x;
	}
	else 
	{
		fhq[y].l = merge(x,fhq[y].l);
		pushup(y);
		return y;
	}
}

int x,y,z;
void insert(int val)
{
	split(root,val,x,y);
	root = merge(merge(x,create(val)), y);
}

void del(int val)
{
	split(root,val,x,z);	
	split(x,val-1,x,y);
	y = merge(fhq[y].l,fhq[y].r);
	root = merge(merge(x,y),z);
}

void getrank(int val)
{
	split(root,val-1,x,y);
	printf("%d\n",fhq[x].size);
	root = merge(x,y);
}

void getval(int rank)	
{
	rank++;
	int u = root;
	
	while(u)
	{
		if(fhq[fhq[u].l].size + 1 == rank) break;
		if(fhq[fhq[u].l].size >= rank) u = fhq[u].l;
		else rank -= fhq[fhq[u].l].size + 1, u = fhq[u].r;
	}
	
	printf("%d\n", fhq[u].val);
}

map<int,int> h;
int pre(int val)
{
	split(root,val-1,x,y);
	
	int u = x;
	while(fhq[u].r) u = fhq[u].r;
	
	int ans = fhq[u].val;	
	root = merge(x,y);
	return ans;
}

int nxt(int val)
{
	split(root,val,x,y);
	
	int u = y;
	while(fhq[u].l) u = fhq[u].l;

	int ans = fhq[u].val;	
	root = merge(x,y);
	return ans;
}

int main()
{
	srand(time(0));
	int opt;
	insert(-INF),insert(INF);
	while(~scanf("%d",&opt))
	{
		if(opt == 0) break;
		if(opt == 1)
		{
			int k, p;
			scanf("%d%d",&k,&p);
			h[p] = k;
			insert(p);
		}
		if(opt == 2)
		{
			int p = pre(INF);
			cout<<h[p]<<endl;
			del(p);
		}
		if(opt == 3)
		{
			int p = nxt(-INF);
			cout<<h[p]<<endl;
			del(p);
		}
	}
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162

    T6 Buy Tickets

    ####【题意】
    有 n ( 1 ≤ n ≤ 2 × 1 0 5 ) n (1 \le n \le 2\times 10^5) n(1≤n≤2×105) 个询问，每次询问将一个值 v a l val val 插到 p o s pos pos 的后面。

    【思路】(按下标建立FHQ-Treap)

    明显需要一个 O ( n log ⁡ n ) O(n \log n) O(nlogn) 的算法。

    考虑使用按下标为关键字的 FHQ-Treap。

    每次插入都将按 pos 来 Split。

    再将整个树合并起来即可。

    点击查看代码 
    #include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 300010;

struct Node
{
	int l,r;
	int val;// real value
	int key;// for treap
	int siz;
	int laz;
}fhq[N];
int root,cnt;

int create(int val)
{
	fhq[++cnt].val = val,fhq[cnt].key = rand(),fhq[cnt].siz = 1;
	return cnt;
}

void pushup(int u)
{
	fhq[u].siz = fhq[fhq[u].l].siz + fhq[fhq[u].r].siz + 1;
}

void pushdown(int u)
{
	swap(fhq[u].l,fhq[u].r);
	fhq[fhq[u].l].laz ^= 1;
	fhq[fhq[u].r].laz ^= 1;
	fhq[u].laz = 0;
}

void split(int u,int val,int &x,int &y)
{
	if(!u) 
	{
		x = y = 0;
		return;
	}
	
	if(fhq[u].laz) pushdown(u);
	
	if(fhq[fhq[u].l].siz+1 <= val)
	{
		x = u;
		split(fhq[u].r,val-(fhq[fhq[u].l].siz+1),fhq[u].r, y);
	}
	else 
	{
		y = u;
		split(fhq[u].l,val,x,fhq[u].l);
	}
	pushup(u);
}

int merge(int x,int y)
{
	if(!x || !y) return x + y;
	if(fhq[x].key >= fhq[y].key)
	{
		if(fhq[x].laz) pushdown(x);
		fhq[x].r = merge(fhq[x].r,y);
		pushup(x);
		return x;
	}
	else 
	{
		if(fhq[y].laz) pushdown(y);
		fhq[y].l = merge(x,fhq[y].l);
		pushup(y);
		return y;
	}
}

int x,y,z;
int n, m;	
void print(int u)
{
	if(fhq[u].laz) pushdown(u);
	if(fhq[u].l) print(fhq[u].l);
	printf("%d ",fhq[u].val);
	if(fhq[u].r) print(fhq[u].r);
}

int main()
{
	while(~scanf("%d",&n))
	{
		srand(time(0));
		root = cnt = 0;
		memset(fhq,0,sizeof fhq);
		
		for(int i=1;i<=n;i++) 
		{
			int pos,val;
			scanf("%d%d",&pos,&val);
			if(pos == 0) root = merge(create(val),root);
			else 
			{
				split(root,pos,x,y);
				root = merge(merge(x,create(val)),y);
			}
		}
		
		print(root);
		cout<<endl;
	}
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116

    T7 I Hate It

    ####【题意】
    维护区间最大值，单点修改。

    ####【思路】
    板子线段树秒杀。

    平衡树做法略显复杂。

    询问最大值就查询 INF 的前驱即可。
    单点修改就要删掉原来的值，再插入一个新的值。

    赛时极限7分钟A掉这道题(doge

    点击查看代码 
    #include 
using namespace std;

typedef long long LL;

const int N = 2 * 1e5 + 10;

struct Node
{
	int l,r;
	LL val;
}tr[N * 4];

LL w[N];

void pushup(int u)
{
	tr[u].val = max(tr[u<<1].val, tr[u<<1|1].val);
}

void build(int u,int l,int r)
{
	if(l == r) tr[u] = Node{l,r,w[r]};
	else
	{
		tr[u].l = l,tr[u].r = r;
		int mid = l + r >> 1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

void modify(int u,int x,LL val)
{
	if(tr[u].l == x && tr[u].r == x) tr[u].val = max(tr[u].val,val);
	else
	{
		int mid = tr[u].l + tr[u].r >> 1;
		if(x <= mid) modify(u<<1,x,val);
		if(x > mid) modify(u<<1|1,x,val);
		pushup(u);
	}
}

LL query(int u,int l,int r)
{
	if(l <= tr[u].l && tr[u].r <= r) return tr[u].val;
	else
	{
		int mid = tr[u].l + tr[u].r >> 1;
		
		LL ans = -1e9;
		if(l <= mid) ans = max(ans,query(u<<1,l,r));
		if(r > mid) ans = max(ans,query(u<<1|1,l,r));

		return ans;
	}
}

int main()
{
	int n,m;
	
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;i++) scanf("%lld",&w[i]);

		build(1,1,n);
	
		while(m --)
		{
			char opt[3];
			LL x,y;
			scanf("%s%lld%lld",opt,&x,&y);
			
			if(opt[0] == 'U') modify(1,x,y);
			else cout << query(1,x,y) << endl;
		}
	}

	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82

    T8 Robotic Sort

    【题意】

    给出一个序列，对于每一个 i i i，要求翻转一段连续区间，使得第 i i i 小的数翻转到i的位置。

    【思路】(按下标建立FHQ-Treap)

    区间翻转可以使用 Splay 或者 FHQ-Treap。

    本人擅长 FHQ-Treap，下面讲一下 FHQ-Treap 如何实现区间翻转。

    假设现在要翻转区间 [ a , b ] [a,b] [a,b]。
    首先我们要用两次 Split 将区间 [ a , b ] [a,b] [a,b] 抠出来，一次按 b Split，一次按 a-1 Split。
    之后我们要借助懒标记，标记这个区间需要翻转。
    需要获取序列或输出序列的时候的时候需要中序遍历一遍树。
    注意，所有需要懒标记的题目在递归前都需要 pushdown。(我在这里卡了好久)

    对于这一题，首先要离散化一下数据，之后按下标建立 FHQ-Treap。

    这题比较蛋疼的是，我们需要使用类似笛卡尔树的方式来建树，不然会被卡到 T 飞。

    每一次都找到整棵树内的最小值，这个操作可以直接找 -INF 的后继，由于我们是使用类似笛卡尔树的建树方式，所以根结点就是最小值。

    翻转过后，删掉最小值即可。

    点击查看代码 
    #include 
using namespace std;

typedef long long LL;
const LL N = 100010;

struct Node
{
	LL l,r;
	LL val;// real value
	LL key;// for treap
	LL siz;
	LL laz;
}fhq[N];
LL root,cnt;

mt19937 rnd(114514);

LL create(LL val)
{
	fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].siz = 1;
	return cnt;
}

void pushup(LL u)
{
	fhq[u].siz = fhq[fhq[u].l].siz + fhq[fhq[u].r].siz + 1;
}

void pushdown(LL u)
{
	swap(fhq[u].l,fhq[u].r);
	if(fhq[u].l) fhq[fhq[u].l].laz ^= 1;
	if(fhq[u].r) fhq[fhq[u].r].laz ^= 1;
	fhq[u].laz = 0;
}

LL merge(LL x,LL y)
{
	if(!x || !y) return x + y;
	if(fhq[x].key < fhq[y].key)
	{
		if(fhq[x].laz) pushdown(x);
		fhq[x].r = merge(fhq[x].r,y);
		pushup(x);
		return x;
	}
	else 
	{
		if(fhq[y].laz) pushdown(y);
		fhq[y].l = merge(x,fhq[y].l);
		pushup(y);
		return y;
	}
}

struct Point
{
	LL num,id;
} a[N];
LL b[N];

bool cmp1(const Point& p,const Point& q) {return p.num < q.num;}
bool cmp2(const Point& p,const Point& q) {return p.id < q.id;}

LL x,y,z;
LL n, m;

int main()
{
	while(~scanf("%lld",&n))
	{
		if(n == 0) break;
//		scanf("%lld",&n);
		root = cnt = 0;
		memset(fhq,0,sizeof fhq);
		
		stack<LL> stk;
		for(LL i=1;i<=n;i++)
		{
			scanf("%lld",&fhq[i].key);
			fhq[i].key = fhq[i].key * n + i;
			fhq[i].val = i, fhq[i].siz = 1;
			
			while(!stk.empty() && fhq[i].key < fhq[stk.top()].key) fhq[i].l = stk.top(), stk.pop(), pushup(fhq[i].l);
			if(!stk.empty()) fhq[stk.top()].r = i; 
			stk.push(i);
		}
		
		while(!stk.empty()) root = stk.top(), pushup(stk.top()), stk.pop();
				
		for(LL i=1;i<=n;i++) 
		{
			if(fhq[root].laz) pushdown(root);
			printf("%lld",fhq[fhq[root].l].siz+i);
			if(i < n) putchar(' ');
			fhq[fhq[root].l].laz ^= 1;
			
			LL l = fhq[root].l, r = fhq[root].r;
			fhq[root].l = fhq[root].r = 0;
			root = merge(l, r);
		}
		
		puts("");
	}
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108

    T9 Play with Chain

    【题意】

    有两种操作，一种是将区间 [ a , b ] [a,b] [a,b] 取出，插到 c c c 后面。
    另一种是将区间 [ a , b ] [a,b] [a,b] 翻转。

    【思路】(按下标建立FHQ-Treap)

    对于第一种操作，我们需要将按 b 和 a-1 Split两边，将区间 [ a , b ] [a,b] [a,b] 抠出来，将原本的 [ a , b ] [a,b] [a,b] 删掉，然后按 c c c Split，最后将 [ a , b ] [a,b] [a,b] 在 c c c 之后合并起来。

    对于第二种操作，可以参考本文T8 中的解释。

    点击查看代码 
    #include 
using namespace std;

const int N = 300010;

struct Node
{
	int l,r;
	int val;// real value
	int key;// for treap
	int siz;
	int laz;
}fhq[N];
int root,cnt;

mt19937 rnd(114514);

int create(int val)
{
	fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].siz = 1;
	return cnt;
}

void pushup(int u)
{
	fhq[u].siz = fhq[fhq[u].l].siz + fhq[fhq[u].r].siz + 1;
}

void pushdown(int u)
{
	swap(fhq[u].l,fhq[u].r);
	fhq[fhq[u].l].laz ^= 1;
	fhq[fhq[u].r].laz ^= 1;
	fhq[u].laz = 0;
}

void split(int u,int val,int &x,int &y)
{
	if(!u) 
	{
		x = y = 0;
		return;
	}
	
	if(fhq[u].laz) pushdown(u);
	
	if(fhq[fhq[u].l].siz+1 <= val)
	{
		x = u;
		split(fhq[u].r,val-(fhq[fhq[u].l].siz+1),fhq[u].r, y);
	}
	else 
	{
		y = u;
		split(fhq[u].l,val,x,fhq[u].l);
	}
	pushup(u);
}

int merge(int x,int y)
{
	if(!x || !y) return x + y;
	if(fhq[x].key >= fhq[y].key)
	{
		if(fhq[x].laz) pushdown(x);
		fhq[x].r = merge(fhq[x].r,y);
		pushup(x);
		return x;
	}
	else 
	{
		if(fhq[y].laz) pushdown(y);
		fhq[y].l = merge(x,fhq[y].l);
		pushup(y);
		return y;
	}
}

int x,y,z;
int n, m;	
int tot = 0;
void print(int u)
{
	if(fhq[u].laz) pushdown(u);
	if(fhq[u].l) print(fhq[u].l);
	printf("%d",fhq[u].val);
	tot++;
	if(tot <= n-1) putchar(' ');
	if(fhq[u].r) print(fhq[u].r);
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		root = cnt = 0;
		memset(fhq,0,sizeof fhq);
		
		if(n == -1 && m == -1) break;
		for(int i=1;i<=n;i++) 
		{
			create(i);
			root = merge(root,i);
		}
		
		while(m --)
		{
			char opt[10];
			scanf("%s",opt);
			
			if(opt[0] == 'C')
			{
				int a,b,c;
				scanf("%d%d%d",&a,&b,&c);
				split(root,b,x,y);
				split(x,a-1,x,z);
				root = merge(x,y);
				split(root,c,x,y);
				root = merge(merge(x,z),y);
			}
			if(opt[0] == 'F')
			{
				int l, r;
				scanf("%d%d",&l,&r);
				
				split(root,r,x,y);
				split(x,l-1,x,z);
				fhq[z].laz^=1;
				root = merge(merge(x,z),y);
			} 
		}		
		tot = 0;
		print(root);
		cout<<endl;
	}
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
  • 相关阅读:
    提升ChatGPT答案质量和准确性的方法Prompt专家
    云原生周刊：Istio 1.19 发布 ｜ 2023.9.11
    Docker连接Mysql
    《0基础》学习Python——第十一讲__时间函数
    用Unity同时开发【微信小游戏】【安卓】【IOS】游戏#5.5.2 组件拓展
    【C++面向对象侯捷】12.虚函数与多态 | 13.委托相关设计【设计模式 经典做法，类与类之间关联起来，太妙了，不断的想，不断的写代码】
    [附源码]Python计算机毕业设计儿童闲置物品交易网站
    BI行业分析思维框架 - 环保行业分析（二）
    操作系统 进程同步及线程满分作业
    leetcode-剑指 Offer II 001. 整数除法
  • 原文地址：https://blog.csdn.net/zhaoweiming2019/article/details/126285371