BZOJ 1503 [NOI 2004] 답답 한 출납원 (splay)
3705 단어 ACM_데이터 구조
#include
#include
#include
#include
using namespace std;
const int N = 101000,INF = 0x3f3f3f3f;
int dead,n,delta,total;
struct Node *nill;
struct Node {
Node *ch[2],*fa;
int val,sz;
bool d() { return fa->ch[1]==this; }
void setc(Node *o,int c) {
ch[c] = o;
o->fa = this;
up();
}
void up() {
if (this==nill) return ;
sz = ch[0]->sz + ch[1]->sz + 1;
}
}memo[N],*bat,*root;
void rot(Node *o) {
int c = o->d();
Node *tmp = o->fa;
tmp->setc(o->ch[c^1],c);
tmp->fa->setc(o,tmp->d());
o->setc(tmp,c^1);
o->fa->up();
}
void splay(Node *o,Node *p) {
while (o->fa != p) {
if (o->fa->fa!=p) {
o->d()==o->fa->d() ? rot(o->fa) : rot(o);
}
rot(o);
}
}
void newNode(Node *&o,int val = 0) {
o = bat ++;
o->ch[0] = o->ch[1] = o->fa = nill;
o->val = val;
o->sz = 1;
}
void init() {
bat = memo;
newNode(nill); nill->sz = 0;
root = nill;
}
Node *getK(int K) {
Node *o = root;
while (true) {
if (K==o->ch[0]->sz+1) return o;
if (o->ch[0]->sz >= K) {
o = o->ch[0];
} else {
K -= o->ch[0]->sz + 1;
o = o->ch[1];
}
}
}
Node *getBig(int val) {
Node *o = root;
Node *ret;
while (true) {
if (o==nill) return ret;
if (o->val >= val) {
ret = o;
o = o->ch[0];
} else {
o = o->ch[1];
}
}
}
void ins(int x) {
if (xsetc(root->ch[0],0);
root->setc(p,0);
}
void check() {
int val = dead-delta;
root = getBig(val);
splay(root,nill);
total += root->ch[0]->sz;
root->setc(nill,0);
}
int query(int K) {
if (root->sz-1 < K) return -1;
K = root->sz-1 - K + 1;
root = getK(K);
splay(root,nill);
return root->val + delta;
}
void show(Node *o) {
if (o==nill) return ;
show(o->ch[0]);
printf("%d ",o->val);
show(o->ch[1]);
}
void show() {
show(root); puts("");
}
int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&dead);
init();
newNode(root,INF);
while (n--) {
char s[13];
int x;
scanf("%s%d",s,&x);
if (s[0]=='I') {
ins(x);
} else if (s[0]=='A') {
delta += x;
} else if (s[0]=='S') {
delta -= x;
check();
} else {
printf("%d
",query(x));
}
}
printf("%d
",total);
// printf("%.6f
",(double)clock()/CLOCKS_PER_SEC);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ - 2104 주석 나무 판자That is, given an array a[1…n] of different integer numbers, your program must answer a series of questions Q(i, j, k) i...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.