求助大佬,注释里的代码只可以过 7−12 号点和 21 号点。其它WA,改成现在这样(也就是题解普遍写法)就好了
,我原来这种写法应该怎么改进才能过呀
...
int copynode(int k);
struct Tree
{
int ls,rs;
int key,val,sz,sum;
bool lazy;
void push()
{
ls = copynode(ls);
rs = copynode(rs);
ls ^= rs ^= ls ^= rs;
lazy ^= 1;
}
}tr[N * 20];
int idx;
#define lson(k) tr[k].ls
#define rson(k) tr[k].rs
int newnode(int val)
{
tr[++idx].val = val;
tr[idx].key = rnd();
tr[idx].sz = 1;
tr[idx].sum = val;
return idx;
}
int copynode(int k)
{
if(!k)
return 0;
tr[++idx] = tr[k];
return idx;
}
void pushup(int k)
{
tr[k].sz = tr[lson(k)].sz + tr[rson(k)].sz + 1;
tr[k].sum = tr[lson(k)].sum + tr[rson(k)].sum + tr[k].val;
}
void pushdown(int k)
{
if(tr[k].lazy)
{
tr[k].lazy = 0;
lson(k) = copynode(lson(k)); //tr[lson(k)].push();
rson(k) = copynode(rson(k)); //tr[rson(k)].push();
std::swap(lson(k),rson(k)); //
tr[lson(k)].lazy ^= 1; //
tr[rson(k)].lazy ^= 1; //
}
}
void split(int k,int sz,int &x,int &y)
{
if(!k)
x = y = 0;
else
{
pushdown(k);
if(tr[lson(k)].sz < sz)
{
x = copynode(k);
split(rson(x),sz - tr[lson(k)].sz - 1,rson(x),y);
pushup(x);
}
else
{
y = copynode(k);
split(lson(y),sz,x,lson(y));
pushup(y);
}
}
}
int merge(int x,int y)
{
if(!x || !y)
return x | y;
if(tr[x].key < tr[y].key)
{
pushdown(x);
rson(x) = merge(rson(x),y);
pushup(x);
return x;
}
else
{
pushdown(y);
lson(y) = merge(x,lson(y));
pushup(y);
return y;
}
}
int root[N];
signed main()
{
scanf("%lld",&n);
int lastans = 0;
int t1 = 0,t2 = 0,t3 = 0;
for(int i = 1,id,op,x,y;i <= n;i++)
{
scanf("%lld%lld%lld",&id,&op,&x);
if(op != 2)
scanf("%lld",&y);
x ^= lastans,y ^= lastans;
if(op == 1)
{
split(root[id],x,t1,t2);
root[i] = merge(merge(t1,newnode(y)),t2);
}
else if(op == 2)
{
split(root[id],x,t1,t3);
split(t1,x - 1,t1,t2);
root[i] = merge(t1,t3);
}
else if(op == 3)
{
split(root[id],y,t1,t3);
split(t1,x - 1,t1,t2);
tr[t2].lazy ^= 1; // tr[t2].push();
root[i] = merge(merge(t1,t2),t3);
}
else if(op == 4)
{
split(root[id],y,t1,t3);
split(t1,x - 1,t1,t2);
printf("%lld\n",tr[t2].sum);
lastans = tr[t2].sum;
root[i] = merge(merge(t1,t2),t3);
}
}
return 0;
}
不尽感激