A.不相邻集合
考虑值域上连续的段，可以发现连续的长度为 \(x\) 的段的贡献必定为 \(\lceil{\frac{x}{2}}\rceil\)
考虑并查集维护值域连续的段的大小，每次询问求出全部连续段的 \(\lceil{\frac{size}{2}}\rceil\) 之和即为答案
合并操作：在值域上加入 \(x\)，尝试合并 \(x-1\) 与 \(x+1\)
复杂度不对，考虑优化
- 记一个关于值域的 \(vis\)，若单次插入不改变 \(vis\)，则答案不变
- 每次在并查集上合并时直接统计答案，先减去两个分别的答案，再加上总和的答案
- 记得新加入单点时的贡献为 \(\lceil{\frac{1}{2}}\rceil=1\)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define void inline void
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define test(i) cout<<"test: "<<i<<endl
#define testp(i,j) cout<<i<<" "<<j<<endl
#define testd(i) cout<<i<<" "
#define end cout<<"\n"
#define div <<" "<<
#else
#define test(i)
#define testp(i,j)
#define testd(i)
#define end false
#define div ,
#endif
template<typename T>
void read(T& x){
x=0;bool sym=0;char c=getchar();
while(!isdigit(c)){sym^=(c=='-');c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
read(x);read(args...);
}
vector<int>has;
int ans=0;
class dsu{
public:
int fa[500001],siz[500001];
void reset(int n){
for(int i=1;i<=n;++i){
fa[i]=i;
siz[i]=1;
}
}
int find(int id){
if(fa[id]==id) return id;
fa[id]=find(fa[id]);
return fa[id];
}
void connect(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
fa[fx]=fy;
ans-=(siz[fy]+1)/2+(siz[fx]+1)/2;
siz[fy]+=siz[fx];
ans+=(siz[fy]+1)/2;
}
}
};
dsu d;
int a[300001];
bool vis[500001];
int tot,lastans=0;
int main(){
int n;
read(n);d.reset(500000);
for(int i=1;i<=n;++i){
read(a[i]);
if(!vis[a[i]]){
vis[a[i]]=true;
has.push_back(a[i]);
ans++;
if(vis[a[i]-1]){
d.connect(a[i],a[i]-1);
}
if(vis[a[i]+1]){
d.connect(a[i],a[i]+1);
}
}
cout<<ans<<' ';
}
}
B.线段树
设 \(f(n,x)\) 表示对从长度为 \(n\) 的连续段建立线段树（即有 \(n\) 个叶节点），根节点的值为 \(x\)，左儿子的值为 \(2x\)，右儿子的值为 \(2x+1\) 的情况下的全部节点权值和
可以发现对于根节点儿子的权值，相对于根节点权值的变化只有两种：即乘以一个系数或者加上若干值，也即 \(f(n,x)\) 是关于 \(x\) 的一次函数
设 \(f(n,x)=k_{n}x+b_{n}\)，考虑到我们在对此线段树向下分治的时候，总会有 \(\lceil{\frac{n}{2}}\rceil\) 长度的区间被分配到左儿子，\(\lfloor{\frac{n}{2}}\rfloor\) 长度的区间被分配到右儿子，也就是说：
\[f(n,x)=f(\lceil{\frac{n}{2}}\rceil,2x)+f(\lfloor{\frac{n}{2}}\rfloor,2x+1)+x \]根据上设，可得
\[k_{n}x+b_{n}=k_{\lceil{\frac{n}{2}}\rceil}2x+b_{\lceil{\frac{n}{2}}\rceil}+k_{\lfloor{\frac{n}{2}}\rfloor}(2x+1)+b_{\lfloor{\frac{n}{2}}\rfloor}+x \]解这个方程，得到
\[\begin{cases}k_{n}=2k_{\lceil{\frac{n}{2}}\rceil}+2k_{\lfloor{\frac{n}{2}}\rfloor}+1\\b_{n}=b_{\lceil{\frac{n}{2}}\rceil}+k_{\lfloor{\frac{n}{2}}\rfloor}+b_{\lfloor{\frac{n}{2}}\rfloor}\end{cases} \]关于这个递推式的初态，可以感性理解
- 当 \(n=1\) 时，线段树中只有一个节点 \(x\)，因此 \(k_{1}=1,b_{1}=0\)
- 当 \(n=2\) 时，线段树中只有三个节点 \(x,2x,2x+1\)，和为 \(5x+1\)，因此 \(k_{1}=5,b_{1}=1\)
其余开 map 记搜即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
template<typename T>
inline T read(){
T x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch-'0');
ch=getchar();
}
return x*f;
}
template<typename T>
inline T read(T&a){
T x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch-'0');
ch=getchar();
}
return a=x*f;
}
template<typename T>
inline void write(T x){
if(x<0)x*=-1,putchar('-');
if(x>9)write(x/10);
putchar(x%10+'0');
return;
}
const int p=1e9+7;
map<int,int> K,B;
int k(int n){
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 5;
if(K.count(n)) return K[n];
return K[n]=(2*(k((n+1)/2)+k(n/2))+1)%p;
}
int b(int n){
if(n==0) return 0;
if(n==1) return 0;
if(n==2) return 1;
if(B.count(n)) return B[n];
return B[n]=(b((n+1)/2)+b(n/2)+k(n/2))%p;
}
int build(int id,int l,int r,int L,int R){
if(l>R or r<L) return 0;
if(L<=l and r<=R){
return (k(r-l+1)*id%p+b(r-l+1))%p;
}
int mid=(l+r)/2;
return (build((id*2)%p,l,mid,L,R)+build((id*2+1)%p,mid+1,r,L,R))%p;
}
signed main(){
int T;read(T);
while(T--){
int n,l,r;
read(n);read(l);read(r);
write(build(1,1,n,l,r)%p);putchar('\n');
}
}