P4116 Qtree3

题解

树链剖分我讨厌重构代码

考虑线段树维护（还有一个set维护的方式，但是我拒绝）

线段树维护啥？？？

如果我们把黑点的权值设定为1，白点权值设定为0

zx[k] 表示 k 区间的第一个黑点

sum[k] 表示 k 区间的点权最大值，注意这里不需要把权值都加起来，只需要记录 0 ，1 就好

0： k 区间没有黑点，那么 zx[k] 显然为0，输出 -1

1： k 区间有黑点，那么 zx[k] 就是 k 区间最左侧的黑点

考虑维护zx[k]

（1）这是一个单点区间，那么如果 sum[k]=1 ，显然区间左端点就是那个第一个黑点

修改的时候，单点区间0变1,1变0， ^ 可以解决

（2）如果是一个区间，那么考虑左区间有没有 '第一个黑点' ，若有，k区间的 zx[k] 就是左区间的 ‘第一个黑点’ ，否则考虑右区间有没有，不然就都没有，记成0

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>

using namespace std;

typedef long long ll;

inline int read()
{
    int ans=0;
    char last=' ',ch=getchar();
    while(ch<'0'||ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

const int maxn=1e5+10;
int n,q;
int head[maxn<<2],to[maxn<<2],nxt[maxn<<2],cnt=0;
inline void addedge(int x,int y)
{
    to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;
    to[++cnt]=x;nxt[cnt]=head[y];head[y]=cnt;
}
int dfn[maxn],que[maxn],dep[maxn],fa[maxn],son[maxn],top[maxn],size[maxn],tim=0;
int zx[maxn<<2],sum[maxn<<2];

inline void dfs1(int u,int f)
{
    fa[u]=f;
    size[u]=1;  //一开始手残写错了QAQ TLE了 
    son[u]=0;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(v==f) continue;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}

inline void dfs2(int u,int f)
{
    dfn[u]=++tim;
    que[tim]=u;
    dep[u]=dep[f]+1;
    top[u]=(son[f]==u?top[f]:u);
    if(son[u]) dfs2(son[u],u);
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(v==f||v==son[u]) continue;
        dfs2(v,u);
    }
}

inline void up(int k,int l,int r)
{
    sum[k]=sum[k<<1]|sum[k<<1|1];
    //左右区间有一个是1，整体就是1 
    if(zx[k<<1]) zx[k]=zx[k<<1];
    //左区间有黑点 
    else if(zx[k<<1|1]) zx[k]=zx[k<<1|1];
    //右区间有黑点 
    else zx[k]=0;
    //都没有黑点 
}

inline void build(int k,int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    up(k,l,r);
}

inline void modify(int k,int l,int r,int p)
{
    if(l==r) //单点区间 
    {
        sum[k]^=1;
        if(sum[k]) zx[k]=l;
        else zx[k]=0;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) modify(k<<1,l,mid,p);
    if(mid<p) modify(k<<1|1,mid+1,r,p);
    up(k,l,r);
}

ll query(int k,int l,int r,int x,int y)
{
    if(r<x||y<l||l>r) return 0;
    if(x<=l&&r<=y) return zx[k];
    int mid=(l+r)>>1;
    ll a,b;
    a=query(k<<1,l,mid,x,y);
    b=query(k<<1|1,mid+1,r,x,y);
    if(a) return a;
    else return b;
}

int qus(int x)
{
    int a=0,ans=0;
    while(top[x]){
        a=query(1,1,n,dfn[top[x]],dfn[x]);
        if(a) ans=a;
        x=fa[top[x]];
    }
    a=query(1,1,n,1,dfn[x]);
    if(a) ans=a;
    if(a==0&&ans==0) return -1;
    else return que[ans];
}

int main()
{
    n=read();q=read();
    int x,y;
    for(int i=1;i<n;i++)
    {
        x=read();y=read();
        addedge(x,y);
    }

    dfs1(1,0);
    dfs2(1,0);
    build(1,1,n);

    for(int i=1;i<=q;i++)
    {
        x=read();y=read();
        if(x==0) modify(1,1,n,dfn[y]);
        if(x==1) printf("%d
",qus(y));
    }
    return 0;
}