WhileTrueRP @ 2023-11-17 16:26:24
rt,疑似是操作3出错
by WhileTrueRP @ 2023-11-17 16:26:54
样例输出 8
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+1e5+5;
const int INF = 0x3f3f3f3f;
int tot = 0,root;
struct treap{
int val,dat;
int l,r;
int cnt,size;
}a[N];
int New(int val){
a[++tot].val = val;
a[tot].dat = rand();
a[tot].size = 1;
a[tot].cnt = 1;
return tot;
}
void update(int p){
a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}
void zig(int &p){
int q = a[p].l;
a[p].l = a[q].r;
a[q].r = p;
p = q;
update(a[p].r);
update(p);
}
void zag(int &p){
int q = a[p].r;
a[p].r = a[q].l;
a[q].l = p;
p = q;
update(a[p].r);
update(p);
}
void Build(){
New(-INF);
New(INF);
a[1].r = 2;
root = 1;
update(root);
}
int getRank(int p,int val){
if(p == 0){
return 0;
}else if(a[p].val == val){
return a[a[p].l].size;
}else if(a[p].val > val){
return getRank(a[p].l,val);
}else{
return getRank(a[p].r,val) + a[a[p].l].size + a[p].cnt;
}
}
int getVal(int p,int rank){
if(p == 0){
return INF;
}
if(a[a[p].l].size >= rank){
return getVal(a[p].l,rank);
}else if(a[a[p].l].size + a[p].cnt >= rank){
return a[p].val;
}else{
return getVal(a[p].r,rank-a[a[p].l].size-a[p].cnt);
}
}
void insert(int &p,int val){
if(p == 0){
p = New(val);
return;
}else if(val == a[p].val){
a[p].cnt ++;
}else if(val < a[p].val){
insert(a[p].l,val);
if(a[p].dat < a[a[p].l].dat){
zig(p);
}
}else{
insert(a[p].r,val);
if(a[p].dat < a[a[p].r].dat){
zag(p);
}
}
update(p);
}
int getpre(int val){
int ans = 1;
int p = root;
while(p){
if(a[p].val == val){
if(a[p].l > 0){
p = a[p].l;
while(a[p].r > 0){
p = a[p].r;
}
ans = p;
}
break;
}
if(a[ans].val < a[p].val && a[p].val < val){
ans = p;
}
if(val < a[p].val){
p = a[p].l;
}else{
p = a[p].r;
}
}
return a[ans].val;
}
int getnxt(int val){
int ans = 2;
int p = root;
while(p){
if(a[p].val == val){
if(a[p].r > 0){
p = a[p].r;
while(a[p].l > 0){
p = a[p].l;
}
ans = p;
}
break;
}
if(a[ans].val > a[p].val && a[p].val > val){
ans = p;
}
if(val < a[p].val){
p = a[p].l;
}else{
p = a[p].r;
}
}
return a[ans].val;
}
void Remove(int p,int val){
if(a[p].val == val){
if(a[p].cnt > 1){
a[p].cnt --;
}else if(a[p].l || a[p].r){
if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat){
zig(p);
Remove(a[p].r,val);
}else{
zag(p);
Remove(a[p].l,val);
}
}else{
p = 0;
}
}else if(val < a[p].val){
Remove(a[p].l,val);
}else{
Remove(a[p].r,val);
}
update(p);
}
int main(){
srand(time(0));
Build();
int n,m,x,last = 0,ans = 0,opt;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x);
insert(root,x);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&opt,&x);
switch(opt){
case 1:
insert(root,x^last);
break;
case 2:
Remove(root,x^last);
break;
case 3:
last = getRank(root,x^last);
ans ^= last;
break;
case 4:
last = getVal(root,x^last);
ans ^= last;
break;
case 5:
last = getpre(x^last);
ans ^= last;
break;
case 6:
last = getnxt(x^last);
ans ^= last;
break;
}
}
printf("%d",ans);
}by xyYyx @ 2023-11-17 19:03:08
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1.1e6+5;
const ll INF = 1e17;
int tot = 0,root;
struct treap{
ll val,dat;
int l,r;
int cnt,size;
}a[N];
int New(ll val){
a[++tot].val = val;
a[tot].dat = rand();
a[tot].size = 1;
a[tot].cnt = 1;
return tot;
}
void update(int p){
a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}
void zig(int &p){
int q = a[p].l;
a[p].l = a[q].r;
a[q].r = p;
p = q;
update(a[p].r);
update(p);
}
void zag(int &p){
int q = a[p].r;
a[p].r = a[q].l;
a[q].l = p;
p = q;
update(a[p].l);//
update(p);
}
void Build(){
New(-INF);
New(INF);
a[1].r = 2;
root = 1;
update(root);
if(a[2].dat>a[1].dat) zag(root);//
}
ll getRank(int p,ll val){
if(p == 0){
return 0;
}else if(a[p].val == val){
return a[a[p].l].size;
}else if(a[p].val > val){
return getRank(a[p].l,val);
}else{
return getRank(a[p].r,val) + a[a[p].l].size + a[p].cnt;
}
}
ll getVal(int p,ll rank){
if(p == 0){
return INF;
}
if(a[a[p].l].size >= rank){
return getVal(a[p].l,rank);
}else if(a[a[p].l].size + a[p].cnt >= rank){
return a[p].val;
}
int res=getVal(a[p].r,rank-a[a[p].l].size-a[p].cnt);
return res;
}
void insert(int &p,ll val){
if(p == 0){
p = New(val);
return;
}else if(val == a[p].val){
a[p].cnt ++;
}else if(val < a[p].val){
insert(a[p].l,val);
if(a[p].dat < a[a[p].l].dat){
zig(p);
}
}else{
insert(a[p].r,val);
if(a[p].dat < a[a[p].r].dat){
zag(p);
}
}
update(p);
}
ll getpre(ll val){
int ans = 1;
int p = root;
while(p){
if(a[p].val == val){
if(a[p].l > 0){
p = a[p].l;
while(a[p].r > 0){
p = a[p].r;
}
ans = p;
}
break;
}
if(a[ans].val < a[p].val && a[p].val < val){
ans = p;
}
if(val < a[p].val){
p = a[p].l;
}else{
p = a[p].r;
}
}
return a[ans].val;
}
ll getnxt(ll val){
int ans = 2;
int p = root;
while(p){
if(a[p].val == val){
if(a[p].r > 0){
p = a[p].r;
while(a[p].l > 0){
p = a[p].l;
}
ans = p;
}
break;
}
if(a[ans].val > a[p].val && a[p].val > val){
ans = p;
}
if(val < a[p].val){
p = a[p].l;
}else{
p = a[p].r;
}
}
return a[ans].val;
}
void Remove(int &p,ll val){//
if(a[p].val == val){
if(a[p].cnt > 1){
a[p].cnt --;
}else if(a[p].l || a[p].r){
if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat){
zig(p);
Remove(a[p].r,val);
}else{
zag(p);
Remove(a[p].l,val);
}
}else{
p = 0;
}
}else if(val < a[p].val){
Remove(a[p].l,val);
}else{
Remove(a[p].r,val);
}
update(p);
}
int main(){
srand(time(0));
Build();
int n,m,opt;
ll x,ans=0,last=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&x);
insert(root,x);
}
for(int i=1;i<=m;i++){
scanf("%d%lld",&opt,&x);
switch(opt){
case 1:
insert(root,x^last);
break;
case 2:
Remove(root,x^last);
break;
case 3:
last = getRank(root,x^last);
ans ^= last;
break;
case 4:
last = getVal(root,(x^last)+1);
ans ^= last;
break;
case 5:
last = getpre(x^last);
ans ^= last;
break;
case 6:
last = getnxt(x^last);
ans ^= last;
break;
}
}
printf("%lld",ans);
return 0;
}修改之后的代码。除了行后打了"//"的代码修改了之外，开了long long，加大了INF。
by xyYyx @ 2023-11-17 19:25:31
哦，还有case4修改为 last = getVal(root,(x^last)+1);。因为您最开始创建了一个值为-INF的占位节点，所以之后求排名都要+1。