基础分块
基础分块很简单
我们把长度为n的数列分成根号n个块，修改的时候对于散块直接暴力修改，整块把tag数组异或一下1就行了（修改次数为偶数则灯的开关情况不变）。
但只这样的话查询的时候不好查整块，所以还要维护一个ans数组，用于保存块内目前开着的灯的数量。散块修改的时候好维护，至于整块，修改的时候把ans变为 块的大小减去ans 就行了。
这样一来查询的时候也很简单了，散块直接暴力去查，整块的答案就是我们维护的ans qaq
详细代码（有注释，随便写了一个代码成了最优解？？？）
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define N 100005
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=nc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=nc();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline int Min(register int a,register int b)
{
return a<b?a:b;
}
int n,m,blocksize=0;
int a[N],b[N],tag[N],ans[N];
inline void change(register int l,register int r) //修改操作
{
for(register int i=l;i<=Min(r,b[l]*blocksize);++i) //散块直接修改
{
ans[b[l]]-=a[i]^tag[b[l]]; //维护ans数组
a[i]^=1; //更改状态
ans[b[l]]+=a[i]^tag[b[l]]; //维护ans数组
}
if(b[l]!=b[r]) //特判不能少，否则就会使同一个块被更改了两遍
for(register int i=(b[r]-1)*blocksize+1;i<=r;++i)
{
//同上
ans[b[r]]-=a[i]^tag[b[r]];
a[i]^=1;
ans[b[r]]+=a[i]^tag[b[r]];
}
for(register int i=b[l]+1;i<=b[r]-1;++i) //整块修改tag，维护ans数组
{
tag[i]^=1;
ans[i]=blocksize-ans[i];
}
}
inline int query(register int l,register int r) //查询操作
{
register int res=0;
for(register int i=l;i<=Min(r,b[l]*blocksize);++i) //散块直接查询
res+=a[i]^tag[b[l]];
if(b[l]!=b[r])
for(register int i=(b[r]-1)*blocksize+1;i<=r;++i)
res+=a[i]^tag[b[r]];
for(register int i=b[l]+1;i<=b[r]-1;++i) //整块加上维护的ans
res+=ans[i];
return res;
}
int main()
{
n=read(),m=read();
blocksize=sqrt(n); //分块大小默认为根号n，修改也有珂能能变得更快
for(register int i=1;i<=n;++i)
b[i]=(i-1)/blocksize+1; //预处理每个点所在的块
while(m--)
{
int opt=read(),l=read(),r=read();
if(opt==0)
change(l,r);
else
write(query(l,r)),puts("");
}
return 0;
}
树上分块
把一棵树分块，每块大小在[B, 3B]之间（B由输入数据给出），每个块需要对应一个核心点，核心点可以在块内，这个点要满足块内每个点到核心点的路径上的点都属于这个块（核心点本身不算），请输出分块方案。
实际bfs就行了qaq
对于一个子树u, 记录刚进入子树时的top，然后DFS所有子树，每当DFS完一个子树并发现新top - 原top >= B时，就把旧top以上的所有点弹出作为一个块，核心点是当前子树的根节点u。
注意最后可能有一块与根节点相连的部分没有归到任何块里，把它归到最后一个块中
完整代码（好草率qaq）
#include <bits/stdc++.h>
#define N 1005
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=nc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=nc();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
struct edge{
int to,next;
}e[N<<1];
int head[N],tot=0;
inline void add(register int u,register int v)
{
e[++tot]=(edge){v,head[u]};
head[u]=tot;
}
int n,B,top=0,idx=0;
int bel[N],cap[N],sta[N];
inline void dfs(register int u,register int pre)
{
int st=top;
for(register int i=head[u];i;i=e[i].next)
if(e[i].to!=pre)
{
dfs(e[i].to,u);
if(top-st>=B)
{
cap[++idx]=u;
while(top>st)
bel[sta[top--]]=idx;
}
}
sta[++top]=u;
}
int main()
{
n=read(),B=read();
for(register int i=1;i<n;++i)
{
int u=read(),v=read();
add(u,v),add(v,u);
}
dfs(1,0);
while(top)
bel[sta[top--]]=idx;
write(idx),putchar('
');
for(register int i=1;i<=n;++i)
write(bel[i]),putchar(' ');
putchar('
');
for(register int i=1;i<=idx;++i)
write(cap[i]),putchar(' ');
return 0;
}