Coder
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1954 Accepted Submission(s): 804
Problem Description
In mathematics and computer science, an algorithm describes a set of procedures or instructions that define a procedure. The term has become increasing popular since the advent of cheap and reliable computers. Many companies now
employ a single coder to write an algorithm that will replace many other employees. An added benefit to the employer is that the coder will also become redundant once their work is done.
1
You are now the signle coder, and have been assigned a new task writing code, since your boss would like to replace many other employees (and you when you become redundant once your task is complete).
Your code should be able to complete a task to replace these employees who do nothing all day but eating: make the digest sum.
By saying “digest sum” we study some properties of data. For the sake of simplicity, our data is a set of integers. Your code should give response to following operations:
1. add x – add the element x to the set;
2. del x – remove the element x from the set;
3. sum – find the digest sum of the set. The digest sum should be understood by
where the set S is written as {a1, a2, ... , ak} satisfying a1 < a2 < a3 < ... < ak
Can you complete this task (and be then fired)?
------------------------------------------------------------------------------
1 See http://uncyclopedia.wikia.com/wiki/Algorithm
employ a single coder to write an algorithm that will replace many other employees. An added benefit to the employer is that the coder will also become redundant once their work is done.
1
You are now the signle coder, and have been assigned a new task writing code, since your boss would like to replace many other employees (and you when you become redundant once your task is complete).
Your code should be able to complete a task to replace these employees who do nothing all day but eating: make the digest sum.
By saying “digest sum” we study some properties of data. For the sake of simplicity, our data is a set of integers. Your code should give response to following operations:
1. add x – add the element x to the set;
2. del x – remove the element x from the set;
3. sum – find the digest sum of the set. The digest sum should be understood by
where the set S is written as {a1, a2, ... , ak} satisfying a1 < a2 < a3 < ... < ak
Can you complete this task (and be then fired)?
------------------------------------------------------------------------------
1 See http://uncyclopedia.wikia.com/wiki/Algorithm
Input
There’re several test cases.
In each test case, the first line contains one integer N ( 1 <= N <= 105 ), the number of operations to process.
Then following is n lines, each one containing one of three operations: “add x” or “del x” or “sum”.
You may assume that 1 <= x <= 109.
Please see the sample for detailed format.
For any “add x” it is guaranteed that x is not currently in the set just before this operation.
For any “del x” it is guaranteed that x must currently be in the set just before this operation.
Please process until EOF (End Of File).
In each test case, the first line contains one integer N ( 1 <= N <= 105 ), the number of operations to process.
Then following is n lines, each one containing one of three operations: “add x” or “del x” or “sum”.
You may assume that 1 <= x <= 109.
Please see the sample for detailed format.
For any “add x” it is guaranteed that x is not currently in the set just before this operation.
For any “del x” it is guaranteed that x must currently be in the set just before this operation.
Please process until EOF (End Of File).
Output
For each operation “sum” please print one line containing exactly one integer denoting the digest sum of the current set. Print 0 if the set is empty.
Sample Input
9 add 1 add 2 add 3 add 4 add 5 sum add 6 del 3 sum 6 add 1 add 3 add 5 add 7 add 9 sum
Sample Output
3 4 5
又来试了一下这题，虽然用vector可以6s+水过，我还是尝试了一下BST的解法。
思路很直接，维护5棵BST。
insert x：询问一下所有小于x的数的个数size，然后将x插入tree[size%5]，将大于x的子树分离出来，循环右移一位。
delete x：分离出大于x的子树，循环左移一位，并且删除x。
sum ：更简单，直接输出tree[2]->sum
由于给定的集合元素不重复，删除元素时保证合法，挺方便的。
treap解法
#include<cstdio>
#include<cstdlib>
using namespace std;
const int inf=0x3f3f3f3f;
typedef long long ll;
struct node
{
int value,key,size;
ll sum;
node(){}
node(int v, node*n, int ky=0):value(v),sum(v),key(ky)
{c[0]=c[1]=n; size=1; if (!key) key=rand()-1;}
void update(){
size = c[0]->size + c[1]->size + 1;
sum = c[0]->sum + c[1]->sum + (ll)value;
}
node*c[2];
};
const int MAX = 200100;
class treap
{
static int cnt, top;
static node *stk[MAX], data[MAX], *null;
static node *newnode(int var, node *r, int key=0) {
node *p;
if (top) p = stk[--top];
else p = data+cnt++;
//p = data + cnt++;
*p = node(var, r, key);
return p;
}
void rot(node*&t,bool d)//rotate
{
node*c=t->c[d];
t->c[d]=c->c[!d];
c->c[!d]=t;
t->update(); c->update();
t=c;
}
void insert(node*&t, int x, int key=0)
{
if(t==null) {t=newnode(x,null,key);return;}
if(x==t->value) return;
bool d=x>t->value;
insert(t->c[d], x, key);
if(t->c[d]->key<t->key)
rot(t,d);
else
t->update();
//printf("value = %d key = %d\n", t->value, t->key);
}
void erase(node*&t,int x)
{
if(t==null) return;
if(t->value==x)
{
bool d=t->c[1]->key<t->c[0]->key;
if(t->c[d]==null)
{
stk[top++] = t;//delete t;
t=null;
return;
}
rot(t,d);
erase(t->c[!d],x);
}
else
{
bool d=x>t->value;
erase(t->c[d],x);
}
t->update();
}
node* selectk(node*t,int k)//select kth
{
int r=t->c[0]->size;
if(k==r) return t;
if(k<r) return selectk(t->c[0],k);
return selectk(t->c[1],k-r-1);
}
int rank(node*t,int x)
{
if(t==null) return 0;
int r=t->c[0]->size;
if(x==t->value) return r;
if(x<t->value) return rank(t->c[0],x);
return r+1+rank(t->c[1],x);
}
public:
node *root;
treap(){
root = null;
}
static void init(){
top = cnt = 0;
null=newnode(0,0);null->size=0;null->key=inf;
}
void cl( node *r){
if (r==0 || r==null) return ;
cl(r->c[0]);
cl(r->c[1]);
delete r;
}
void clear(){
//cl(root);
root=null;
}
void ins(int x)
{
insert(root,x);
}
int findkth(int k) //find kth
{
if(k>root->size) return -inf;
return selectk(root,k-1)->value;
}
int rank(int x)
{
return rank(root,x);
}
void del(int x)
{
erase(root,x);
}
static treap& join(treap &a, treap &b, int x){//a_i < b_i, virtual node is (x, -inf)
a.insert(a.root, x, -inf);
a.root->c[1] = b.root;
a.root->update();
a.erase(a.root, x);
return a;
}
node* split(int x){//return right_subtree,
erase(root, x);
insert(root, x, -inf);
node *l = root->c[0], *r = root->c[1];
/*
printf("split: root->value = %d\n", root->value);
printf("split: root->key = %d\n", root->key);
printf("split: root->c[1]->value = %d\n", root->c[1]->value);
printf("split: root->c[1]->key = %d\n", root->c[1]->key);
puts("");
*/
stk[top++] = root;//delete root;
root = l;
return r;
}
} t[5], tmp[5];
node *treap::null;
int treap::top, treap::cnt;
node *treap::stk[MAX];
node treap::data[MAX];
int main() {
int n,i,T,x,p;
char cmd[10];
srand(19921031);
//treap::init();
while (scanf("%d", &n) != EOF) {
treap::init();
for (i=0; i<5; i++){
t[i].clear();
tmp[i].clear();
}
for (T=0; T<n; T++){
scanf("%s", cmd);
if (*cmd=='a'){
scanf("%d", &x);
//for (i=0; i<5; i++) t[i].ins(x);
int size=0;
for (i=0; i<5; i++) {
tmp[ (i+1)%5 ].root = t[i].split(x);
size += t[i].root->size;
}
p = size % 5;
for (i=0; i<5; i++) treap::join( t[i], tmp[i], x );
t[p].ins(x);
//printf("size = %d\n", t[0].root->size);
}else if (*cmd=='d'){
scanf("%d", &x);
//for (i=0; i<5; i++) t[i].del(x);
//for (i=0; i<5; i++) t[i].ins(x);
for (i=0; i<5; i++) tmp[(i+4)%5].root = t[i].split(x);
for (i=0; i<5; i++) treap::join(t[i], tmp[i], x);
}else{
printf("%I64d\n", t[2].root->sum);
//printf("value = %d\n", t[2].root->value);
}
/*
printf("0:");t[0].debug();
printf("1:");t[1].debug();
printf("2:");t[2].debug();
printf("3:");t[3].debug();
printf("4:");t[4].debug();*/
}
}
}
Splay解法，快了Treap好多，理解不能。。
/*
Splay BST模板
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;
const int MAX = 200005;
struct node {
int key, size;
ll sum;
node *ch[2], *pre;
void update() {
size = ch[0]->size + ch[1]->size + 1;
sum = ch[0]->sum + ch[1]->sum + key;
}
};
int arr[MAX];
#define keytree root->ch[1]->ch[0]
class Splay {
static int cnt, top;
static node *stk[MAX], data[MAX], *null;
public:
node *root;
/*
* 获得一个新的节点，之前删除的节点会放到stk中以便再利用
*/
static node *Newnode(int var) {
node *p;
if (top) p = stk[--top];
else p = &data[cnt++];
p->key = var;
p->size = 1;
p->ch[0] = p->ch[1] = p->pre = null;
return p;
}
static void init() {
top = cnt = 0;
null = Newnode(0);
null -> size = 0;
null -> sum = 0;
}
void clear(){
root = null;
}
/*
* 旋转操作, c=0 表示左旋, c=1 表示右旋
*/
void rotate(node *x, int c) {
node *y = x->pre;
y->ch[!c] = x->ch[c];
if (x->ch[c] != null)
x->ch[c]->pre = y;
x->pre = y->pre;
if (y->pre != null)
y->pre->ch[ y == y->pre->ch[1] ] = x;
x->ch[c] = y;
y->pre = x;
y->update();
if (y == root) root = x;
}
/*
* 旋转使x成为f的子节点，若f为null则x旋转为根节点
*/
void splay(node *x, node *f) {
while (x->pre != f) {
if (x->pre->pre == f) {
rotate(x, x->pre->ch[0] == x);
break;
}
node *y = x->pre;
node *z = y->pre;
int c = (y == z->ch[0]);
if (x == y->ch[c]) {
rotate(x, !c); rotate(x, c); // 之字形旋转
} else {
rotate(y, c); rotate(x, c); // 一字形旋转
}
}
x->update();
}
/*
* 找到大小为x的节点，并将其升至根
*/
node* select(int x) {
node *z = root, *p = null;
while (z&&z!=null){
p = z;
if ( x == z->key ) break;
if ( x < z->key) z=z->ch[0];else z=z->ch[1];
}
splay(p, null);
return z;
}
/*
* 插入X
*/
void insert(int x) {
node *z = root, *p = null;
while (z&&z!=null){
p = z;
if ( x == z->key ) break;
if ( x < z->key) z=z->ch[0];else z=z->ch[1];
}
if (z->key==x) {
splay(z, null);
return ;
}
z = Newnode(x);z->pre = p;
if ( p==null ) root = z;
else if ( p->key < z->key ) p->ch[1] = z; else p->ch[0] = z;
splay(z, null);
}
/*
* 删除大小为x的数。
*/
void del(int x) {
node *res = select(x);
if (root->key!=x || res==null) { //puts("no find");
return ;
}
stk[top++] = root;
if (root->ch[0]==null) {
root = root->ch[1];
root->pre = null;
}
else if (root->ch[1]==null) {
root = root->ch[0];
root->pre = null;
}
else{
node *l, *r;
l = subtreemax(root->ch[0]);
r = subtreemin(root->ch[1]);
splay(l,null);
splay(r,l);
r->ch[0] = null;
splay(r,null);
}
}
node* subtreemin(node *p) {
while ( p->ch[0]!=null ){
p=p->ch[0];
}
return p;
}
node* subtreemax(node *p) {
while ( p->ch[1]!=null ){
p=p->ch[1];
}
return p;
}
void dfs( node *p ){
if (p->ch[0]!=null) dfs(p->ch[0]);
printf("%d ", p->key);
if (p->ch[1]!=null) dfs(p->ch[1]);
}
void debug(){
if (root==null) return ;
dfs(root);
puts("|@debug");
}
node* split(int x)//split the tree <x and >x, return right_subtree (>x), new root is left_subtree (<x)
{
//insert(x);
stk[top++] = root;
node *l=root->ch[0], *r=root->ch[1];
l->pre = r->pre = null;
root = l;
return r;
}
static Splay& join(Splay &a, Splay &b)//a_i < b_i, a = merge(a,b)
{
if (b.root==null) return a;
if (a.root==null) {
a.root=b.root;
return a;
}
node *r = a.subtreemax(a.root);
a.splay(r,null);
a.root->ch[1] = b.root; b.root->pre = a.root; a.root->update();
return a;
}
} t[5], tmp[5];
int Splay::cnt, Splay::top;
node *Splay::stk[MAX], *Splay::null;
node Splay::data[MAX];
int main() {
int n,i,T,x,p;
char cmd[10];
while (scanf("%d", &n) != EOF) {
Splay::init();
for (i=0; i<5; i++){
t[i].clear();
tmp[i].clear();
}
for (T=0; T<n; T++){
scanf("%s", cmd);
if (*cmd=='a'){
scanf("%d", &x);
for (i=0; i<5; i++) t[i].insert(x);
int size=0;
for (i=0; i<5; i++) {
tmp[ (i+1)%5 ].root = t[i].split(x);
size += t[i].root->size;
}
p = size % 5;
for (i=0; i<5; i++) Splay::join( t[i], tmp[i] );
t[p].insert(x);
//printf("size = %d\n", size);
}else if (*cmd=='d'){
scanf("%d", &x);
//for (i=0; i<5; i++) t[i].del(x);
for (i=0; i<5; i++) t[i].insert(x);
for (i=0; i<5; i++) tmp[(i+4)%5].root = t[i].split(x);
for (i=0; i<5; i++) Splay::join(t[i], tmp[i]);
}else{
printf("%I64d\n", t[2].root->sum);
}
/*
printf("0:");t[0].debug();
printf("1:");t[1].debug();
printf("2:");t[2].debug();
printf("3:");t[3].debug();
printf("4:");t[4].debug();*/
}
}
}