作业介绍

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5,Inf=1e9+1;
struct node{
	int ch[2],fa,val,cnt;
	int size;
}tree[N];
int n,root,tot;
int Get(int x){
	//返回x是左儿子还是右儿子
	return x == tree[tree[x].fa].ch[1];
}
void pushup(int x){
	//更新size
	if(!x)return;
	tree[x].size = tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+tree[x].cnt;
}
void rotate(int x){
	//将x旋转到父亲之上
	int y=tree[x].fa,z=tree[y].fa,chk=Get(x);
	tree[y].ch[chk] = tree[x].ch[chk^1];
	if(tree[x].ch[chk^1]) tree[tree[x].ch[chk^1]].fa = y;
	
	tree[x].ch[chk^1] = y;
	tree[y].fa = x;
	
	if(z)tree[z].ch[y==tree[z].ch[1]] = x;
	tree[x].fa = z;
	
	pushup(y);
	pushup(x);
}

void splay(int x,int k){
	//将x旋转到k的儿子
	while(tree[x].fa!=k){
		int y = tree[x].fa,z=tree[y].fa;
		if(z!=k){
			if(Get(x)==Get(y))rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if(k==0)root = x;
}

void insert(int x){
	//插入x
	int cur = root;
	int fa = 0;
	while(cur){
		if(tree[cur].val==x){
			tree[cur].cnt++;
			pushup(cur);
			pushup(fa);
			splay(cur,0);
			return;
		}
		fa = cur;
		cur = tree[cur].ch[x>tree[cur].val];
	}
	cur = ++tot;
	tree[cur].val = x;
	tree[cur].fa = fa;
	tree[cur].cnt = 1;
	tree[fa].ch[x>tree[fa].val] = cur;
	pushup(cur);
	pushup(fa);
	splay(cur,0);
}
int rnk(int x){
	//返回x的排名
	int res = 0,cur=root;
	while(cur){
		if(x<tree[cur].val)cur = tree[cur].ch[0];
		else{
			res+=tree[tree[cur].ch[0]].size;
			if(x==tree[cur].val){
				splay(cur,0);
				return res+1;
			}
			else{
				res+=tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return res+1;
}
int kth(int x){
	//返回排名为x的数
	int cur = root;
	while(cur){
		if(x<=tree[tree[cur].ch[0]].size)cur = tree[cur].ch[0];
		else{
			x-=tree[tree[cur].ch[0]].size;
			if(x<=tree[cur].cnt){
				splay(cur,0);
				return cur;
			}
			else{
				x-=tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return -1;
}

int pre(int x){
	//返回x的前驱
	int res = -Inf;
	int cur = root;
	while(cur){
		if(tree[cur].val<x){
			res = max(res,tree[cur].val);
			cur = tree[cur].ch[1];
		}
		else cur = tree[cur].ch[0];
	}
	return res;
}
int nxt(int x){
	//返回x的后继
	int res = Inf;
	int cur = root;
	while(cur){
		if(tree[cur].val>x){
			res = min(res,tree[cur].val);
			cur = tree[cur].ch[0];
		}
		else cur = tree[cur].ch[1];
	}
	return res;
}
void find(int x){
	//将x旋转至根节点
	int cur = root;
	while(cur){
		if(tree[cur].val==x){
			splay(cur,0);
			return;
		}
		cur = tree[cur].ch[x>tree[cur].val];
	}
}
void del(int x){
	find(x);
	int L = tree[root].ch[0],R=tree[root].ch[1];
	while(tree[L].ch[1])L=tree[L].ch[1];
	while(tree[R].ch[0])R=tree[R].ch[0];
	splay(L,0);
	splay(R,L);
	if(tree[tree[R].ch[0]].cnt>1){
		tree[tree[R].ch[0]].cnt--;
		pushup(tree[R].ch[0]);
		pushup(R);
		pushup(L);
	}
	else{
		tree[R].ch[0] = 0;
		pushup(R);
		pushup(L);
	}
}
int main(){
	insert(-Inf);
	insert(Inf);
	cin>>n;
	for(int i=1;i<=n;i++){
		int op,x;
		cin>>op>>x;
		if(op==1){
			insert(x);
		}
		if(op==2){
			del(x);
		}
		if(op==3){
			cout<<rnk(x)-1<<endl;
		}
		if(op==4){
			cout<<tree[kth(x+1)].val<<endl;
		}
		if(op==5){
			cout<<pre(x)<<endl;
		}
		if(op==6){
			cout<<nxt(x)<<endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5,Inf=1e9+1;
struct node{
	int ch[2],fa,val,cnt;
	int size,rev;
}tree[N];
int n,root,tot;
void pushdown(int x);
int Get(int x){
	//返回x是左儿子还是右儿子
	return x == tree[tree[x].fa].ch[1];
}
void pushup(int x){
	//更新size
	if(!x)return;
	tree[x].size = tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+tree[x].cnt;
}
void rotate(int x){
	//将x旋转到父亲之上
	int y=tree[x].fa,z=tree[y].fa,chk=Get(x);
	tree[y].ch[chk] = tree[x].ch[chk^1];
	if(tree[x].ch[chk^1]) tree[tree[x].ch[chk^1]].fa = y;
	
	tree[x].ch[chk^1] = y;
	tree[y].fa = x;
	
	if(z)tree[z].ch[y==tree[z].ch[1]] = x;
	tree[x].fa = z;
	
	pushup(y);
	pushup(x);
}

void splay(int x,int k){
	//将x旋转到k的儿子
	while(tree[x].fa!=k){
		int y = tree[x].fa,z=tree[y].fa;
		if(z!=k){
			if(Get(x)==Get(y))rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if(k==0)root = x;
}

void insert(int x){
	//插入x
	int cur = root;
	int fa = 0;
	while(cur){
		if(tree[cur].val==x){
			tree[cur].cnt++;
			pushup(cur);
			pushup(fa);
			splay(cur,0);
			return;
		}
		fa = cur;
		cur = tree[cur].ch[x>tree[cur].val];
	}
	cur = ++tot;
	tree[cur].val = x;
	tree[cur].fa = fa;
	tree[cur].cnt = 1;
	tree[fa].ch[x>tree[fa].val] = cur;
	pushup(cur);
	pushup(fa);
	splay(cur,0);
}
int rnk(int x){
	//返回x的排名
	int res = 0,cur=root;
	while(cur){
		if(x<tree[cur].val)cur = tree[cur].ch[0];
		else{
			res+=tree[tree[cur].ch[0]].size;
			if(x==tree[cur].val){
				splay(cur,0);
				return res+1;
			}
			else{
				res+=tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return res+1;
}
int kth(int x){
	//返回排名为x的数
	int cur = root;
	while(cur){
		pushdown(cur);
		if(x<=tree[tree[cur].ch[0]].size)cur = tree[cur].ch[0];
		else{
			x-=tree[tree[cur].ch[0]].size;
			if(x<=tree[cur].cnt){
				splay(cur,0);
				return cur;
			}
			else{
				x-=tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return -1;
}

int pre(int x){
	//返回x的前驱
	int res = -Inf;
	int cur = root;
	while(cur){
		if(tree[cur].val<x){
			res = max(res,tree[cur].val);
			cur = tree[cur].ch[1];
		}
		else cur = tree[cur].ch[0];
	}
	return res;
}
int nxt(int x){
	//返回x的后继
	int res = Inf;
	int cur = root;
	while(cur){
		if(tree[cur].val>x){
			res = min(res,tree[cur].val);
			cur = tree[cur].ch[0];
		}
		else cur = tree[cur].ch[1];
	}
	return res;
}
void find(int x){
	//将x旋转至根节点
	int cur = root;
	while(cur){
		if(tree[cur].val==x){
			splay(cur,0);
			return;
		}
		cur = tree[cur].ch[x>tree[cur].val];
	}
}
void del(int x){
	find(x);
	int L = tree[root].ch[0],R=tree[root].ch[1];
	while(tree[L].ch[1])L=tree[L].ch[1];
	while(tree[R].ch[0])R=tree[R].ch[0];
	splay(L,0);
	splay(R,L);
	if(tree[tree[R].ch[0]].cnt>1){
		tree[tree[R].ch[0]].cnt--;
		pushup(tree[R].ch[0]);
		pushup(R);
		pushup(L);
	}
	else{
		tree[R].ch[0] = 0;
		pushup(R);
		pushup(L);
	}
}
void pushrev(int x,int y){
	int L = kth(x);
	int R = kth(y+2);
	splay(L,0);
	splay(R,L);
	swap(tree[tree[R].ch[0]].ch[0],tree[tree[R].ch[0]].ch[1]);
	tree[tree[R].ch[0]].rev^=1;
}
void pushdown(int x){
	if(tree[x].rev){
		tree[tree[x].ch[0]].rev^=1;
		tree[tree[x].ch[1]].rev^=1;
		swap(tree[tree[x].ch[0]].ch[0],tree[tree[x].ch[0]].ch[1]);
		swap(tree[tree[x].ch[1]].ch[0],tree[tree[x].ch[1]].ch[1]);
		tree[x].rev = 0;
	}
}
void print(int x){
	pushdown(x);
	if(tree[x].ch[0])print(tree[x].ch[0]);
	if(tree[x].val>0 && tree[x].val<=n)cout<<tree[x].val<<" ";
	if(tree[x].ch[1])print(tree[x].ch[1]);
}
int main(){
	int m;
	cin>>n>>m;
	for(int i=0;i<=n+1;i++){
		insert(i);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		pushrev(x,y);
	}
	print(root);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+5;
struct node{
	int ch[2],fa,val,size;
	int rev,tag;
	bool flag;//rev区间被翻转，flag代表区间被修改，tag区间被修改的值
	int lm,rm,sum,max;
}tree[N];
int n,m,root,tot,a[500005];
int Get(int x){
	return x == tree[tree[x].fa].ch[1];
}
void pushup(int x){
	if(!x)return;
	tree[x].size = tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1;
	tree[x].sum = tree[tree[x].ch[0]].sum+tree[x].val+tree[tree[x].ch[1]].sum;
	tree[x].lm = max(tree[tree[x].ch[0]].sum+tree[x].val+tree[tree[x].ch[1]].lm,tree[tree[x].ch[0]].lm);
	tree[x].lm = max(tree[x].lm,tree[tree[x].ch[0]].sum+tree[x].val);
	tree[x].rm = max(tree[tree[x].ch[1]].sum+tree[x].val+tree[tree[x].ch[0]].rm,tree[tree[x].ch[1]].rm);
	tree[x].rm = max(tree[x].rm,tree[tree[x].ch[1]].sum+tree[x].val);
	tree[x].max = max(tree[tree[x].ch[0]].max,tree[tree[x].ch[1]].max);
	tree[x].max = max(tree[x].max,tree[tree[x].ch[0]].rm+tree[x].val);
	tree[x].max = max(tree[x].max,tree[tree[x].ch[0]].rm+tree[x].val+tree[tree[x].ch[1]].lm);
	tree[x].max = max(tree[x].max,tree[tree[x].ch[1]].lm+tree[x].val);
}
void pushdown(int x){
	if(tree[x].flag){
		tree[tree[x].ch[0]].flag = 1;
		tree[tree[x].ch[1]].flag = 1;
		tree[tree[x].ch[0]].tag = tree[x].tag;
		tree[tree[x].ch[1]].tag = tree[x].tag;
		tree[tree[x].ch[0]].val = tree[x].tag;
		tree[tree[x].ch[1]].val = tree[x].tag;
		tree[tree[x].ch[0]].sum = tree[x].tag*tree[tree[x].ch[0]].size;
		tree[tree[x].ch[1]].sum = tree[x].tag*tree[tree[x].ch[1]].size;
		if(tree[x].tag>0){
			tree[tree[x].ch[0]].lm = tree[tree[x].ch[0]].rm = tree[tree[x].ch[0]].sum = tree[tree[x].ch[0]].max = tree[x].tag*tree[tree[x].ch[0]].size;
			tree[tree[x].ch[1]].lm = tree[tree[x].ch[1]].rm = tree[tree[x].ch[1]].sum = tree[tree[x].ch[1]].max = tree[x].tag*tree[tree[x].ch[1]].size;
		}
		else{
			tree[tree[x].ch[0]].lm = tree[tree[x].ch[0]].rm = tree[tree[x].ch[0]].max = tree[x].tag;
			tree[tree[x].ch[1]].lm = tree[tree[x].ch[1]].rm = tree[tree[x].ch[1]].max = tree[x].tag;
		}
		tree[x].flag = 0;
		tree[x].tag = 0;
		tree[x].rev = 0;
	}
	else if(tree[x].rev){
		tree[tree[x].ch[0]].rev^=1;
		swap(tree[tree[x].ch[0]].ch[0],tree[tree[x].ch[0]].ch[1]);
		swap(tree[tree[x].ch[0]].lm,tree[tree[x].ch[0]].rm);
		tree[tree[x].ch[1]].rev^=1;
		swap(tree[tree[x].ch[1]].ch[0],tree[tree[x].ch[1]].ch[1]);
		swap(tree[tree[x].ch[1]].lm,tree[tree[x].ch[1]].rm);
		tree[x].rev = 0;
	}
}

void rotate(int x){
	int y = tree[x].fa,z=tree[y].fa;
	int chk = Get(x);
	tree[y].ch[chk] = tree[x].ch[chk^1];
	if(tree[x].ch[chk^1])tree[tree[x].ch[chk^1]].fa = y;
	tree[x].ch[chk^1] = y;
	tree[y].fa = x;
	if(z)tree[z].ch[y==tree[z].ch[1]] = x;
	tree[x].fa = z;
	pushup(y);
	pushup(x);
}
void splay(int x,int k){ 
	while(tree[x].fa!=k){
		int y = tree[x].fa,z=tree[y].fa;
		if(z!=k){
			if(Get(x)==Get(y))rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if(k==0)root = x;
}
int build(int l,int r,int fa){
	//将l~r区间插入splay中
	int mid = (l+r)>>1;
	++tot;
	int c = tot;
	tree[c].val = a[mid];
	tree[c].fa = fa;
	if(l<mid)tree[c].ch[0] = build(l,mid-1,c);
	if(r>mid)tree[c].ch[1] = build(mid+1,r,c);
	pushup(c);
	return c;
}
int kth(int x){
	int cur = root;
	while(cur){
		pushdown(cur);
		if(x<=tree[tree[cur].ch[0]].size)cur = tree[cur].ch[0];
		else{
			x-=tree[tree[cur].ch[0]].size;
			if(x<=1){
				splay(cur,0);
				return cur;
			}
			else{
				x--;
				cur = tree[cur].ch[1];
			}
		}
	}
	return -1;
}
void insert(int pos,int tot){
	//在pos后面插入a[1],a[2]...a[tot]
	int L = kth(pos+1),R=kth(pos+2);
	splay(L,0);
	splay(R,L);
	tree[R].ch[0] = build(1,tot,R);
	pushup(R);
	pushup(L);
}
void del(int pos,int tot){
	int L = kth(pos),R=kth(pos+tot+1);
	splay(L,0);
	splay(R,L);
	tree[R].ch[0] = 0;
	pushup(R);
	pushup(L);
}
void change(int pos,int tot,int c){
	int L=kth(pos),R=kth(pos+tot+1);
	splay(L,0);
	splay(R,L);
	tree[tree[R].ch[0]].flag = 1;
	tree[tree[R].ch[0]].tag = c;
	tree[tree[R].ch[0]].rev = 0;
	tree[tree[R].ch[0]].val = c;
	tree[tree[R].ch[0]].sum = c*tree[tree[R].ch[0]].size;
	if(c>0){
		tree[tree[R].ch[0]].lm = tree[tree[R].ch[0]].rm = tree[tree[R].ch[0]].max = tree[tree[R].ch[0]].sum;
	}
	else{
		tree[tree[R].ch[0]].lm = c;
		tree[tree[R].ch[0]].rm = c;
		tree[tree[R].ch[0]].max = c;
	}
	pushup(R);
	pushup(L);
}
void REV(int pos,int tot){
	int L=kth(pos),R=kth(pos+tot+1);
	splay(L,0);splay(R,L);
	tree[tree[R].ch[0]].rev^=1;
	swap(tree[tree[R].ch[0]].ch[0],tree[tree[R].ch[0]].ch[1]);
	swap(tree[tree[R].ch[0]].lm,tree[tree[R].ch[0]].rm);
	pushup(R);
	pushup(L);
}
int GetSum(int pos,int tot){
	int L=kth(pos),R=kth(pos+tot+1);
	splay(L,0);splay(R,L);
	return tree[tree[R].ch[0]].sum;
}
int GetMax(){
	return tree[root].max;
}
int main(){
	freopen("in.in","r",stdin);
	freopen("1.out","w",stdout);
	cin>>n>>m;
	a[0] =  a[n+1] = 0;
	tree[0].max = -1e9;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	root = build(0,n+1,0);
	for(int i=1;i<=m;i++){
		string s;
		int pos,tot,c;
		cin>>s;
		if(s=="INSERT"){
			cin>>pos>>tot;
			for(int i=1;i<=tot;i++){
				cin>>a[i];
			}
			insert(pos,tot);
		}
		else if(s=="DELETE"){
			cin>>pos>>tot;
			del(pos,tot);
		}
		else if(s=="MAKE-SAME"){
			cin>>pos>>tot>>c;
			change(pos,tot,c);
		}
		else if(s=="REVERSE"){
			cin>>pos>>tot;
			REV(pos,tot);
		}
		else if(s=="GET-SUM"){
			cin>>pos>>tot;
			cout<<GetSum(pos,tot)<<endl;
		}
		else cout<<GetMax()<<endl;
	}
	return 0;
}

题目

题目
P3369   【模板】普通平衡树
P3391   【模板】文艺平衡树
P2234   [HNOI2002] 营业额统计
P3850   [TJOI2007] 书架
P1486   [NOI2004] 郁闷的出纳员
P3224   [HNOI2012] 永无乡
P2286   [HNOI2004] 宠物收养场
P2042   [NOI2005] 维护数列
P2710   数列
P4008   [NOI2003] 文本编辑器
P2073   送花
P1503   鬼子进村
P1533   可怜的狗狗
状态
已结束
题目
13
开始时间
2026-6-2 0:00
截止时间
2026-6-13 23:59
可延期
24 小时
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 蜀ICP备2022005482号-4
  3. Worker 0, 31ms
  4. Powered by Hydro v5.0.4 Community