dwjshift's Blog

spoj COT系列题 代码

| Comments

详细题解

COT2(在线,树上选关键点):

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)
using namespace std;
 
int n,m,w[40100],a[40100],last,tot,u,v,dep[40100],fa[40100],len[40100],
qt,key[410],idx[40100],fst[40100],snd[40100],cnt[40100][210],blk[40100][210],
l[40100],r[40100],sum[40100][340],lca[40100][340],x,t,path[40100][130],ans;
char ch;
struct edge
{
    int v;
    edge *next;
} pool[80100],*tp=pool,*first[40100];
  
inline int getint()
{
    while (!isdigit(ch=getchar()));
    int ret=ch-'0';
    for (; isdigit(ch=getchar()); ret=ret*10+ch-'0');
    return ret;
}
  
inline bool cmp(const int &x,const int &y)
{
    return w[x]<w[y];
}
  
void dfs(int x)
{
    memcpy(cnt[x],cnt[fa[x]],sizeof(cnt[x]));
    memcpy(blk[tot],blk[cnt[x][fst[w[x]]]],sizeof(blk[tot]));
    ++blk[tot][snd[w[x]]],cnt[x][fst[w[x]]]=tot++;
    for (edge *i=first[x]; i; i=i->next)
        if (i->v!=fa[x])
        {
            dep[i->v]=dep[x]+1,fa[i->v]=x,dfs(i->v);
            len[x]=max(len[x],len[i->v]+1);
        }
    if (len[x]>120)
        len[x]=0,key[idx[x]=++qt]=x;
}
 
inline int query(int u,int v,int lca,int w)
{
    return blk[cnt[u][fst[w]]][snd[w]]+blk[cnt[v][fst[w]]][snd[w]]
    -blk[cnt[lca][fst[w]]][snd[w]]-blk[cnt[fa[lca]][fst[w]]][snd[w]];
}
 
void dfs_(int x)
{
    repu(i,1,qt)
        if (!sum[x][i])
        {
            sum[x][i]=sum[fa[x]][i],lca[x][i]=lca[fa[x]][i];
            if (!query(key[i],fa[x],lca[x][i],w[x]))
                ++sum[x][i];
        }
    if (idx[x])
        len[x]=0;
    else
    {
        memcpy(path[x],path[fa[x]],sizeof(path[x]));
        path[x][len[x]=len[fa[x]]+1]=x;
    }
    l[x]=++tot;
    for (edge *i=first[x]; i; i=i->next)
        if (i->v!=fa[x])
            dfs_(i->v);
    r[x]=tot;
}
  
void query(int u,int v)
{
    if (dep[u]<dep[v])
        swap(u,v);
    x=idx[u]?u:fa[path[u][1]];
    if (l[x]<=l[v] && r[x]>=r[v])
    {
        ans=0;
        for (; u!=v; u=fa[u])
        {
            if (dep[u]<dep[v])
                swap(u,v);
            if (a[w[u]]!=m)
                a[w[u]]=m,++ans;
        }
        if (a[w[u]]!=m)
            ++ans;
        return;
    }
    ans=sum[v][idx[x]],t=lca[v][idx[x]];
    repu(i,1,len[u])
        if (!query(fa[path[u][i]],v,t,w[path[u][i]]))
            ++ans;
}
 
int main()
{
    scanf("%d%d",&n,&m);
    repu(i,1,n)
        w[i]=getint(),a[i]=i;
    sort(a+1,a+1+n,cmp);
    last=-1;
    repu(i,1,n)
        if (last==w[a[i]])
            w[a[i]]=tot;
        else
            last=w[a[i]],w[a[i]]=++tot;
    repu(i,1,tot)
        if (i%200)
            fst[i]=i/200+1,snd[i]=i%200;
        else
            fst[i]=i/200,snd[i]=200;
    tot=1;
    repu(i,1,n-1)
    {
        u=getint(),v=getint();
        tp->v=v,tp->next=first[u],first[u]=tp++;
        tp->v=u,tp->next=first[v],first[v]=tp++;
    }
    tot=1,dfs(dep[1]=1);
    if (key[qt]!=1)
        key[idx[1]=++qt]=1;
    memset(a,0,sizeof(a));
    repu(i,1,qt)
    {
        ans=0,++tot;
        for (int j=key[i]; j; j=fa[j])
        {
            if (a[w[j]]!=tot)
                a[w[j]]=tot,++ans;
            sum[j][i]=ans,lca[j][i]=j;
        }
    }
    tot=0,dfs_(1);
    ans=0,memset(a,-1,sizeof(a));
    while (m--)
    {
        u=getint()^ans,v=getint();
        query(u,v);
        printf(m?"%d\n":"%d",ans);
    }
    return 0;
}

COT5

#include <cstdio>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define mid l+(r-l>>1)
using namespace std;

const int maxnum=2147483647;
int n,opt,k,w,u,v,lca,maxw,lmax,rmax;
struct node
{
    int maxw,p,llen,rlen;
    node *lc,*rc;
    node();
} *tp,*nul,*root;

inline node::node()
{
    lc=tp,tp=this;
}

inline void newnode(node *&x)
{
    if (x!=nul)
        return;
    if (!tp)
        new node[10000];
    x=tp,tp=tp->lc;
    x->lc=x->rc=nul;
}

int queryl(node *x,int l,int r,int w)
{
    if (x->maxw<=w)
        return 0;
    if (l==r)
        return 1;
    if (x->lc->maxw<w)
        return queryl(x->rc,mid+1,r,w);
    return queryl(x->lc,l,mid,w)+x->llen-x->lc->llen;
}

int queryr(node *x,int l,int r,int w)
{
    if (x->maxw<=w)
        return 0;
    if (l==r)
        return 1;
    if (x->rc->maxw<w)
        return queryr(x->lc,l,mid,w);
    return queryr(x->rc,mid+1,r,w)+x->rlen-x->rc->rlen;
}

void modify(node *x,int l,int r,int k,int w)
{
    if (l==r)
    {
        x->maxw=w,x->p=k,x->llen=x->rlen=1;
        return;
    }
    if (k<=mid)
        newnode(x->lc),modify(x->lc,l,mid,k,w);
    else
        newnode(x->rc),modify(x->rc,mid+1,r,k,w);
    if (x->lc->maxw>x->rc->maxw)
        x->maxw=x->lc->maxw,x->p=x->lc->p;
    else
        x->maxw=x->rc->maxw,x->p=x->rc->p;
    x->llen=x->lc->llen+queryl(x->rc,mid+1,r,x->lc->maxw);
    x->rlen=x->rc->rlen+queryr(x->lc,l,mid,x->rc->maxw);
}

void query(node *x,int l,int r)
{
    if (u<=l && v>=r)
    {
        if (x->maxw>maxw)
            maxw=x->maxw,lca=x->p;
        return;
    }
    if (u<=mid)
        query(x->lc,l,mid);
    if (v>mid)
        query(x->rc,mid+1,r);
}

int query(node *x,int l,int r,int p)
{
    if (l==r)
    {
        lmax=rmax=x->maxw;
        return 1;
    }
    int ret;
    if (p<=mid)
    {
        ret=query(x->lc,l,mid,p)+queryl(x->rc,mid+1,r,lmax);
        lmax=max(lmax,x->rc->maxw);
    }
    else
    {
        ret=query(x->rc,mid+1,r,p)+queryr(x->lc,l,mid,rmax);
        rmax=max(rmax,x->lc->maxw);
    }
    return ret;
}

int main()
{
    newnode(nul),newnode(root=nul);
    scanf("%d",&n);
    while (n--)
    {
        scanf("%d",&opt);
        if (!opt)
            scanf("%d%d",&k,&w),modify(root,1,maxnum,k,w);
        if (opt==1)
            scanf("%d",&k),modify(root,1,maxnum,k,0);
        if (opt==2)
        {
            scanf("%d%d",&u,&v),maxw=0;
            if (u>v)
                swap(u,v);
            query(root,1,maxnum);
            printf("%d\n",query(root,1,maxnum,u)+query(root,1,maxnum,v)-query(root,1,maxnum,lca)*2);
        }
    }
    return 0;
}

Comments

comments powered by Disqus