@[ZSH_ZSH](/user/287850) 你看题了没
by zhoukangyang @ 2020-07-03 18:05:39
建议您的split里用else语句
by zhoukangyang @ 2020-07-03 18:18:14
~~我看不出来错,您看我的代码吧~~
```
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,opt,us,spa,splx,sply,splz,root,las,cr;
struct node {
int son[2],siz,val,key;
} q[2000009];
void upd(int x) {q[x].siz=q[q[x].son[0]].siz+q[q[x].son[1]].siz+1;}
int new_root(int value) {++n,q[n].siz=1,q[n].val=value,q[n].key=rand();return n;}
int merge(int x,int y) { //x < y
if(!x||!y) return x+y;
if(q[x].key<q[y].key) {
q[x].son[1]=merge(q[x].son[1],y),upd(x);
return x;
}
else {
q[y].son[0]=merge(x,q[y].son[0]),upd(y);
return y;
}
}
void split(int now,int k,int &x,int &y) {
if(!now) x=y=0;
else {
if(q[now].val<=k) x=now,split(q[now].son[1],k,q[now].son[1],y);
else y=now,split(q[now].son[0],k,x,q[now].son[0]);
upd(now);
}
}
int kth(int now,int k) {
while(1) {
if(k<=q[q[now].son[0]].siz) now=q[now].son[0];
else if(k==q[q[now].son[0]].siz+1) return q[now].val;
else k-=q[q[now].son[0]].siz+1,now=q[now].son[1];
}
}
signed main() {
srand(1919810);
scanf("%d%d",&us,&m);
while(us--) scanf("%d",&cr),split(root,cr,splx,sply),root=merge(merge(splx,new_root(cr)),sply),cr=0;
while(m--) {
scanf("%d%d",&opt,&us),us^=las;
if(opt==1) split(root,us,splx,sply),root=merge(merge(splx,new_root(us)),sply);
if(opt==2) split(root,us,splx,sply),split(splx,us-1,splx,splz),splz=merge(q[splz].son[0],q[splz].son[1]),root=merge(merge(splx,splz),sply);
if(opt==3) split(root,us-1,splx,sply),las=q[splx].siz+1,root=merge(splx,sply),cr^=las;
if(opt==4) las=kth(root,us),cr^=las;
if(opt==5) split(root,us-1,splx,sply),las=kth(splx,q[splx].siz),root=merge(splx,sply),cr^=las;
if(opt==6) split(root,us,splx,sply),las=kth(sply,1),root=merge(splx,sply),cr^=las;
}
printf("%d\n",cr);
return 0;
}
```
by zhoukangyang @ 2020-07-03 18:18:43
~~我看不出来错,您看我的代码吧~~
```cpp
#include <cstdio>
#include <cstdlib>
#define ll long long
#define re register
#define il inline
#define gc getchar
#define pc putchar
template <class T>
void read(T &x) {
re bool f = 0;
re char c = gc();
while ((c < '0' || c > '9') && c != '-') c = gc();
if (c == '-') f = 1, c = gc();
x = 0;
while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = gc();
f && (x = -x);
}
template <class T>
void print(T x) {
if (x < 0) pc('-'), x = -x;
if (x >= 10) print(x / 10);
pc((x % 10) ^ 48);
}
#define priln(x) do{print(x);pc('\n');}while(0)
#define prisp(x) do{print(x);pc(' ');}while(0)
const int N = 100005, S = N * 40;
int nc, ch[S][2], val[S], pri[S], siz[S];
il int newd(int x) {
val[++nc] = x;
ch[nc][0] = ch[nc][1] = 0;
pri[nc] = rand();
siz[nc] = 1;
return nc;
}
il void upd(int x) {
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
void split(int x, int k, int &a, int &b) {
if (!x) {a = b = 0; return;}
if (k < val[x]) {
split(ch[x][0], k, a, ch[x][0]);
b = x;
upd(b);
} else {
split(ch[x][1], k, ch[x][1], b);
a = x;
upd(a);
}
}
int merge(int a, int b) {
if (!a || !b) return a | b;
if (pri[a] < pri[b]) {
ch[a][1] = merge(ch[a][1], b);
upd(a);
return a;
} else {
ch[b][0] = merge(a, ch[b][0]);
upd(b);
return b;
}
}
int kth(int x, int k) {
if (k == siz[ch[x][0]] + 1) return val[x];
if (k < siz[ch[x][0]] + 1) return kth(ch[x][0], k);
else return kth(ch[x][1], k - siz[ch[x][0]] - 1);
}
int n, m, root;
int main() {
read(n);
read(m);
for (re int i = 1; i <= n; ++i)
{
re int x, a, b;
read(x);
split(root, x, a, b);
root = merge(a, merge(newd(x), b));
}
re int la = 0, ans = 0;
while (m--) {
re int opt, x;
read(opt);
read(x);
x ^= la;
if (opt == 1) {
re int a, b;
split(root, x, a, b);
root = merge(a, merge(newd(x), b));
} else if (opt == 2){
re int a, b, c;
split(root, x, b, c);
split(b, x - 1, a, b);
b = merge(ch[b][0], ch[b][1]);
root = merge(a, merge(b, c));
} else if (opt == 3) {
re int a, b;
split(root, x - 1, a, b);
la = siz[a] + 1;
ans ^= la;
root = merge(a, b);
} else if (opt == 4) {
la = kth(root, x);
ans ^= la;
} else if (opt == 5) {
re int a, b;
split(root, x - 1, a, b);
la = kth(a, siz[a]);
ans ^= la;
root = merge(a, b);
} else if (opt == 6) {
re int a, b;
split(root, x, a, b);
la = kth(b, 1);
ans ^= la;
root = merge(a, b);
}
}
priln(ans);
}
```
by water_lift @ 2020-07-03 18:19:47
您的cnt是不是重名了?
by pikabi @ 2020-07-03 18:27:28
~~查不出来,看我的代码~~
```cpp
#include <bits/stdc++.h>
#define SZ(x) (x?x->sz:0)
using namespace std;
const int N=1100010;
struct Node{
int sz,rk,dat;
Node *lson,*rson;
void update() {
sz=SZ(lson)+SZ(rson)+1;
}
};
int n,m,cnt,lastans,ans;
Node pool[N<<1];
Node *rt;
inline int read() {
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)) {
if (c == '-') f = -1;
c = getchar();
}
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
void split(Node *p,Node *&pl, Node *&pr, int x){
if(!p){pl=pr=NULL;return;}
if(p->dat<=x){
pl=p;split(p->rson,pl->rson,pr,x);
pl->update();
}else{
pr=p;split(p->lson,pl,pr->lson,x);
pr->update();
}
}
void merge(Node*& p,Node* pl,Node* pr){
if(!pl||!pr){p=pl?pl:pr;return;}
if(pl->rk<pr->rk){
p=pl;merge(p->rson,pl->rson,pr);
}else{
p=pr;merge(p->lson,pl,pr->lson);
}
p->update();
}
Node *newNode(int x){
Node* newN=pool+(++cnt);
newN->dat=x;
newN->rk=rand();
newN->sz=1;
return newN;
}void insert(Node*& rt,int x){
Node *l,*r;
split(rt,l,r,x-1);
merge(rt,l,newNode(x));
merge(rt,rt,r);
}void del(Node*& rt,int x){
Node *p1,*p2,*p3,*p4;
split(rt,p1,p2,x-1);
split(p2,p3,p4,x);
merge(p3,p3->lson,p3->rson);
merge(p3,p3,p4);
merge(rt,p1,p3);
}int getRk(Node*& rt,int x){
Node *l,*r;
split(rt,l,r,x-1);
int ans=SZ(l)+1;
merge(rt,l,r);
return ans;
}int kth(Node *cur,int k){
while(cur){
if(SZ(cur->lson)>=k){
cur=cur->lson;
}else if(k>SZ(cur->lson)+1){
k-=SZ(cur->lson)+1;cur=cur->rson;
}else{
return cur->dat;
}
}
return 0;
}int pre(Node *cur,int x){
int ans=INT_MIN;
while(cur){
if(x>cur->dat){
ans=max(ans,cur->dat);
cur=cur->rson;
}else{
cur=cur->lson;
}
}
return ans;
}int succ(Node *cur,int x){
int ans=INT_MAX;
while (cur){
if(x<cur->dat){
ans=min(ans,cur->dat);
cur=cur->lson;
}else{
cur=cur->rson;
}
}
return ans;
}
signed main() {
srand(time(0));
n=read(),m=read();
for(int i=1;i<=n;i++){
int x=read();insert(rt,x);
}
while(m--){
int opt=read(),x=read();
x^=lastans;
// printf("LOGOUT: %d %d\n", opt, x);
if(opt==1){
insert(rt,x);
}else if(opt==2){
del(rt,x);
}else if(opt==3){
lastans=getRk(rt,x);ans^=lastans;
}else if(opt==4){
lastans=kth(rt,x);ans^=lastans;
}else if(opt==5){
lastans=pre(rt,x);ans^=lastans;
}else{
lastans=succ(rt,x);ans^=lastans;
}
}
printf("%d\n",ans);
return 0;
}
```
by SamariumPhosphide @ 2020-07-03 19:03:21
看不出来错,顺手膜拜
by syksykCCC @ 2020-07-03 19:15:38
~~不是怎么都发代码了呀呀呀~~
by Rubidium_Chloride @ 2020-07-03 19:16:30
一个zz地方写错了,此贴终结
by 小蒟蒻皮皮鱼 @ 2020-07-03 19:25:30
```cpp
split(rt, k - 1, x, z);
```
by 小蒟蒻皮皮鱼 @ 2020-07-03 19:25:55