Viewing Text Document

Title:

Owner: Andrian Kurniady

Last updated on: Tuesday, 15 July 2008

Description:

Content:

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
int delt[101000];
int isi[101000][6];

char buffer[500];

typedef struct Node {
    int x;
    int baka;
    int count;
    int min, max;
    Node* left, *right;
} Node;

Node preReserve[1000000];
int upc;

inline Node* make_Node(int x){
    Node* temp = preReserve+upc;
    upc++;
    
    temp->baka = 1;
    temp->count = 1;
    temp->x = x;
    temp->left = NULL;
    temp->right = NULL;    
    temp->min = x;
    temp->max = x;
    return temp;
}
void insert(Node* pos, int x){
    pos->max>?=x;
    pos->min<?=x;
    
    if (pos->x==x){
        pos->baka++;
        pos->count++;
    } else if (pos->x>x){
        // kiri
        if (pos->left!=NULL){
            pos->baka++;
            insert(pos->left, x);
        } else {
            pos->baka++;
            pos->left = make_Node(x);
        }
    } else {
        // kanan
        if (pos->right!=NULL){
            pos->baka++;
            insert(pos->right, x);
        } else {
            pos->baka++;
            pos->right = make_Node(x);
        }        
    }
}
int countBetween(Node* pos, int a, int b, int kiripol, int kananpol){
    if (pos==NULL) return 0;
    
    back:
    
    if (kiripol && kananpol)
        return pos->baka;
        
    if (pos->min>b || pos->max<a) return 0;
    
    int x = pos->x;
    if (kiripol){
        if (pos->max<=b){
            return pos->baka;
        } else {
            if (b<x){
                return countBetween(pos->left, a,b,1, 0);
            } else if (b==x){
                return pos->left->baka + (pos->count);
            } else {
                // b > x
                return pos->left->baka +(pos->count)+countBetween(pos->right, a,b,1,0);
            }
        }
    } else if (kananpol){
        if (pos->min>=a){
            return pos->baka;
        } else {
            if (a>x){
                return countBetween(pos->right, a,b,0,1);
            } else if (a==x){
                return pos->right->baka+(pos->count);
            } else {
                return pos->right->baka+(pos->count)+countBetween(pos->left, a,b,0,1);
            }
        }
    } else {
        if (x>=a && x<=b){
            int res = pos->count;
            if (a<x){
                res+=countBetween(pos->left, a,b,0,1);
            } 
            if (b>x){
                res+=countBetween(pos->right, a,b,1,0);
            }
            return res;
        } else {
            if (b<x){
                pos = pos->left;
                goto back;
//                return countBetween(pos->left, a,b,0,0);
            } else {
                pos = pos->right;
                goto back;
  //              return countBetween(pos->right,a ,b,0,0);
            }
        }        
    }
}
void buang(Node* pos, int x){
    pos->baka--;
    
    if (pos->x==x){
        pos->count--;     
    } else if (pos->x>x){
        buang(pos->left, x);
    } else {
        buang(pos->right,x);
    }
}
void bantai(Node* lala){
    if (lala!=NULL){
        bantai(lala->left);
        bantai(lala->right);
        delete(lala);
    }
}

int main(){
    int ntc;
    scanf("%d", &ntc);
    for (int ttc=1;ttc<=ntc;ttc++){
        upc = 0;
        long long a,b,x,m; int n;
        scanf("%I64d%I64d%I64d%I64d%d", &a,&b,&x,&m,&n);
        memset(delt,0,sizeof(delt));
        memset(isi,0,sizeof(isi));
        int initn = n;
//        vector<int> delrows;
        // init
        x%=m;
        set<pair<int,int> > coldata[6];

        int q;
        scanf("%d", &q);

        Node* roots[10];
        memset(roots, 0, sizeof(roots));
        
        vector<int> que[6];
        
        for (int i=1;i<=n;i++){
            for (int j=1;j<=5;j++){
                isi[i][j]=((a*isi[i-1][j])%m+(b*isi[i][j-1])%m+x)%m;
                coldata[j].insert(make_pair(isi[i][j], i));
                
                que[j].push_back(isi[i][j]);                 
            }
        }
        for (int i=1;i<=5;i++)
            random_shuffle(que[i].begin(), que[i].end());
        
        for (int i=0;i<n;i++){
            for (int j=1;j<=5;j++){
                if (!roots[j]){
                    roots[j] = make_Node(que[j][i]);
                } else {
                    insert(roots[j], que[j][i]);
                }     
            }
        }        
                
        printf("Case #%d:\n", ttc);
        
        
        
        for (int i=0;i<q;i++){
            scanf("%s", buffer);
            if (!strcmp(buffer, "insert")){
                n++;                
                int p,q,r,s,t;
                scanf("%d%d%d%d%d", &p,&q,&r,&s,&t);
                isi[n][1]=p;
                isi[n][2]=q;
                isi[n][3]=r;
                isi[n][4]=s;
                isi[n][5]=t;
                coldata[1].insert(make_pair(p,n));
                coldata[2].insert(make_pair(q,n));
                coldata[3].insert(make_pair(r,n));
                coldata[4].insert(make_pair(s,n));
                coldata[5].insert(make_pair(t,n));
                
                if (!roots[1]){
                    roots[1] = make_Node(p);
                } else {
                    insert(roots[1], p);
                }      
                if (!roots[2]){
                    roots[2] = make_Node(q);
                } else {
                    insert(roots[2], q);
                }      
                if (!roots[3]){
                    roots[3] = make_Node(r);
                } else {
                    insert(roots[3], r);
                }      
                if (!roots[4]){
                    roots[4] = make_Node(s);
                } else {
                    insert(roots[4], s);
                }      
                if (!roots[5]){
                    roots[5] = make_Node(t);
                } else {
                    insert(roots[5], t);
                }      
            } else if (!strcmp(buffer, "remove")){
                int ln;
                scanf("%d" , &ln);
                if (ln<=n)
                if (!delt[ln]){
                    delt[ln]=1;
                    for (int i=1;i<=5;i++){
                        buang(roots[i], isi[ln][i]);
                        coldata[i].erase(make_pair(isi[ln][i],ln));
                    }
                }
            } else if (!strcmp(buffer, "max")){
                int cn;
                scanf("%d", &cn);
                set<pair<int,int> >::reverse_iterator it = coldata[cn].rbegin();
                /*
                while (delt[(*it).second]){
                    it++;
                }*/
                printf("%d\n", (*it).first);
            } else if (!strcmp(buffer, "min")){
                int cn;
                scanf("%d", &cn);
                set<pair<int,int> >::iterator it = coldata[cn].begin();
                /*
                while (delt[(*it).second]){
                    it++;
                }*/
                printf("%d\n", (*it).first);
                
            } else {
                // range   
                int cn,a,b;
                scanf("%d%d%d",&cn, &a,&b);
                if (a>b) swap(a,b);
                int res = countBetween(roots[cn], a,b,0,0);
                /*
                for (int d=0;d<delrows.size();d++){
                    int rn = delrows[d];
                    int data = isi[rn][cn];
                    if (data>=a && data<=b) res--;
                }*/
                
                printf("%d\n",res);                                             
            }
        }/*
        bantai(roots[1]);
        bantai(roots[2]);
        bantai(roots[3]);
        bantai(roots[4]);
        bantai(roots[5]);*/
    }
    
    return 0;
}