思想：
每次开点的时候：左右孩子都开辟新空间
注意懒惰标记tag: 因为会向下传递
提前在值中减去懒惰标记，避免重复计算
链接：https://www.nowcoder.com/acm/contest/121/H
来源：牛客网
乐于助人，善于团结，吃苦耐劳，平易近人，尊敬师长，团结同学，心地善良，为人诚实，一心一意，精明能干，个性稳重······的ddjing，为了柯怡着想，非常善良诚恳地向她提出一个很有建设性的建议————她该减肥了！
柯怡听了之后非常不高兴！她坚定的认为自己是微胖（连233斤都没有怎么能叫胖！）！而微胖才是最受欢迎的！并且做出了一个人神公愤的决定！她居然想要以此为借口欺负ddjing！
委屈的ddjing生气了！所以ddjing决定对柯怡降下天罚！这把柯怡吓得到处乱跑！
然而柯怡也不能坐以待毙，她知道每次天罚的时候ddjing会在[l,r]之间劈下x道闪电，而她当时会站在某个位置，由于她的身躯过于肥胖，她会占据[keyiL,keyiR]这段区间（为什么柯怡的体型会不同呢？因为柯怡逃跑的时候可能消耗掉一些脂肪，体型就会减少，而当她跑累的时候她又会去吃吃吃，体型就又会变大）；
忙于逃跑的柯怡实在没办法算的过来，因为零食早已塞满了她的大脑，所以她决定求助于你；
她想知道，在ddjing降下这次天罚之后，她现在所处的位置已经被闪电劈过多少次了？（这方便她去估算下一次逃跑的方向）
ddjing也猜测到了柯怡想预判他的天罚位置，所以他决定对他的天罚情报进行加密；
聪明的ddjing知道上一次柯怡所处的位置已经被res道闪电劈过了，并且他成功入侵了柯怡与你进行py交易的app，所以他会把数据篡改了；
幸好聪明的你发现了还原数据的方法；
因为ddjing十分坚持不懈，所以他一共向柯怡提了T次减肥建议；
每次提完减肥建议的时候，生气的ddjing会降下n次天罚；
每次天罚的时候，你会收到柯怡发过来的，包括l,r,x,keyiL,keyiR，其中l,r,keyiL,keyiR都是被ddjing篡改过的（不包括xi），而还原数据的方法是将这些被篡改过的数据按位异或(xor)上（res %19980105)，而你需要告诉柯怡，在ddjing这次天罚降下以后，她所处于的位置已经被闪电劈过多少次了；
输入描述:
一共有T(T<=10)组数据，对于每组数据，第一行有一个整数n，代表ddjing降下的天罚次数，接下来会有n（n<=100000)行，每一行有5个整数，分别为l,r,keyiL,keyiR (0<=l,r,keyiL,keyiR<=1000000000,1<=x<=5000);
其中，i是从1开始计数的，而res=0；
输出描述:
对于每次天罚，你需要输出一个整数，代表柯怡在这次天罚之后，她所处于的位置已经被闪电劈了多少次了；
输入例子:
1
4
1 3 5 2 4
2 3 1 1 1
150 250 8 2 4
1 2 3 4 5
输出例子:
10
0
10
0
-->
输入
1
4
1 3 5 2 4
2 3 1 1 1
150 250 8 2 4
1 2 3 4 5
输出
10
0
10
0
说明
对于第1次天罚,res0 = 0,l^(0%19980105)=1，r^(0%19980105)=3,keyiL^(0%19980105)=2,keyiR^(0%19980105)=4，在这次天罚后，柯怡所在的位置中的[2,3]分别被闪电劈过了5次，所以res=10;
对于第2次天罚，res =10,l^(10%19980105)=8，r^(10%19980105)=9，keyiL^(10%19980105)=11，keyiR^(10%19980105)= 11，所以res=0；
对于第三次天罚柯怡占据了[2,4]，[2,3]在第一次天罚中已经被劈过了，所以res =10；
对于第四次天罚，res=10，l ^(10%19980105)=11，r^(10%19980105)=8，所以ddjing降下天罚的范围是[8,11]；
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct node {
LL sum;
LL lson;
LL rson;
LL tag;
};
const int N=4e6+;// 点要开20~40倍
const LL X=1e9;
const LL p=;
node tree[N];
int n,cnt;
void newnode (LL &rt,LL x) {
rt=++cnt;
tree[rt].sum=x;
tree[rt].lson=tree[rt].rson=-;
tree[rt].tag=;
}
void pushdown (LL rt,LL l,LL r) {
LL m=(l+r)/;
if (tree[rt].tag) {
tree[tree[rt].lson].sum+=tree[rt].tag*(m-l+);
tree[tree[rt].lson].tag+=tree[rt].tag;
tree[tree[rt].rson].sum+=tree[rt].tag*(r-m);
tree[tree[rt].rson].tag+=tree[rt].tag;
tree[rt].tag=;
}
}
void pushup (LL rt) {
tree[rt].sum=tree[t ree[rt].lson].sum+tree[tree[rt].rson].sum;
}
void update (LL L,LL R,LL x,LL l,LL r,LL rt) {
if (l>R||r<L) return ;
if (l>=L&&r<=R) {
tree[rt].sum+=(r-l+)*x;
tree[rt].tag+=x;
return ;
}
LL m=(l+r)/; LL k=tree[rt].sum/(r-l+)-tree[rt].tag;// 提前减去tag
if (tree[rt].lson<) newnode (tree[rt].lson,k*(m-l+));
if (tree[rt].rson<) newnode (tree[rt].rson,k*(r-m));
pushdown(rt,l,r);// 因为这里会自动加上tag
update (L,R,x,l,m,tree[rt].lson);
update (L,R,x,m+,r,tree[rt].rson);
pushup(rt);
return ;
}
LL query (LL L,LL R,LL l,LL r,LL rt) {
if (l>R||r<L) return ;
if (l>=L&&r<=R) return tree[rt].sum;
LL m=(l+r)/; LL k=tree[rt].sum/(r-l+)-tree[rt].tag;
if (tree[rt].lson<) newnode (tree[rt].lson,k*(m-l+));
if (tree[rt].rson<) newnode (tree[rt].rson,k*(r-m));
pushdown(rt,l,r);
return query (L,R,l,m,tree[rt].lson)+query (L,R,m+,r,tree[rt].rson);
}
int main ()
{
int T; scanf ("%d",&T);
while (T--) {
cnt=;
LL res=,rt=++cnt;
tree[rt].sum=tree[rt].tag=;
tree[rt].lson=tree[rt].rson=-;
scanf ("%d",&n);
for (int i=;i<=n;i++) {
LL l,r,x,kl,kr;
scanf ("%lld %lld %lld %lld %lld",&l,&r,&x,&kl,&kr);
l=l^res; r=r^res; kl=kl^res; kr=kr^res;
if (l>r) swap(l,r); if (kl>kr) swap(kl,kr);
update (l,r,x,,X,rt);
res=query (kl,kr,,X,rt);
printf("%lld\n",res);
res%=p;
}
}
return ;
}