潍坊网站建设求职简历,网络推广方案策划书,网站建设重庆最加科技,网络营销思想的网站改版计划传送门 就是说要维护一个数据结构资瓷区间反转和查询第\(K\)大#xff0c;那么splay吧 我们可以把原数组按高度为第一关键字#xff0c;下标为第二关键字排序#xff0c;然后直接建出splay 这样的话每次第\(K\)大直接查询编号然后把它转到根节点#xff0c;那么左子树大小1…传送门 就是说要维护一个数据结构资瓷区间反转和查询第\(K\)大那么splay吧 我们可以把原数组按高度为第一关键字下标为第二关键字排序然后直接建出splay 这样的话每次第\(K\)大直接查询编号然后把它转到根节点那么左子树大小1就是下标了区间反转打标记就好了 //minamoto
#includebits/stdc.h
#define R register
#define inf 0x3f3f3f3f
#define fp(i,a,b) for(R int ia,Ib1;iI;i)
#define fd(i,a,b) for(R int ia,Ib-1;iI;--i)
#define go(u) for(int ihead[u],ve[i].v;i;ie[i].nx,ve[i].v)
using namespace std;
char buf[121],*p1buf,*p2buf;
inline char getc(){return p1p2(p2(p1buf)fread(buf,1,121,stdin),p1p2)?EOF:*p1;}
int read(){R int res,f1;R char ch;while((chgetc())9||ch0)(ch-)(f-1);for(resch-0;(chgetc())0ch9;resres*10ch-0);return res*f;
}
char sr[121],z[20];int C-1,Z0;
inline void Ot(){fwrite(sr,1,C1,stdout),C-1;}
void print(R int x){if(C120)Ot();if(x0)sr[C]-,x-x;while(z[Z]x%1048,x/10);while(sr[C]z[Z],--Z);sr[C] ;
}
const int N1e55;
struct node{int id,k;friend bool operator (const node a,const node b){return a.kb.k?a.idb.id:a.kb.k;}
}a[N];
int ch[N][2],fa[N],sz[N],tag[N],rt,n,ans,xx,yy;
inline int get(R int x){return ch[fa[x]][1]x;}
inline void upd(R int x){sz[x]sz[ch[x][0]]sz[ch[x][1]]1;}
void pd(R int x){if(tag[x]){if(ch[x][0])tag[ch[x][0]]^1;if(ch[x][1])tag[ch[x][1]]^1;swap(ch[x][0],ch[x][1]),tag[x]0;}
}
void rotate(R int x){int yfa[x],zfa[y],dget(x);pd(y),pd(x);ch[y][d]ch[x][d^1],fa[ch[y][d]]y,ch[x][d^1]y,fa[y]x,fa[x]z;if(z)ch[z][ch[z][1]y]x;upd(y);
}
void splay(R int x,R int goal){for(R int yfa[x],zfa[y];y!goal;yfa[x],zfa[y]){pd(z),pd(y),pd(x);if(z!goal)rotate(get(x)get(y)?y:x);rotate(x);}if(!goal)rtx;
}
void build(R int l,R int r,R int fat){if(lr)return;R int mid(lr)1;ch[fat][midfat]mid,sz[mid]1,fa[mid]fat;if(lr)return;build(l,mid-1,mid),build(mid1,r,mid);upd(mid);
}
int Kth(int x){int nowrt;while(true){pd(now);if(ch[now][0]xsz[ch[now][0]])nowch[now][0];else{x-sz[ch[now][0]]1;if(!x)return now;nowch[now][1];}}
}
int main(){
// freopen(testdata.in,r,stdin);nread();fp(i,2,n1)a[i].kread(),a[i].idi;a[1].id1,a[1].k-inf,a[n2].idn2,a[n2].kinf;sort(a1,an3),build(1,n2,0),rt(n3)1;fp(i,2,n){splay(a[i].id,0),anssz[ch[rt][0]]1;print(ans-1),xxKth(i-1),yyKth(ans1);splay(xx,0),splay(yy,xx);tag[ch[ch[rt][1]][0]]^1;}print(n);return Ot(),0;
} 转载于:https://www.cnblogs.com/bztMinamoto/p/10078567.html
