emm
可重集合没用用。直接变成不可重复集合
有若干个区间
每个区间形如[L,R]
[L,R]计算的话，就是若干个连续奇数的和。拆位统计1的个数
平衡树维护
加入一个[L,R]，把相交的区间合并。之后相邻不相交的部分O(1)计算贡献到答案里。
O(nlogn+30n)
写起来并不太好写
set就可以
删除一些区间，合并成大区间
要分类讨论
至于calc(l,r)
有O(1)公式，可以不用按位：
第一个第二个发现了，后面就是多余位置处理即可。
代码：
1.注意插入区间被包含的情况，删掉前驱，R还要取一个max
2.按位的话，最高的是1e9+1e9=2e9，是1<<30，不是29.。。
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
int q;
struct po{
ll l,r;
po(){}
po(int x,int y){
l=x;r=y;
}
bool friend operator <(po a,po b){
if(a.l!=b.l) return a.l<b.l;
return a.r<b.r;
}
};
set<po>s;
set<po>::iterator it,le,ri;
ll ans;
ll pre(int x,ll p){
if(p==) return x%;
if(p==) {
if(x%==) return ;
if(x%==) return ;
if(x%==) return ;
if(x%==) return ;
}
x=x%(<<p);
if(x==) return (<<(p-))%;
return max(,x-(<<(p-)))%;
}
ll clac(int l,int r){
ll ret=;
l=(l+l+)/+;
r=(r+r-)/+;
if(l>r) return ;
for(ll i=;i>=;--i){
ret+=(pre(r,i)-pre(l-,i)+++)%*(<<i);
}
return ret;
}
void dele(int typ){ if(typ==){//pre and bac and me
ll tmp=clac((*it).l,(*it).r);
ans^=tmp;
ri=it;
++ri;
if(ri!=s.end()){
ans^=((*ri).l)*((*ri).l)-((*it).r)*((*it).r);
}
le=it;
if(le!=s.begin()){
--le;
ans^=((*it).l)*((*it).l)-((*le).r)*((*le).r);
}
s.erase(it);
}
else if(typ==){//bac and me
ll tmp=clac((*it).l,(*it).r);
ans^=tmp;
ri=it;
++ri;
if(ri!=s.end()){
ans^=((*ri).l)*((*ri).l)-((*it).r)*((*it).r);
}
s.erase(it);
}else {//only bac
ri=it;
++ri;
if(ri!=s.end()){
ans^=((*ri).l)*((*ri).l)-((*it).r)*((*it).r);
}
}
}
void ins(int l,int r){
if(s.empty()){
ans^=clac(l,r);
s.insert(po(l,r));
}else{
it=s.lower_bound(po(l,r));
ll L=l,R=r;
//bool fl=false;
if(it!=s.begin()){
--it;
if((*it).r>=l-){
L=min(L,(*it).l);
R=max(R,(*it).r);
dele();
//fl=true;
it=s.lower_bound(po(l,r));
}else{
dele();
}
}
while(){
it=s.lower_bound(po(l,r));
if(it==s.end()) break;
if((*it).l>r) break;
R=max(R,(*it).r);
dele();
} if(it!=s.end()){
ans^=((*it).l)*((*it).l)-R*R;
}
if(it!=s.begin()){
--it;
ans^=L*L-((*it).r)*((*it).r);
}
ans^=clac(L,R);
s.insert(po(L,R));
}
}
int main(){
rd(q);
int op,l,r;
while(q--){
rd(op);
if(op==){
rd(l);rd(r);
ins(l,r);
}else{
printf("%lld\n",ans);
}
}
return ;
} }
signed main(){
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/1/16 9:17:43
*/