struct TreeNode {
int key;
TreeNode* left;
TreeNode* right;
int height; // 节点高度
int size; // 子树大小
int count; // 重复次数
TreeNode(int value)
: key(value), height(1), size(1), count(1), left(nullptr), right(nullptr) {}
};
class BalancedBST {
private:
TreeNode* root;
// 获取节点高度
int getHeight(TreeNode* node) const {
return node ? node->height : 0;
}
// 获取节点子树大小
int getSize(TreeNode* node) const {
return node ? node->size : 0;
}
// 更新节点高度和大小
void updateNodeInfo(TreeNode* node) const {
if (node) {
node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
node->size = node->count + getSize(node->left) + getSize(node->right);
}
}
// 获取平衡因子
int getBalanceFactor(TreeNode* node) const {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}
// 右旋
TreeNode* rightRotate(TreeNode* y) const {
TreeNode* x = y->left;
TreeNode* T2 = x->right;
x->right = y;
y->left = T2;
updateNodeInfo(y);
updateNodeInfo(x);
return x;
}
// 左旋
TreeNode* leftRotate(TreeNode* x) const {
TreeNode* y = x->right;
TreeNode* T2 = y->left;
y->left = x;
x->right = T2;
updateNodeInfo(x);
updateNodeInfo(y);
return y;
}
// 平衡节点
TreeNode* balanceNode(TreeNode* node) const {
if (!node) return nullptr;
updateNodeInfo(node);
int balance = getBalanceFactor(node);
// Left Left Case
if (balance > 1 && getBalanceFactor(node->left) >= 0)
return rightRotate(node);
// Right Right Case
if (balance < -1 && getBalanceFactor(node->right) <= 0)
return leftRotate(node);
// Left Right Case
if (balance > 1 && getBalanceFactor(node->left) < 0) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && getBalanceFactor(node->right) > 0) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 递归插入
TreeNode* insertHelper(TreeNode* node, int value){
if (!node) {
return new TreeNode(value);
}
if (value < node->key) {
node->left = insertHelper(node->left, value);
} else if (value > node->key) {
node->right = insertHelper(node->right, value);
} else {
node->count++;
node->size++;
return node;
}
return balanceNode(node);
}
// 查找最小节点
TreeNode* findMinNode(TreeNode* node) const {
while (node && node->left) {
node = node->left;
}
return node;
}
// 递归删除
TreeNode* removeHelper(TreeNode* node, int value){
if (!node) return nullptr;
if (value < node->key) {
node->left = removeHelper(node->left, value);
} else if (value > node->key) {
node->right = removeHelper(node->right, value);
} else {
if (node->count > 1) {
node->count--;
node->size--;
return node;
}
if (!node->left || !node->right) {
TreeNode* temp = node->left ? node->left : node->right;
if (!temp) {
delete node;
return nullptr;
} else {
*node = *temp;
delete temp;
}
} else {
TreeNode* successor = findMinNode(node->right);
node->key = successor->key;
node->count = successor->count;
successor->count = 1;
node->right = removeHelper(node->right, successor->key);
}
}
return balanceNode(node);
}
// 递归查找
bool searchHelper(TreeNode* node, int value) const {
if (!node) return false;
if (value == node->key) return true;
if (value < node->key) return searchHelper(node->left, value);
return searchHelper(node->right, value);
}
// 递归中序遍历
void inorderHelper(TreeNode* node, std::vector<int>& result) const {
if (!node) return;
inorderHelper(node->left, result);
for (int i = 0; i < node->count; ++i) {
result.push_back(node->key);
}
inorderHelper(node->right, result);
}
// 递归查询排名
int rankHelper(TreeNode* node, int value) const {
if (!node) return 0;
if (value < node->key) {
return rankHelper(node->left, value);
} else if (value > node->key) {
return getSize(node->left) + node->count + rankHelper(node->right, value);
} else {
return getSize(node->left) + 1;
}
}
// 递归按排名查找
int selectHelper(TreeNode* node, int k) const {
if (!node) return -1;
int leftSize = getSize(node->left);
if (k <= leftSize) {
return selectHelper(node->left, k);
} else if (k <= leftSize + node->count) {
return node->key;
} else {
return selectHelper(node->right, k - leftSize - node->count);
}
}
// 递归释放所有节点
void clearHelper(TreeNode* node) {
if (!node) return;
clearHelper(node->left);
clearHelper(node->right);
delete node;
}
public:
BalancedBST() : root(nullptr) {}
// 插入元素 - O(log n)
void insert(int value) {
root = insertHelper(root, value);
}
// 删除元素 - O(log n)
void remove(int value) {
root = removeHelper(root, value);
}
// 查找元素 - O(log n)
bool search(int value) const {
return searchHelper(root, value);
}
// 获取最小值 - O(log n)
int min() const {
TreeNode* node = findMinNode(root);
return node ? node->key : -1;
}
// 获取最大值 - O(log n)
int max() const {
TreeNode* node = root;
while (node && node->right) {
node = node->right;
}
return node ? node->key : -1;
}
// 中序遍历 - O(n)
std::vector<int> inorder() const {
std::vector<int> result;
inorderHelper(root, result);
return result;
}
// 查询排名 - O(log n)
int rank(int value) const {
return rankHelper(root, value);
}
// 按排名查找 - O(log n)
int select(int k) const {
return selectHelper(root, k);
}
// 清空整棵树
void clear() {
clearHelper(root);
root = nullptr;
}
// 获取树的大小 - O(1)
int size() const {
return getSize(root);
}
// 获取树的高度 - O(1)
int height() const {
return getHeight(root);
}
};#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int T,x,y,n,o,root,a[N];
struct Splay{int v,fa,ps[2],tag,cnt,size;}tr[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void pushup(Re p){if(!p)return;tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void pushdown(Re p){
if(tr[p].tag)tr[p].tag=0,swap(pl,pr),tr[pl].tag^=1,tr[pr].tag^=1;
}
inline void rotate(Re p){
Re y=pf,ys=which(p);
Re R=tr[y].fa,Rs=which(y);
Re B=tr[p].ps[ys^1];
connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);
pushup(y),pushup(p);
}
inline void Splay(Re p,Re to){
for(Re fa;(fa=pf)!=to;rotate(p))
if(tr[fa].fa!=to)rotate(which(p)==which(fa)?fa:p);
if(!to)root=p;
}
inline void New(Re x,Re fa){
tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;
if(fa)tr[fa].ps[tr[fa].v<x]=o;
}
inline int ask_w(Re p,Re x){
pushdown(p);
if(x<=tr[pl].size)return ask_w(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?p:ask_w(pr,x-tmp);
}
}
inline void build(Re &p,Re L,Re R,Re fa){
if(L>R)return;
Re mid=L+R>>1;p=++o;
pf=fa,pv=a[mid];
tr[p].cnt=tr[p].size=1;
build(pl,L,mid-1,p),build(pr,mid+1,R,p);
pushup(p);
}
inline void reverse(Re l,Re r){
l=ask_w(root,l-1),r=ask_w(root,r+1);
Splay(l,0),Splay(r,l);
tr[tr[r].ps[0]].tag^=1;
}
inline void print(Re p){
pushdown(p);
if(pl)print(pl);
if(pv!=inf&&pv!=-inf)printf("%d ",pv);
if(pr)print(pr);
}
int main(){
in(n),in(T);
a[1]=-inf,a[n+2]=inf;
for(Re i=2;i<=n+1;++i)a[i]=i-1;
build(root,1,n+2,0);
while(T--)in(x),in(y),reverse(x+1,y+1);
print(root);
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int T,x,y,n,o,root,a[N];
struct Splay{int v,fa,ps[2],tag,cnt,size;}tr[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void pushup(Re p){if(!p)return;tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void pushdown(Re p){
if(tr[p].tag)tr[p].tag=0,swap(pl,pr),tr[pl].tag^=1,tr[pr].tag^=1;
}
inline void rotate(Re p){
Re y=pf,ys=which(p);
Re R=tr[y].fa,Rs=which(y);
Re B=tr[p].ps[ys^1];
connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);
pushup(y),pushup(p);
}
inline void Splay(Re p,Re to){
for(Re fa;(fa=pf)!=to;rotate(p))
if(tr[fa].fa!=to)rotate(which(p)==which(fa)?fa:p);
if(!to)root=p;
}
inline void New(Re x,Re fa){
tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;
if(fa)tr[fa].ps[tr[fa].v<x]=o;
}
inline int ask_w(Re p,Re x){
pushdown(p);
if(x<=tr[pl].size)return ask_w(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?p:ask_w(pr,x-tmp);
}
}
inline void build(Re &p,Re L,Re R,Re fa){
if(L>R)return;
Re mid=L+R>>1;p=++o;
pf=fa,pv=a[mid];
tr[p].cnt=tr[p].size=1;
build(pl,L,mid-1,p),build(pr,mid+1,R,p);
pushup(p);
}
inline void reverse(Re l,Re r){
l=ask_w(root,l-1),r=ask_w(root,r+1);
Splay(l,0),Splay(r,l);
tr[tr[r].ps[0]].tag^=1;
}
inline void print(Re p){
pushdown(p);
if(pl)print(pl);
if(pv!=inf&&pv!=-inf)printf("%d ",pv);
if(pr)print(pr);
}
int main(){
in(n),in(T);
a[1]=-inf,a[n+2]=inf;
for(Re i=2;i<=n+1;++i)a[i]=i-1;
build(root,1,n+2,0);
while(T--)in(x),in(y),reverse(x+1,y+1);
print(root);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,inf=1e9;
int n,x,y,z,T,A[N];char op[20];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Splay{
#define pl (tr[p].ps[0])
#define pr (tr[p].ps[1])
#define pf (tr[p].fa)
#define pv (tr[p].v)
int O,root,Q[N];queue<int>D;
struct QAQ{int v,S,fa,max,lmax,rmax,size,ps[2];bool tag,turn;}tr[N];
inline void pushup(Re p){
tr[p].S=tr[pl].S+tr[pr].S+pv;
tr[p].size=tr[pl].size+tr[pr].size+1;
tr[p].lmax=max(tr[pl].lmax,tr[pl].S+pv+tr[pr].lmax);
tr[p].rmax=max(tr[pr].rmax,tr[pr].S+pv+tr[pl].rmax);
tr[p].max=max(tr[pl].rmax+pv+tr[pr].lmax,max(tr[pl].max,tr[pr].max));
}
inline void updata(Re p){tr[p].turn^=1,swap(pl,pr),swap(tr[p].lmax,tr[p].rmax);}
inline void updata(Re p,Re v){
tr[p].tag=1,tr[p].S=(pv=v)*tr[p].size;
if(v>0)tr[p].lmax=tr[p].rmax=tr[p].max=tr[p].S;
else tr[p].lmax=tr[p].rmax=0,tr[p].max=v;
}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl,pv);
if(pr)updata(pr,pv);
tr[p].tag=tr[p].turn=0;
}
if(tr[p].turn){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].turn=0;
}
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
connect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);
pushup(fa),pushup(p);
}
inline void splay(Re p,Re to){
Re x=p,t=0;Q[++t]=x;
while(tr[x].fa)Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;pf!=to;rotate(p))
if(tr[fa=pf].fa!=to)rotate(which(p)==which(fa)?fa:p);
if(!to)root=p;
}
inline void CL(Re p){
tr[p].size=tr[p].turn=tr[p].tag=tr[p].lmax=tr[p].rmax=tr[p].S=pv=pf=pl=pr=0,tr[p].max=-inf;
}
inline int New(){
Re p;
if(D.empty())p=++O;
else p=D.front(),D.pop();
CL(p),tr[p].size=1;return p;
}
inline void build(Re &p,Re L,Re R,Re fa){
if(L>R)return;Re mid=(L+R)>>1;p=New(),pv=A[mid],pf=fa;
build(pl,L,mid-1,p),build(pr,mid+1,R,p);
pushup(p);
}
inline void recycle(Re p){
if(pl)recycle(pl);
if(pr)recycle(pr);
D.push(p),CL(p);
}
inline int find(Re p,Re K){
pushdown(p);
if(K<=tr[pl].size)return find(pl,K);
return K<=tr[pl].size+1?p:find(pr,K-tr[pl].size-1);
}
inline int split(Re L,Re R){
Re p=find(root,L-1),q=find(root,R+1);
splay(p,0),splay(q,p);return tr[q].ps[0];
}
inline void insert(Re st,Re m){
for(Re i=1;i<=m;++i)in(A[i]);
Re rt=0;build(rt,1,m,0);
Re p=find(root,st),q=find(root,st+1);
splay(p,0),splay(q,p);
connect(rt,q,0),pushup(q),pushup(p);
}
inline void erase(Re L,Re R){
Re p=split(L,R),fa=pf;
tr[fa].ps[0]=pf=0,recycle(p);
pushup(fa),pushup(tr[fa].fa);
}
inline int ask(Re L,Re R){return tr[split(L,R)].S;}
inline int ask_max(Re L,Re R){return tr[split(L,R)].max;}
inline void change(Re L,Re R,Re v){
Re p=split(L,R);updata(p,v),pushup(pf),pushup(tr[pf].fa);
}
inline void reverse(Re L,Re R){
Re p=split(L,R);
if(!tr[p].tag)updata(p),pushup(pf),pushup(tr[pf].fa);
}
}TR;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),TR.tr[0].max=A[1]=A[n+2]=-inf;
for(Re i=2;i<=n+1;++i)in(A[i]);
TR.build(TR.root,1,n+2,0);
while(T--){
scanf("%s",op);
if(op[0]=='M'&&op[2]=='X')in(x),in(y),++x,printf("%d\n",TR.ask_max(x,x+y-1));
else if(op[0]=='G'&&(int)strlen(op)==3)in(x),++x,printf("%d\n",TR.ask(x,x));
else{
in(x),in(y),++x;
if(op[0]=='I')TR.insert(x,y);
if(op[0]=='D')TR.erase(x,x+y-1);
if(op[0]=='M')in(z),TR.change(x,x+y-1,z);
if(op[0]=='R')TR.reverse(x,x+y-1);
if(op[0]=='G')printf("%d\n",TR.ask(x,x+y-1));
}
}
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+5;
int x,T,op;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Splay{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
int O,root;
struct QAQ{int v,fa,cnt,size,ps[2];}tr[N];
inline void pushup(Re p){
if(p)tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
connect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);
pushup(fa),pushup(p);
}
inline void splay(Re p){
for(Re fa;fa=pf;rotate(p))
if(tr[fa].fa)rotate(which(p)==which(fa)?fa:p);
root=p;
}
inline int ask_level(Re p,Re x){
if(x==pv){Re ans=tr[pl].size+1;splay(p);return ans;}
return x<pv?ask_level(pl,x):tr[pl].size+tr[p].cnt+ask_level(pr,x);
}
inline int ask_v(Re p,Re k){
if(!p)return 0;
if(k<=tr[pl].size)return ask_v(pl,k);
Re tmp=tr[pl].size+tr[p].cnt;
return k<=tmp?pv:ask_v(pr,k-tmp);
}
inline int pre(Re p){p=pl;while(pr)p=pr;return p;}
inline int nex(Re p){p=pr;while(pl)p=pl;return p;}
inline void insert(Re x){
Re p=root,fa=0;
while(p&&pv!=x)fa=p,p=tr[p].ps[x>pv];
if(p)++tr[p].cnt,pushup(p);
else{
tr[p=++O]=(QAQ){x,fa,1,1};
if(fa)tr[fa].ps[x>tr[fa].v]=p;
}
splay(p);
}
inline void del(Re x){
ask_level(root,x);Re p=root;
if(tr[p].cnt>1){--tr[p].cnt,pushup(p);return;}
if(!pl&&!pr){root=0;return;}
if(!pl||!pr){tr[root=pl+pr].fa=0;return;}
splay(pre(p));
tr[root].ps[1]=pr,tr[pr].fa=root;
pushup(root);
}
inline int ask_pre(Re x){insert(x);Re ans=tr[pre(root)].v;del(x);return ans;}
inline int ask_nex(Re x){insert(x);Re ans=tr[nex(root)].v;del(x);return ans;}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(T);
while(T--){
in(op),in(x);
if(op==1)T1.insert(x);
if(op==2)T1.del(x);
if(op==3)printf("%d\n",T1.ask_level(T1.root,x));
if(op==4)printf("%d\n",T1.ask_v(T1.root,x));
if(op==5)printf("%d\n",T1.ask_pre(x));
if(op==6)printf("%d\n",T1.ask_nex(x));
}
}
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int T,a,b,n,o,root;
struct Splay{int v,fa,ps[2],cnt,size;}tr[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void pushup(Re p){if(!p)return;/*�������Ҫ���ж�return����������*/tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void rotate(Re p){
Re y=pf,ys=which(p);
Re R=tr[y].fa,Rs=which(y);
Re B=tr[p].ps[ys^1];
connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);
pushup(y),pushup(p);
}
inline void Splay(Re p){
for(Re fa;fa=pf;rotate(p))
if(tr[fa].fa)rotate(which(p)==which(fa)?fa:p);
root=p;
}
inline void New(Re x,Re fa){
tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;
if(fa)tr[fa].ps[tr[fa].v<x]=o;
}
inline void insert(Re x){
if(!root){New(x,0);root=o;return;}
int p=root,fa=0;
while(1){
if(x==pv){++tr[p].cnt,pushup(p),pushup(fa),Splay(p);break;}
fa=p,p=tr[p].ps[pv<x];
if(!p){New(x,fa),pushup(fa),Splay(o);break;}
}
}
inline int ask_level(Re p,Re x){
//printf("p: %d\n",p);exit(0);
if(x==pv){Re ans=tr[pl].size+1;Splay(p);return ans;}
else return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);
}
inline int ask_v(Re p,Re x){
if(x<=tr[pl].size)return ask_v(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?pv:ask_v(pr,x-tmp);
}
}
inline int ask_nex_p(Re p){p=pr;while(pl)p=pl;return p;}
inline int ask_pri_p(Re p){p=pl;while(pr)p=pr;return p;}
inline void del(Re x){
ask_level(root,x);Re p=root;
if(tr[p].cnt>1){--tr[p].cnt,--tr[p].size;return;}
if(!pl&&!pr){root=0;return;}
if(!pl||!pr){tr[root=pl+pr].fa=0;return;}
Splay(ask_pri_p(root));
tr[root].ps[1]=pr,tr[pr].fa=root;
pushup(root);
}
int main(){
in(T);
while(T--){
in(a),in(b);
if(a==1)insert(b);
if(a==2)del(b);
if(a==3)printf("%d\n",ask_level(root,b));
if(a==4)printf("%d\n",ask_v(root,b));
if(a==5)insert(b),printf("%d\n",tr[ask_pri_p(root)].v),del(b);
if(a==6)insert(b),printf("%d\n",tr[ask_nex_p(root)].v),del(b);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define Re register int
#define pl tr[p].lp
#define pr tr[p].rp
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int a,b,o,T,root;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];
inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void lturn(Re &p){
Re q=pr;pr=tr[q].lp,tr[q].lp=p;
pushup(p),pushup(p=q);
}
inline void rturn(Re &p){
Re q=pl;pl=tr[q].rp,tr[q].rp=p;
pushup(p),pushup(p=q);
}
inline void insert(Re &p,Re x){
if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}
++tr[p].size;
if(x==pv)++tr[p].cnt;
else if(x<pv){
insert(pl,x);
if(tr[pl].rd<tr[p].rd)rturn(p);
}
else{
insert(pr,x);
if(tr[pr].rd<tr[p].rd)lturn(p);
}
}
inline void del(Re &p,Re x){
if(!p)return;
if(x<pv)--tr[p].size,del(pl,x);
else if(x>pv)--tr[p].size,del(pr,x);
else{
if(tr[p].cnt>1)--tr[p].cnt,--tr[p].size;
else{
if(pl*pr==0)p=pl+pr;
else if(tr[pl].rd<tr[pr].rd)rturn(p),del(p,x);
else lturn(p),del(p,x);
}
}
}
inline int ask_level(Re p,Re x){
if(x==pv)return tr[pl].size+1;
else return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);
}
inline int ask_v(Re p,Re x){
if(x<=tr[pl].size)return ask_v(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?pv:ask_v(pr,x-tmp);
}
}
inline int ask_pri(Re p,Re x){
if(!p)return -inf;
if(x<=pv)return ask_pri(pl,x);
else return max(pv,ask_pri(pr,x));
}
inline int ask_nex(Re p,Re x){
if(!p)return inf;
if(x>=pv)return ask_nex(pr,x);
else return min(pv,ask_nex(pl,x));
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
int main(){
srand((int)time(NULL));
in(T);
while(T--){
in(a),in(b);
if(a==1)insert(root,b);
if(a==2)del(root,b);
if(a==3)write(ask_level(root,b)),puts("");
if(a==4)write(ask_v(root,b)),puts("");
if(a==5)write(ask_pri(root,b)),puts("");
if(a==6)write(ask_nex(root,b)),puts("");
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define Re register int
#define pl tr[p].lp
#define pr tr[p].rp
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int a,b,o,T,root;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];
inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void lturn(Re &p){
Re q=pr;pr=tr[q].lp,tr[q].lp=p;
pushup(p),pushup(p=q);
}
inline void rturn(Re &p){
Re q=pl;pl=tr[q].rp,tr[q].rp=p;
pushup(p),pushup(p=q);
}
inline void insert(Re &p,Re x){
if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}
++tr[p].size;
if(x==pv)++tr[p].cnt;
else if(x<pv){
insert(pl,x);
if(tr[pl].rd<tr[p].rd)rturn(p);
}
else{
insert(pr,x);
if(tr[pr].rd<tr[p].rd)lturn(p);
}
}
inline void del(Re &p,Re x){
if(!p)return;
if(x<pv)--tr[p].size,del(pl,x);
else if(x>pv)--tr[p].size,del(pr,x);
else{
if(tr[p].cnt>1)--tr[p].cnt,--tr[p].size;
else{
if(pl*pr==0)p=pl+pr;
else if(tr[pl].rd<tr[pr].rd)rturn(p),del(p,x);
else lturn(p),del(p,x);
}
}
}
inline int ask_level(Re p,Re x){
if(x==pv)return tr[pl].size+1;
else return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);
}
inline int ask_v(Re p,Re x){
if(x<=tr[pl].size)return ask_v(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?pv:ask_v(pr,x-tmp);
}
}
inline int ask_pri(Re p,Re x){
if(!p)return -inf;
if(x<=pv)return ask_pri(pl,x);
else return max(pv,ask_pri(pr,x));
}
inline int ask_nex(Re p,Re x){
if(!p)return inf;
if(x>=pv)return ask_nex(pr,x);
else return min(pv,ask_nex(pl,x));
}
int main(){
srand((int)time(NULL));
in(T);
while(T--){
in(a),in(b);
if(a==1)insert(root,b);
if(a==2)del(root,b);
if(a==3)printf("%d\n",ask_level(root,b));
if(a==4)printf("%d\n",ask_v(root,b));
if(a==5)printf("%d\n",ask_pri(root,b));
if(a==6)printf("%d\n",ask_nex(root,b));
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20];
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=0;
F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
if(tmp>=k){
F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
return ask_kth(L,mid,k);
}
else{
F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
return ask_kth(mid+1,R,k-tmp);
}
}
inline int ask_kth_pre(Re L,Re R,Re k){
tl=tr=0;
for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
Re w=lo(a[x]);
for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
return ans;
}
int main(){
in(n),in(T),m=n;
F(i,1,n)in(a[i]),b[i]=a[i];
F(i,1,T){
in(opt[i]);
if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
else{
in(Q[i].l),in(Q[i].r),in(Q[i].k);
if(opt[i]!=2)b[++m]=Q[i].k;
}
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,n)add_pre(i,1);
F(i,1,T){
if(opt[i]==1)Q[i].k=lo(Q[i].k),printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
if(opt[i]==2)printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
if(opt[i]==3)add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
if(opt[i]==4){
Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k)-1);
if(!level)printf("%d\n",-inf);
else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level));
}
if(opt[i]==5){
Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k));
if(level==Q[i].r-Q[i].l+1)printf("%d\n",inf);
else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level+1));
}
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20];
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=0;
F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
if(tmp>=k){
F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
return ask_kth(L,mid,k);
}
else{
F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
return ask_kth(mid+1,R,k-tmp);
}
}
inline int ask_kth_pre(Re L,Re R,Re k){
tl=tr=0;
for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
Re w=lo(a[x]);
for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
return ans;
}
int main(){
// printf("%lf\n",(sizeof(tree))/1024.0/1024.0);
// printf("%lf\n",(sizeof(tree)+sizeof(Q)+sizeof(c)+sizeof(a)+sizeof(b)+sizeof(pt)+sizeof(C))/1024.0/1024.0);
in(n),in(T),m=n;
F(i,1,n)in(a[i]),b[i]=a[i];
F(i,1,T){
in(opt[i]);
if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
else{
in(Q[i].l),in(Q[i].r),in(Q[i].k);
if(opt[i]!=2)b[++m]=Q[i].k;
}
}
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
F(i,1,n)add_pre(i,1);
F(i,1,T){
if(opt[i]==1)
Q[i].k=lo(Q[i].k),
printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
if(opt[i]==2)
printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
if(opt[i]==3)
add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
if(opt[i]==4){
}
if(opt[i]==5){
}
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#define Re register int
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
#define P(x) if(op[i]==x)
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,fu,C[N],a[N],b[N],Q[N],op[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void add(Re x,Re v){while(x<=m)C[x]+=v,x+=x&-x;}
inline int ask(Re x){
Re ans=0;
while(x>0)ans+=C[x],x-=x&-x;
return ans;
}
inline int ask_kth(Re k){
Re l=0,r=m;
while(l<r){
Re mid=l+r>>1;
if(ask(mid)>=k)r=mid;
else l=mid+1;
}
return b[l];
}
int main(){
in(T);
F(i,1,T){
in(op[i]),in(Q[i]);
if(op[i]!=4)b[++m]=Q[i];
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,T){
P(1)add(lo(Q[i]),1);
P(2)add(lo(Q[i]),-1);
P(3)printf("%d\n",ask(lo(Q[i])-1)+1);
P(4)printf("%d\n",ask_kth(Q[i]));
P(5)printf("%d\n",ask_kth(ask(lo(Q[i])-1)));
P(6)printf("%d\n",ask_kth(ask(lo(Q[i]))+1));
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,t,fu,cnt,root,a[N],b[N],Q[N],opt[N];
struct QAQ{int g,lp,rp;}tree[N<<1];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re p,Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=tree[pl].g;
if(tmp>=k)return ask_kth(pl,L,mid,k);
else return ask_kth(pr,mid+1,R,k-tmp);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(!x)return 0;
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
int main(){
in(T);
F(i,1,T){
in(opt[i]),in(Q[i]);
if(opt[i]!=4)b[++m]=Q[i];
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,T){
if(opt[i]==1)add(root,1,m,lo(Q[i]),1);
if(opt[i]==2)add(root,1,m,lo(Q[i]),-1);
if(opt[i]==3)printf("%d\n",ask_level(root,1,m,lo(Q[i])-1)+1);
if(opt[i]==4)printf("%d\n",ask_kth(root,1,m,Q[i]));
if(opt[i]==5){
Re level=ask_level(root,1,m,lo(Q[i])-1);
printf("%d\n",ask_kth(root,1,m,level));
}
if(opt[i]==6){
Re level=ask_level(root,1,m,lo(Q[i]));
printf("%d\n",ask_kth(root,1,m,level+1));
}
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define Re register int
#define pl tr[p].lp
#define pr tr[p].rp
#define pv tr[p].v
using namespace std;
const int N=32780,inf=2e9;
int a,o,T,ans,root;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];
inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void lturn(Re &p){
Re q=pr;pr=tr[q].lp,tr[q].lp=p;
pushup(p),pushup(p=q);
}
inline void rturn(Re &p){
Re q=pl;pl=tr[q].rp,tr[q].rp=p;
pushup(p),pushup(p=q);
}
inline void insert(Re &p,Re x){
if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}
++tr[p].size;
if(x==pv)++tr[p].cnt;
else if(x<pv){
insert(pl,x);
if(tr[pl].rd<tr[p].rd)rturn(p);
}
else{
insert(pr,x);
if(tr[pr].rd<tr[p].rd)lturn(p);
}
}
inline int ask_pri(Re p,Re x){
if(!p)return -inf;
if(x==pv)return x;
else if(x<pv)return ask_pri(pl,x);
else return max(pv,ask_pri(pr,x));
}
inline int ask_nex(Re p,Re x){
if(!p)return inf;
if(x==pv)return x;
else if(x>pv)return ask_nex(pr,x);
else return min(pv,ask_nex(pl,x));
}
int main(){
srand((int)time(NULL));
in(T);--T;in(a);ans=a;insert(root,a);
while(T--){
in(a);
ans+=min(abs(a-ask_pri(root,a)),abs(a-ask_nex(root,a)));
insert(root,a);
}
printf("%d",ans);
}