疑问+警示后人

代码60pts 错因为wa和tle

但将qian函数和hou函数的返回值调大2倍 即可ac 猜测为死循环但不理解为什么

#include<bits/stdc++.h>
using namespace std;
int in(){
    int ans = 0, f = 1;
    char c = getchar();
    while(c < '0' || '9' < c){
        if(c == '-') f = -1;
        c = getchar();
    }
    do{
        ans = ans * 10 + c - '0';
        c = getchar();
    }while('0' <= c && c <= '9');
    return ans * f;
}
void out(int x){
    if(x < 0){
        x = -x;
        putchar('-');
    }
    if(x >= 10) out(x / 10);
    putchar(x % 10 + '0');
}
struct node{
    int ls, rs;
    int sum, lazy, size, p;
}a[19198010];
int cnt;
void zuo(int &root){
    int u = a[root].rs;
    int v = a[u].ls;
    a[root].rs = v;
    a[u].ls = root;
    a[u].size = a[root].size;
    a[root].size = a[a[root].ls].size + a[v].size + a[root].lazy;
    root = u;
}
void you(int &root){
    int u = a[root].ls;
    int v = a[u].rs;
    a[root].ls = v;
    a[u].rs = root;
    a[u].size = a[root].size;
    a[root].size = a[a[root].rs].size + a[v].size + a[root].lazy;
    root = u;
}
void add(int &root, int key){
    if(root == 0){
        root = ++cnt;
        a[root].sum = key;
        a[root].size = a[root].lazy = 1;
        a[root].ls = a[root].rs = 0;
        a[root].p = rand();
        return;
    }
    a[root].size++;
    if(a[root].sum == key){
        a[root].lazy++;
        return;
    }
    if(a[root].sum < key){
        add(a[root].rs, key);
        if(a[a[root].rs].p < a[root].p)zuo(root);
        return;
    }
    else {
        add(a[root].ls, key);
        if(a[a[root].ls].p < a[root].p)you(root);
        return;
    }
}
void cut(int &root, int key){
    if(a[root].sum == key){
        if(a[root].lazy > 1){
            a[root].size--;
            a[root].lazy--;
        }
        else if(a[root].ls == 0 || a[root].rs == 0)root = a[root].ls + a[root].rs;
        else if(a[a[root].ls].p < a[a[root].rs].p){
            you(root);
            cut(a[root].rs, key);
            a[root].size--;
        }
        else {
            zuo(root);
            cut(a[root].ls, key);
            a[root].size--;
        }
        return;
    }
    a[root].size--;
    if(key < a[root].sum)cut(a[root].ls, key);
    else cut(a[root].rs, key);
}
int num(int root, int key){
    if(root == 0)return 1;
    if(a[root].sum == key)return a[a[root].ls].size + 1;
    if(a[root].sum > key)return num(a[root].ls, key);
    else return a[a[root].ls].size + a[root].lazy + num(a[root].rs, key);

}
int number(int root, int key){
    int s = a[a[root].ls].size;
    if(s < key && key <= s + a[root].lazy)return a[root].sum;
    else if(key <= s)return number(a[root].ls, key);
    else return number(a[root].rs, key - s - a[root].lazy);
}
int qian(int root, int key){
    if(root == 0)return -(1000000000);
    if(a[root].sum >= key)return qian(a[root].ls, key);
    else return max(a[root].sum, qian(a[root].rs, key));
}
int hou(int root, int key){
    if(root == 0)return 1000000000;
    if(a[root].sum <= key)return hou(a[root].rs, key);
    else return min(a[root].sum, hou(a[root].ls, key));
}
int n, op, x, root = 0, ans, m, sum;
int main(){
//  freopen("P6136_15.in", "r", stdin);
    a[root].ls = a[root].rs = 0;
    n = in();m = in();
    for(int i = 1;i <= n;i++){
        add(root, in());
    }
    for(int i = 1;i <= m;i++){
        op = in(), x = in();
        if(op == 1)add(root, x ^ sum);
        if(op == 2)cut(root, x ^ sum);
        if(op == 3)sum = num(root, x ^ sum), ans ^= sum;
        if(op == 4)sum = number(root, x ^ sum), ans ^= sum;
        if(op == 5)sum = qian(root, x ^ sum), ans ^= sum;
        if(op == 6)sum = hou(root, x ^ sum), ans ^= sum;
//      out(i);
//      putchar('\n');
    }
    out(ans);
}