查询最远点对，带修改

显然可以用动态点分治

对于每个点，维护两个堆

堆q1[x] 维护 点分树x的子树中，所有黑点到x的点分树中父节点的距离

堆q2[x]维护 点分树x的子节点的堆q1的堆顶，即若y是x在点分树中的子节点，则q2[x].push(q1[y].top())

再来维护一个全局的堆Q，维护所有q2的堆顶，即Q.push(q2[x].top())

 

#include
     
      #include
      
       #include
       
        #include
        
          using namespace std; #define N 100001 #define Swap(a,b) ( (a)^=(b),(b)^=(a),(a)^=(b) ) int n; int front[N],to[N<<1],nxt[N<<1],tot; int fa[N]; bool light[N];int sum; void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }} void add(int u,int v){    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;} namespace LCA{    int fa[N][18],dep[N],bin[18],lim;             void dfs(int x)    {        for(int i=front[x];i;i=nxt[i])            if(to[i]!=fa[x][0])            {                dep[to[i]]=dep[x]+1;                fa[to[i]][0]=x;                dfs(to[i]);            }    }     int query(int x,int y)    {        if(dep[x]
         
          =0;--i)            if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];        if(x==y) return x;        for(int i=lim;i>=0;--i)            if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];        return fa[x][0];    }     int dist(int x,int y)    {        return dep[x]+dep[y]-(dep[query(x,y)]<<1);    }     void main()    {        lim=log(n)/log(2);        bin[0]=1;        for(int i=1;i<18;++i) bin[i]=bin[i-1]<<1;        dep[1]=1;        dfs(1);        for(int i=1;i<=lim;++i)            for(int j=1;j<=n;++j)                fa[j][i]=fa[fa[j][i-1]][i-1];    }} struct HEAP{    priority_queue
          
           heap,trash; void Pop(int x) { trash.push(x); } void Push(int x) { heap.push(x); } int Size() { return heap.size()-trash.size(); } int Top() { if(Size()) { while(!trash.empty() && heap.top()==trash.top()) heap.pop(),trash.pop(); return heap.top(); } return 0; } int Top_Sec() { if(Size()>=2) { int first,second; while(!trash.empty() && heap.top()==trash.top()) heap.pop(),trash.pop(); first=heap.top(); heap.pop(); while(!trash.empty() && heap.top()==trash.top()) heap.pop(),trash.pop(); second=heap.top(); heap.push(first); return first+second; } else return Top(); } }q1[N],q2[N],Q; namespace Point_divide{ int siz[N],mx[N]; bool vis[N]; int root,min_size; void get_dist(int x,int pa,int fa) { q1[root].Push(LCA::dist(pa,x)); for(int i=front[x];i;i=nxt[i]) if(to[i]!=fa && !vis[to[i]]) get_dist(to[i],pa,x); } void get_size(int x,int fa) { siz[x]=1; mx[x]=0; for(int i=front[x];i;i=nxt[i]) if(!vis[to[i]] && to[i]!=fa) { get_size(to[i],x); siz[x]+=siz[to[i]]; if(siz[to[i]]>mx[x]) mx[x]=siz[to[i]]; } } void get_root(int x,int pa,int fa) { mx[x]=max(mx[x],siz[pa]-siz[x]); if(mx[x]
           
            =2) Q.Push(q2[rt].Top_Sec()); } void main() { work(1,0); } } void turn_off(int x){ if(q2[x].Size()>=2) Q.Pop(q2[x].Top_Sec()); q2[x].Push(0); if(q2[x].Size()>=2) Q.Push(q2[x].Top_Sec()); for(int u=x;fa[u];u=fa[u]) { if(q2[fa[u]].Size()>=2) Q.Pop(q2[fa[u]].Top_Sec()); if(q1[u].Size()) q2[fa[u]].Pop(q1[u].Top()); q1[u].Push(LCA::dist(fa[u],x)); q2[fa[u]].Push(q1[u].Top()); if(q2[fa[u]].Size()>=2) Q.Push(q2[fa[u]].Top_Sec()); }} void turn_on(int x){ if(q2[x].Size()>=2) Q.Pop(q2[x].Top_Sec()); q2[x].Pop(0); if(q2[x].Size()>=2) Q.Push(q2[x].Top_Sec()); for(int u=x;fa[u];u=fa[u]) { if(q2[fa[u]].Size()>=2) Q.Pop(q2[fa[u]].Top_Sec()); q2[fa[u]].Pop(q1[u].Top()); q1[u].Pop(LCA::dist(x,fa[u])); if(q1[u].Size()) q2[fa[u]].Push(q1[u].Top()); if(q2[fa[u]].Size()>=2) Q.Push(q2[fa[u]].Top_Sec()); }} int main(){ //freopen("hide.in","r",stdin); //freopen("hide.out","w",stdout); read(n); int u,v; for(int i=1;i
            
             =2) printf("%d\n",Q.Top()); else printf("%d\n",sum-1); } else { read(u); if(light[u])turn_off(u),sum++; else turn_on(u),sum--; light[u]^=1; //printf("%d\n",Q.Top()); } } return 0;}