1146_cqtest.cpp

/**************************************************************
    Problem: 1146
    User: cqtest
    Language: C++
    Result: Accepted
    Time:2388 ms
    Memory:127016 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
std::pair<int,int> number[110004];
int cnt,tot,arg,op,times,cht[80004],orig[110004],prt[80004],fa[80004],w[80004],head[80004],entry[80004],LCA[30004],Q[30004][3],IN[80004],OUT[80004],BIT[80004];
bool vis[80004];
struct chairtree{
    int lc,rc,size;
}tree[10000000];
struct _e{
    int to,next;
}e[80004*2];
struct _list{
    int to,id,next;
}list[30004*2];
void add(int u,int v)
{
    static int tot=0;
    e[++tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;
}
void addq(int u,int v,int id)
{
    static int tot=0;
    list[++tot].to=v;
    list[tot].id=id;
    list[tot].next=entry[u];
    entry[u]=tot;
}
int getrt(int x)
{
    return x==prt[x]?x:prt[x]=getrt(prt[x]);
}
int buildempty(int l,int r)
{
    int v=++tot;
    if(l==r)
        return v;
    int mid=l+r>>1;
    tree[v].lc=buildempty(l,mid);
    tree[v].rc=buildempty(mid+1,r);
    return v;
}
int insert(int old,int l,int r)
{
    int node=++tot;
    if(l==r){
        tree[node].size=tree[old].size+op;
        return node;
    }
    int mid=(l+r)>>1;
    tree[node]=tree[old];
    if(arg<=mid)
        tree[node].lc=insert(tree[node].lc,l,mid);
    else
        tree[node].rc=insert(tree[node].rc,mid+1,r);
    tree[node].size+=op;
    return node;
}
void tarjan_dfs(int v,int f)
{
    fa[v]=f;
    arg=w[v],op=1;
    cht[v]=insert(cht[f],1,cnt);
    prt[v]=v;
    IN[v]=++times;
    for(int i=head[v];i;i=e[i].next){
        int to=e[i].to;
        if(to!=f){
            tarjan_dfs(to,v);
            prt[to]=v;
        }
    }
    vis[v]=1;
    for(int i=entry[v];i;i=list[i].next){
        int to=list[i].to;
        if(vis[to])
            LCA[list[i].id]=getrt(to);
    }
    OUT[v]=times;
}
struct result{
    int index[21],cnt;
    result():cnt(0){}
    void operator+=(int x){
        index[++cnt]=x;
    }
    int size(){
        int ret=0;
        for(int i=1;i<=cnt;i++)
            ret+=tree[index[i]].size;
        return ret;
    }
    int rsize(){
        int ret=0;
        for(int i=1;i<=cnt;i++)
            ret+=tree[tree[index[i]].rc].size;
        return ret;
    }
    void left(){
        for(int i=1;i<=cnt;i++)
            index[i]=tree[index[i]].lc;
    }
    void right(){
        for(int i=1;i<=cnt;i++)
            index[i]=tree[index[i]].rc;
    }
};
void BITquery(result &R,int x)
{
    if(x==0)
        R+=BIT[0];
    else
        for(;x<=times;x+=x&-x)
            R+=BIT[x];
}
void BITmodify(int l,int r,int val,int d)
{
    arg=val,op=d;
    for(;r>0;r^=r&-r)
        BIT[r]=insert(BIT[r],1,cnt);
    op=-d;
    for(l--;l>0;l^=l&-l)
        BIT[l]=insert(BIT[l],1,cnt);
}
void discretize(int n)
{
#define ID(i) number[i].second
    std::sort(number+1,number+1+n);
    for(int i=1,j;i<=n;i++){
        if(ID(i)>123456)
            Q[ID(i)-123456][1]=++cnt;
        else
            w[ID(i)]=++cnt;
        orig[cnt]=number[i].first;
        for(j=i+1;j<=n&&number[i].first==number[j].first;j++)
            if(ID(j)>123456)
                Q[ID(j)-123456][1]=cnt;
            else
                w[ID(j)]=cnt;
        i=j-1;
    }
}
int getint(){
    int c,ret=0;
    while(c=getchar(),c<'0'||c>'9');
    while(c>='0'&&c<='9'){
        ret=ret*10+(c-'0');
        c=getchar();
    }
    return ret;
}
int main()
{
    int n,m,all;
    scanf("%d%d",&n,&m);
    all=n;
    for(int i=1;i<=n;i++){
        w[i]=getint();
        number[i]=std::make_pair(w[i],i);
    }
    for(int i=1;i<n;i++){
        int u,v;
        u=getint(),v=getint();
        add(u,v);add(v,u);
    }
    for(int i=1;i<=m;i++){
        Q[i][2]=getint();
        Q[i][0]=getint();
        Q[i][1]=getint();
        if(Q[i][2]){
            addq(Q[i][0],Q[i][1],i);
            addq(Q[i][1],Q[i][0],i);
        }else{
            number[++all]=std::make_pair(Q[i][1],123456+i);
        }
    }
    discretize(all);
    BIT[0]=cht[0]=buildempty(1,cnt);
    tarjan_dfs(1,0);
    for(int i=1;i<=m;i++){
        if(Q[i][2]){
            result a,b,c,d;
            BITquery(a,IN[Q[i][0]]);a+=cht[Q[i][0]];
            BITquery(b,IN[Q[i][1]]);b+=cht[Q[i][1]];
            BITquery(c,IN[LCA[i]]);c+=cht[LCA[i]];
            BITquery(d,IN[fa[LCA[i]]]);d+=cht[fa[LCA[i]]];
            int l=1,r=cnt,k=Q[i][2],s;
            if(a.size()+b.size()-c.size()-d.size()<k){
                puts("invalid request!");
                continue;
            }
            while(l!=r){
                s=a.rsize()+b.rsize()-c.rsize()-d.rsize();
                if(s<k){
                    k-=s;
                    a.left();b.left();c.left();d.left();
                    r=l+r>>1;
                }else{
                    a.right();b.right();c.right();d.right();
                    l=(l+r>>1)+1;
                }
            }
            printf("%d\n",orig[l]);
        }else{
            BITmodify(IN[Q[i][0]],OUT[Q[i][0]],w[Q[i][0]],-1);
            BITmodify(IN[Q[i][0]],OUT[Q[i][0]],w[Q[i][0]]=Q[i][1],1);
        }
    }
    //fprintf(stderr,"%d\n",tot);
}

1146_YangZX.cpp

/**************************************************************
    Problem: 1146
    User: YangZX
    Language: C++
    Result: Accepted
    Time:7192 ms
    Memory:162696 kb
****************************************************************/
 
int getint(void);
/*
   可持久化线段树
   求定义:sin(一个线段树)
 */
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
 
using namespace std;
const int MAXN = 80008, MAXV = 120008, DMAXN = 2*MAXN, LOGV = 17;
 
struct Tree{
    struct edge{
        int t, next;
    }es[MAXN * 2];
    int h[MAXN], cnt;
 
    void addedge(int a, int b)
    {
        es[++cnt] = (edge){b, h[a]};
        h[a] = cnt;
    }
}T;
int n, Q;
 
int delay[MAXN];
 
struct Query{
    int k, a, b;
}qs[MAXN];
 
void ReadInput()
{
    n = getint();
    Q = getint();
    int i;
    for(i=1; i<=n; i++)
        delay[i] = getint();
    for(i=1; i<n; i++){
        int a, b;
        a = getint();
        b = getint();
        T.addedge(a, b);
        T.addedge(b, a);
    }
    for(i=1; i<=Q; i++){
        qs[i].k = getint();
        qs[i].a = getint();
        qs[i].b = getint();
    }
}
 
pair<int,int> disc[MAXV];
int cnt, rdisc[MAXV];
void Discretize()
{
    int num, i;
    for(i=1; i<=n; i++)
        disc[++num] = make_pair(delay[i], i);
    for(i=1; i<=Q; i++)
        if(!qs[i].k)
            disc[++num] = make_pair(qs[i].b, n+i);
    sort(disc+1, disc+num+1, greater< pair<int,int> >());
    for(i=1; i<=num; i++){
        if(i == 1 || disc[i].first != disc[i-1].first)
            rdisc[++cnt] = disc[i].first;
        if(disc[i].second <= n)
            delay[disc[i].second] = cnt;
        else
            qs[disc[i].second - n].b = cnt;
    }
}
 
int vis[MAXN], euler[DMAXN], stamp_euler, first_euler[MAXN], depth[MAXN];
int dfs[MAXN], first[MAXN], second[MAXN], stamp_dfs;
void Foreach(int v, int dep = 0)
{
    vis[v] = 1;
    depth[v] = dep;
    euler[++stamp_euler] = v;
    first_euler[v] = stamp_euler;
 
    dfs[++stamp_dfs] = v;
    first[v] = stamp_dfs;
 
    for(int p = T.h[v]; p; p = T.es[p].next){
        int dst = T.es[p].t;
        if(vis[dst])
            continue;
        Foreach(dst, dep+1);
 
        euler[++stamp_euler] = v;
    }
    second[v] = stamp_dfs;
}
 
int st[20][DMAXN];
void InitRMQ()
{
    int i, j;
    for(i=1; i<=stamp_euler; i++)
        st[0][i] = euler[i];
    int bnd = int(log2(stamp_euler));
    for(j=1; j<=bnd; j++)
        for(i=1; i + (1<<j) - 1 <= stamp_euler; i++)
            if(depth[st[j-1][i]] < depth[st[j-1][i + (1<<j-1)]])
                st[j][i] = st[j-1][i];
            else
                st[j][i] = st[j-1][i + (1<<j-1)];
}
 
int RMQQuery(int a, int b)
{
    int len = int(log2(b - a + 1));
    if(depth[st[len][a]] < depth[st[len][b - (1<<len) + 1]])
        return st[len][a];
    else
        return st[len][b - (1<<len) + 1];
}
int LCA(int a, int b)
{
    if(first_euler[a] > first_euler[b])
        swap(a, b);
    return RMQQuery(first_euler[a], first_euler[b]);
}
 
struct ChairTree{
    ChairTree *l, *r;
    int sz;
    bool fresh;
}SLOT[8964648], *null;
 
__inline ChairTree* newnode()
{
    static int tcnt = 0;
    return SLOT + (++tcnt);
}
ChairTree* NullTree(int l, int r)
{
    ChairTree* ret = newnode();
    if(l == r)
        return ret;
    int mid = (l + r)>>1;
    ret->l = NullTree(l, mid);
    ret->r = NullTree(mid+1, r);
    return ret;
}
 
int ml, mr, mk, md;
ChairTree* Modify(ChairTree* v)
{
    ChairTree* ret;
    if(v -> fresh)
        ret = v;
    else{
        ret = newnode();
        *ret = *v;
        ret->fresh = 1;
    }
    if(ml == mr){
        ret->sz = v->sz + md;
        return ret;
    }
    int mid = (ml + mr)>>1;
    if(mk <= mid){
        mr = mid;
        ret -> l = Modify(ret -> l);
    }else{
        ml = mid+1;
        ret -> r = Modify(ret -> r);
    }
    ret -> sz += md;
    return ret;
}
 
int curtime, curdir;
struct FenwickTree{
    ChairTree* c[MAXN], *cur[MAXN];
    int cookie[MAXN];
    void add(int k, int v, int d)
    {
        for(; k<=stamp_dfs; k += k & -k){
            ml = 1, mr = cnt, mk = v, md = d;
            c[k] = Modify(c[k]);
        }
    }
 
    int sum(int k)
    {
        int ret = 0;
        for(; k; k -= k & -k){
            if(cookie[k] != curtime){
                cookie[k] = curtime;
                if(curdir == -1)
                    cur[k] = c[k];
                else if(curdir == 1)
                    cur[k] = cur[k] -> l;
                else
                    cur[k] = cur[k] -> r;    
            }
            ret += cur[k] -> l -> sz;
        }
        return ret;
    }
 
    void init()
    {
        for(int i=0; i<=stamp_dfs; i++)
            c[i] = null;
    }
}bit;
int main()
{
    ReadInput();
    Discretize();
    Foreach(1);
    InitRMQ();
    null = NullTree(1, cnt);
    bit.init();
     
    int i;
    for(i=1; i<=n; i++){
        bit.add(first[i], delay[i], 1);
        bit.add(second[i]+1, delay[i], -1);
    }
     
    for(i=1; i<=Q; i++)
        if(qs[i].k == 0){
            int a = qs[i].a, b = qs[i].b;
            if(second[a] <= n)
                bit.add(second[a]+1, delay[a], 1);
            bit.add(first[a], delay[a], -1);
            bit.add(first[a], b, 1);
            if(second[a] <= n)
                bit.add(second[a]+1, b, -1);
            delay[a] = b;
        }else{
            curdir = -1;
            curtime++;
            int a = qs[i].a, b = qs[i].b, lca = LCA(a, b), k = qs[i].k;
            if(k > depth[a] + depth[b] - 2*depth[lca] + 1){
                puts("invalid request!");
                continue;
            }
            int l = 1, r = cnt;
            while(l != r){
                int mid = (l + r)>>1;
                int szl = bit.sum(first[a]) + bit.sum(first[b]) - 2*bit.sum(first[lca]) + (delay[lca] <= mid && delay[lca] >= l);
                if(k <= szl){
                    r = mid;
                    curdir = 1;
                }else{
                    l = mid+1;
                    k -= szl;
                    curdir = 0;
                }
                curtime++;
            }   
            printf("%d\n", rdisc[l]);
        }
    return 0;
}
int getint()
{
    int ret = 0, c;
    while(c = getchar(), c < '0' || c > '9')
        ;
    do
        ret = ret * 10 + c - '0';
    while(c = getchar(), c >= '0' && c <= '9');
    return ret;
}