Bakser's Blog

我是逗比。

bzoj3531 树链剖分+动态开点线段树

| Comments

这就是考场上打错文件名的那道题。。。。
代码基本上跟考场一样,就是用动态线段树代替了zkw线段树。然后50->100,打错文件名50->0!!!!!
其实dfs在win下会爆TAT,一会写非递归去。。。。
可惜现在只能是一道bzoj3531了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define N 100100
#define MAX(a,b) (((a)>(b))?(a):(b))
struct hh
{
    int lson,rson,maxx,sum;
    hh(){lson=rson=maxx=sum=0;}
}tree[3010000];
struct edge
{
    int next,v;
}edges[N<<1];
int n,q,w[N],c[N],col[N],point[N],tid[N],son[N],dep[N],top[N],fa[N],size[N],tot,num,L,R;
bool flag;
char str[10];
queue<int> pool;
inline void addedge(int u,int v)
{
    static int en(0);
    edges[++en].next=point[u];
    point[u]=en;
    edges[en].v=v;
}
inline void newnode(int &x)
{
    if(!pool.empty()){x=pool.front();pool.pop();}
    else x=++num;
}
inline void push_up(int x)
{
    tree[x].maxx=MAX(tree[tree[x].lson].maxx,tree[tree[x].rson].maxx);
    tree[x].sum=tree[tree[x].lson].sum+tree[tree[x].rson].sum;
}
inline void modify(int &x,int l,int r,int pos,int delta)
{
    if(!x)newnode(x);
    if(l==r)
    {
        tree[x].maxx=tree[x].sum=delta;
        return;
    }
    int mid(l+r>>1);
    if(pos<=mid)modify(tree[x].lson,l,mid,pos,delta);
    if(pos>mid)modify(tree[x].rson,mid+1,r,pos,delta);
    push_up(x);
}
inline int merge(int a,int b)
{
    return flag?a+b:MAX(a,b);
}
inline int query(int x,int l,int r)
{
    if(!x)return 0;
    if(l>=L&&r<=R)return flag?tree[x].sum:tree[x].maxx;
    int mid(l+r>>1),res(0);
    if(L<=mid)res=merge(res,query(tree[x].lson,l,mid));
    if(R>mid)res=merge(res,query(tree[x].rson,mid+1,r));
    return res;
}
inline void dfs(int x)
{
    size[x]=1;son[x]=0;
    for(int i=point[x];i;i=edges[i].next)
    if(edges[i].v!=fa[x]){
        fa[edges[i].v]=x;
        dep[edges[i].v]=dep[x]+1;
        dfs(edges[i].v);
        size[x]+=size[edges[i].v];
        if(size[edges[i].v]>size[son[x]])son[x]=edges[i].v;
    }
}
inline void make(int x,int anc)
{
    top[x]=anc;tid[x]=++tot;modify(col[c[x]],1,n,tid[x],w[x]);
    if(son[x])make(son[x],anc);
    for(int i=point[x];i;i=edges[i].next)
        if(edges[i].v!=fa[x]&&edges[i].v!=son[x])
            make(edges[i].v,edges[i].v);
}
inline int ask(int x,int y)
{
    int f1=top[x],f2=top[y],res(0),color(c[x]);
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2]){swap(x,y);swap(f1,f2);}
        L=tid[f1];R=tid[x];
        int tmp=query(col[color],1,n);
        res=merge(res,tmp);
        x=fa[f1];f1=top[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    L=tid[x];R=tid[y];
    int tmp=query(col[color],1,n);
    res=merge(res,tmp);
    return res;
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d%d",w+i,c+i);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    dfs(1);
    make(1,0);
    while(q--)
    {
        int x,y;
        scanf("%s%d%d",str,&x,&y);
        if(str[0]=='C')
        {
            if(str[1]=='C')
            {
                modify(col[c[x]],1,n,tid[x],0);
                c[x]=y;
                modify(col[y],1,n,tid[x],w[x]);
            }
            else modify(col[c[x]],1,n,tid[x],y),w[x]=y;
        }
        else
        {
            if(str[1]=='M')flag=0,printf("%d\n",ask(x,y));
            else flag=1,printf("%d\n",ask(x,y));
        }
    }
    return 0;
}

Comments

comments powered by Disqus