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=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+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==0) return x%2; if(p==1) { if(x%4==0) return 0; if(x%2==0) return 1; if(x%4==1) return 0; if(x%4==3) return 1; } x=x%(1<<p); if(x==0) return (1<<(p-1))%2; return max(0,x-(1<<(p-1)))%2; } ll clac(int l,int r){ ll ret=0; l=(l+l+1)/2+1; r=(r+r-1)/2+1; if(l>r) return 0; for(ll i=30;i>=0;--i){ ret+=(pre(r,i)-pre(l-1,i)+2+2+2)%2*(1<<i); } return ret; } void dele(int typ){ if(typ==0){//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==1){//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-1){ L=min(L,(*it).l); R=max(R,(*it).r); dele(0); //fl=true; it=s.lower_bound(po(l,r)); }else{ dele(2); } } while(1){ it=s.lower_bound(po(l,r)); if(it==s.end()) break; if((*it).l>r) break; R=max(R,(*it).r); dele(1); } 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==1){ rd(l);rd(r); ins(l,r); }else{ printf("%lld ",ans); } } return 0; } } signed main(){ // freopen("data.in","r",stdin); // freopen("my.out","w",stdout); Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/1/16 9:17:43 */