題目：http://www.lydsy.com/JudgeOnline/problem.php?id=1503

?

#include <iostream> #include <string.h> #include <stdio.h>using namespace std;struct Node {int val,size,cnt,lazy;Node *pre,*ch[2];Node(){size = lazy = cnt = 0;} };Node *null,*root,*newNode,*last;void Init() //新增的newNode為root的父親節點 {null = new(Node);root = null;newNode = new(Node);newNode->ch[0] = root;newNode->ch[1] = null;root->pre = newNode; }void Update(Node* &t) {t->size = t->cnt + t->ch[0]->size + t->ch[1]->size;t->ch[0]->pre = t->ch[1]->pre = t; }int F(Node *t) // 判斷當前點的是左孩子還是右孩子 {return t->pre->ch[1] == t; }void Rotate(Node* t,int c) {Node *k = t->ch[c];k->pre = t->pre;t->pre->ch[F(t)] = k;t->ch[c] = k->ch[!c];k->ch[!c] = t;Update(t);Update(k); }void Splay(Node* last,Node* newNode) {Node *tmp = last;while(tmp->pre != newNode){if(tmp->pre->pre == newNode)Rotate(tmp->pre,F(tmp));else if(F(tmp->pre) == F(tmp)){Rotate(tmp->pre->pre,F(tmp->pre));Rotate(tmp->pre,F(tmp));}else{Rotate(tmp->pre,F(tmp));Rotate(tmp->pre,F(tmp));}}root = newNode->ch[0]; }void PushDown(Node* &t) {t->ch[0]->val += t->lazy;t->ch[0]->lazy += t->lazy;t->ch[1]->val += t->lazy;t->ch[1]->lazy += t->lazy;t->lazy = 0; }void Insert(Node* &t,int x) {if(t == null){t=new(Node);t->val = x;t->ch[0] = t->ch[1] = null;t->size = t->cnt = 1;last = t;return;}PushDown(t);if(t->val == x) t->cnt++;if(t->val > x) Insert(t->ch[0],x);if(t->val < x) Insert(t->ch[1],x);Update(t); }Node *Find(Node *t,int x) //查找后繼，包括等于自己 {if(t == null) return null;PushDown(t);if(t->val == x) return t;if(t->val < x) return Find(t->ch[1],x);if(t->val > x){Node *tmp = Find(t->ch[0],x);if(tmp != null) return tmp;else return t;} }int Query(Node *t,int k) //詢問第K大 {if(t == null) return -1;PushDown(t);if(t->ch[1]->size >= k) return Query(t->ch[1],k);if(t->ch[1]->size + t->cnt >= k) return t->val;return Query(t->ch[0],k - t->ch[1]->size - t->cnt); }void Work() {int n,limit;scanf("%d%d%*c",&n,&limit);int x,ans = 0;while(n--){char c;scanf("%c %d%*c",&c,&x);if(c == 'I'&&x < limit) continue;if(c == 'I'){Insert(newNode->ch[0],x);Update(newNode);Splay(last,newNode);}else if(c == 'A'){root->val += x;root->lazy += x;}else if(c == 'S'){last = null;last = Find(root,limit + x);if(last == null){ans += root->size;root = null;newNode->ch[0] = root;Update(newNode);}else{Splay(last,newNode);ans += root->ch[0]->size;root->ch[0] = null;root->val -= x;root->lazy -= x;Update(root);}}else if(c == 'F')printf("%d\n",Query(root,x));}printf("%d\n",ans); }int main() {Init();Work();return 0; }

?

總結

以上是生活随笔為你收集整理的BZOJ1503(Splay)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。