description

solution

这里的单点询问需要全部的修改才能统计出答案

需要用到线段树分治的另一个形式:

在树上$DFS$维护数据结构,进入叶子的时候求出询问答案,回溯的时候栈序撤销

数据结构选择的是并查集，维护连通性和到达代表元(根节点)的路径长度奇偶性，合并的时候判断是否出现奇环即可

写了一个比较直接的内存修改的撤销

空间227M

千万别学我

code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   #include
                    
                     #define FILE "a"#define mp make_pair#define pb push_back#define RG register#define il inlineusing namespace std;typedef unsigned long long ull;typedef vector
                     
                      VI;typedef long long ll;typedef double dd;const dd eps=1e-10;const int mod=1e9+7;const int N=2e5+10;const dd pi=acos(-1);const int inf=2147483647;const ll INF=1e18+1;il ll read(){ RG ll data=0,w=1;RG char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar(); return data*w;}int n,m,T;struct modify{int u,v;}M[N];vector
                      
                       f[N<<4];struct data{int o,id,x;};vector
                       g[N<<4];#define mid ((l+r)>>1)#define ls (t<<1)#define rs (t<<1|1)void insertmodify(int t,int l,int r,int x,int y,modify m){ if(x<=l&&r<=y){f[t].pb(m);return;} if(x<=mid)insertmodify(ls,l,mid,x,y,m); if(mid
                        
                         sz[fv])swap(u,v),swap(fu,fv); g[now].pb((data){1,fu,fa[fu]}); fa[fu]=fv; g[now].pb((data){2,fv,sz[fv]}); sz[fv]+=sz[fu]; g[now].pb((data){3,fu,dis[fu]}); dis[fu]=dis[u]^dis[v]^1; return 1;}il void recover(int t){ while(g[t].size()){ RG data a=g[t][g[t].size()-1]; if(a.o==1)fa[a.id]=a.x; if(a.o==2)sz[a.id]=a.x; if(a.o==3)dis[a.id]=a.x; g[t].pop_back(); }}void segdiv(int t,int l,int r){ now=t; for(RG int i=0,sz=f[t].size();i