前言
考试的时候居然想错了区间贡献，mdzz
思路
题目看着很方啊，难道要树套树？
但数据范围提醒我们，是nlogn的复杂度
Sort(S)的定义是不是很鬼畜
但我们不动脑子的打表容易发现
连续区间[1，n]内\(a_i^2-a_{i-1}^2\)为连续的奇数
（其实这里直接用初中的完全平方公式就好）
我们再次打表又发现了
连续的奇数的异或和，很有规律的嘛
可以直接O（1）求出
int xx(int x) {
if(x%4==0) return 0;
if(x%4==2) return 2;
if(x%4==1) return x+x-1;
return x+x+1;
}
根据异或的性质(a^a=0)
我们就能计算出任意连续一段的ans了，\(xx(l-1)\)^\(xx(r)\)
虽说允许重复的集合S
但区间如果重叠，他也只计算一次答案，手玩一下很容易看出
也就是集合S还是不允许重复的(重复的删掉是不影响答案的)
合并直接算就好了
我们现在需要一个只需要支持区间更改贡献的数据结构
lsh+线段树真香
struct node {
int l,r,lazy;
int mi,ma,sum;
int full,k;
} e[maxn<<4];
/*
mi,ma维护区间[l,r]最小值
lazy懒惰标记
ok判断区间[l,r]是否全部被计算答案
k判断[mid,mid+1]之间是否连接
ans就是ans啦
*/
ps：可能我的线段树调试的时候打了太多补丁，肯定有比我写的好得多的代码
但也是不难理解的，重要部分我们加以注释
关于int，是会炸的，反正我的数据灰渣
另外提醒
千万别开小了数组,一组询问是两个数偶，我一直报WA
错误
主席树写多了，左右孩子和l,r老是搞混了，mdzz
代码
#include <bits/stdc++.h>
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=3e5+7;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int read() {
int x=0,f=1;char s=getchar();
for(; s>'9'||s<'0'; s=getchar()) if(s=='-') f=-1;
for(; s>='0'&&s<='9'; s=getchar()) x=x*10+s-'0';
return x*f;
}
ll xx(ll x) {
if(x%4==0) return 0;
if(x%4==2) return 2;
if(x%4==1) return x+x-1;
return x+x+1;
}
ll calc(ll l,ll r) {return xx(r)^xx(l-1);}
struct node {
int l,r;
ll mi,ma,sum;
bool full,k,lazy;
} e[maxn<<4];
int lsh[maxn<<1],len;
void pushup(int rt) {
if(e[rt].full) return;
if(e[rt].k) // 区间[mid,mid+1]贡献 需要计算
e[rt].sum=e[rt<<1].sum^e[rt<<1|1].sum^calc(lsh[e[rt<<1].r]+1,lsh[e[rt<<1|1].l]);
else if(e[rt<<1].ma==-inf||e[rt<<1|1].mi==inf) //只有一边有值
e[rt].sum=e[rt<<1].sum^e[rt<<1|1].sum;
else //暴力计算
e[rt].sum=e[rt<<1].sum^e[rt<<1|1].sum^(e[rt<<1|1].mi*e[rt<<1|1].mi-e[rt<<1].ma*e[rt<<1].ma);
e[rt].ma=max(e[rt<<1].ma,e[rt<<1|1].ma);
e[rt].mi=min(e[rt<<1].mi,e[rt<<1|1].mi);
}
void tag(int rt) {//区间全部计算ans
e[rt].sum=calc(lsh[e[rt].l]+1,lsh[e[rt].r]);
e[rt].full=1;
e[rt].mi=lsh[e[rt].l];
e[rt].ma=lsh[e[rt].r];
}
void pushdown(int rt) {
if(e[rt].lazy==0) return;
if(e[rt].lazy) {//显然
tag(rt<<1);tag(rt<<1|1);
e[rt<<1].lazy=e[rt<<1|1].lazy=1;
e[rt].lazy=0;
}
}
void build(int l,int r,int rt) {//显然
e[rt].l=l,e[rt].r=r;
e[rt].ma=-inf,e[rt].mi=inf;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
}
void modify(int L,int R,int rt) {
if(L<=e[rt].l&&e[rt].r<=R) {
tag(rt);
e[rt].lazy=1;
return;
}
if(e[rt].full) return;//如果计算过就不用在计算了
pushdown(rt);
int mid=(e[rt].l+e[rt].r)>>1;
if(L<=mid) modify(L,R,rt<<1);
if(R>mid) modify(L,R,rt<<1|1);
if(L<=mid&&R>mid) e[rt].k=1;//区间两边都经过，中间也一定经过，k=1
pushup(rt);
}
struct edge {int opt,x,y;} Q[maxn];//询问
main() {
//read and lsh
int n=read();
FOR(i,1,n) {
Q[i].opt=read();
if(Q[i].opt==1) lsh[++len]=Q[i].x=read(),lsh[++len]=Q[i].y=read();
}
sort(lsh+1,lsh+1+len);
len=unique(lsh+1,lsh+1+len)-lsh-1;
build(1,len,1);
FOR(i,1,n) {
if(Q[i].opt==2) continue;
Q[i].x=lower_bound(lsh+1,lsh+1+len,Q[i].x)-lsh;
Q[i].y=lower_bound(lsh+1,lsh+1+len,Q[i].y)-lsh;
}
//work
FOR(i,1,n) {
if(Q[i].opt==2)
cout<<e[1].sum<<"\n";
else
modify(Q[i].x,Q[i].y,1);
}
return 0;
}