bzoj 4009 分类： bzoj templates 2015-06-05 13:56 40人阅读 评论(0) 收藏

---

参考题解: http://www.cnblogs.com/mjy0724/p/4447813.html

　　我们先把所有的盘子按照权值排序 然后考虑二分

　　如果能覆盖一个水果的1~mid的所有盘子数>=该水果询问的k值

　　说明答案在[1,mid]当中，否则在[mid+1,r]中

　　但是为了减少计算量 我们可以每次只计算L~mid中的盘子

　　需要改变的就是划分到[mid+1,r]时减去[L,mid]中累积的答案

---

真是一道好题，扫描线+线段树+整体二分。

复杂度： O(N∗log2N+Q∗log2Q∗log2N+P∗log2P∗log2N)≈O(N∗(log2N)2)

第一次写整体二分 QAQ ，真的改了好久。。。

---

代码写了 6k +，我是大蒟蒻！

---

线段树：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

const int MAXN = 4e4+5, logN = 16, MAXP = MAXN, MAXQ = MAXP;
struct Btype{int l, r, val;}; struct Query{int id, k, gain;};
struct Node {int x, y; Node(int x = 0,int y = 0):x(x),y(y){}};
struct Edge {int v, next; Edge(int v = 0,int next = 0):v(v),next(next){}};
struct Squ  {int xl, xr, yl, yr; Squ(int xl = 0,int xr = 0,int yl = 0,int yr = 0):xl(xl),xr(xr),yl(yl),yr(yr){}};   
struct Issue{int x, yl, yr, val; Issue(int x = 0,int yl = 0,int yr = 0,int val = 0):x(x),yl(yl),yr(yr),val(val){}};

int n, P, Q; 
Btype bowl[MAXP]; Query qu[MAXQ];
Squ ss[MAXP<<1]; int sl; Node node[MAXQ];

int read()
{
    int x = 0; char c = getchar();
    while(!(c >= '0' && c <= '9')) c = getchar();
    while(c >= '0' && c <= '9')
        x = (x<<1)+(x<<3)+(c-'0'), c = getchar();
    return  x;  
}
void write(int x)
{
    static char s[12];int sl = 0;
    while(x) s[++sl] = x%10 + '0',x /= 10;
    if(!sl) {putchar('0');return;}
    while(sl) putchar(s[sl--]);
}

namespace TreeSolve
{
    int dfn[MAXN], fc[MAXN], end[MAXN], dl;
    Edge edge[MAXN<<1];int el, head[MAXN];
    int fa[MAXN][logN], dep[MAXN];

    void NewEdge(int u, int v)
    {
        edge[++el] = Edge(v,head[u]), head[u] = el;
    }
    void Init()
    {
        n = read(), P = read(), Q = read();
        for(int i = 1, u, v; i < n; i++)
            u = read(), v = read(), 
            NewEdge(u,v), NewEdge(v,u);
    }
    void PreLca()
    {
        for(int j = 1; j < logN; j++)
            for(int i = 1; i <= n; i++)
                fa[i][j] = fa[fa[i][j-1]][j-1]; 
    }
    int GetLca(int u,int v)
    {
        if(dep[u] > dep[v]) std::swap(u,v);

        for(int i = logN - 1; i >= 0; i--)
            if(dep[fa[v][i]] >= dep[u]) v = fa[v][i];

        if(u == v) return u;

        for(int i = logN - 1; i >= 0; i--)
            if(fa[u][i] != fa[v][i])
                u = fa[u][i], v = fa[v][i]; 

        return fa[u][0];    
    }
    int LinkSon(int u,int v)
    {
        if(dep[u] > dep[v]) std::swap(u,v);

        for(int i = logN - 1; i >= 0; i--)
            if(dep[fa[v][i]] > dep[u]) v = fa[v][i];

        return v;   
    }
    void DFS(int a)
    {
        dfn[++dl] = a, fc[a] = dl;
        dep[a] = dep[fa[a][0]] + 1;

        for(int i = head[a], p; i; i = edge[i].next)
            if((p = edge[i].v) != fa[a][0]) 
                fa[p][0] = a, DFS(p);   

        end[a] = dl;        
    }
    void GetSqu()
    {
        for(int i = 1, u, v, k; i <= P; i++)
        {
            u = read(), v = read(), k = read();
            int t = GetLca(u, v);

            if(t == u || t == v)
            {
                bowl[i].l = sl + 1;

                if(u != t)  std::swap(u,v);

                int w = LinkSon(u,v);

                if(fc[w] > 1)
                    ss[++sl] = Squ(1,fc[w]-1,fc[v],end[v]);
                if(end[w] < n)
                    ss[++sl] = Squ(fc[v],end[v],end[w]+1,n);    

                bowl[i].r = sl;
            }
            else
            {
                bowl[i].l = sl + 1;

                if(fc[u] > fc[v])   std::swap(u,v);
                ss[++sl] = Squ(fc[u],end[u],fc[v],end[v]);

                bowl[i].r = sl;
            }
            bowl[i].val = k;
        }
    }
    void GetNode()
    {
        for(int i = 1, u, v, k; i <= Q; i++)
        {
            u = read(), v = read(), k = read();

            if(fc[u] > fc[v])   std::swap(u,v);
            node[i] = Node(fc[u],fc[v]);
            qu[i].id = i, qu[i].k = k - 1;
        }
    }
    void Main()
    {
        Init(), DFS(1), PreLca(), GetSqu(), GetNode();  
    }
}
namespace SegSolve
{
    #define L(x) ((x)<<1)
    #define R(x) (((x)<<1)|1)
    bool cmpb(const Btype &a, const Btype &b){return a.val < b.val;}
    bool cmpis(const Issue &a, const Issue &b){return a.x < b.x;}
    bool cmpid(const Query &a, const Query &b){return a.id < b.id;}
    bool cmpq(const Query &a, const Query &b){return node[a.id].x < node[b.id].x;}

    int tree[MAXN<<2];

    void PushDown(int x)
    {
        tree[L(x)] += tree[x];
        tree[R(x)] += tree[x];
        tree[x] = 0; 
    }
    void Add(int l,int r,int ll,int rr,int s,int val)
    {
        if(l == ll && r == rr)
            tree[s] += val;
        else
        {
            PushDown(s);

            int mid = (ll + rr)>>1;
            if(r <= mid)
                Add(l,r,ll,mid,L(s),val);
            else if(l > mid)
                Add(l,r,mid+1,rr,R(s),val);
            else
                Add(l,mid,ll,mid,L(s),val),
                Add(mid+1,r,mid+1,rr,R(s),val);     
        }
    }
    int Ask(int k,int ll,int rr,int s)
    {
        if(ll == rr)
            return tree[s];
        else
        {
            PushDown(s);

            int mid = (ll + rr)>>1;
            if(k <= mid)
                return Ask(k,ll,mid,L(s));
            else
                return Ask(k,mid+1,rr,R(s));
        }
    }
    int segroll(int bl,int br,int ql,int qr)
    {
        static Issue hp[MAXP<<2]; int hl = 0;
        static Query tmp[MAXQ]; int tl = 0;

        for(int i = bl; i <= br; i++)
            for(int j = bowl[i].l; j <= bowl[i].r; j++)
            {
                hp[++hl] = Issue(ss[j].xl,ss[j].yl,ss[j].yr,1);
                hp[++hl] = Issue(ss[j].xr+1,ss[j].yl,ss[j].yr,-1);                  
            }
        std::sort(hp+1, hp+hl+1, cmpis);

        int p = ql, ret = ql - 1;

        for(int i = 1; i <= hl; i++)
        {
            while(p <= qr && node[qu[p].id].x < hp[i].x)
                qu[p++].gain = Ask(node[qu[p].id].y,1,n,1);

            Add(hp[i].yl,hp[i].yr,1,n,1,hp[i].val);
        }

        while(p <= qr) qu[p++].gain = 0;

        for(int i = ql; i <= qr; i++)
            if(qu[i].gain <= qu[i].k)
            {
                qu[i].k -= qu[i].gain;
                tmp[++tl] = qu[i];
            }
            else
                qu[++ret] = qu[i];

        for(int i = 1; i <= tl; i++)        
            qu[ret+i] = tmp[i];

        return ret; 
    }
    void Solve(int pl,int pr,int ql,int qr)
    {
        if(pl == pr)
        {
            for(int i = ql; i <= qr; i++)
                qu[i].gain = bowl[pl].val;
            return;
        }
        int mid = (pl + pr)>>1;
        int div = segroll(pl, mid, ql, qr);
        if(ql <= div) Solve(pl, mid, ql, div);
        if(div < qr) Solve(mid+1, pr, div+1, qr);
    }

    void Main()
    {
        std::sort(bowl+1,bowl+P+1,cmpb);
        std::sort(qu+1, qu+Q+1, cmpq);

        Solve(1,P,1,Q);

        std::sort(qu+1,qu+Q+1,cmpid);

        for(int i = 1; i <= Q; i++)
            write(qu[i].gain), putchar('\n');
    }
}

int main()
{
#ifndef ONLINE_JUDGE 
    freopen("bzoj4009.in","r",stdin);
    freopen("bzoj4009.out","w",stdout);
#endif 

    TreeSolve::Main();

    SegSolve::Main();

#ifndef ONLIE_JUDGE 
    fclose(stdin);
    fclose(stdout);
#endif 
    return 0;
}

树状数组：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

const int MAXN = 4e4+5, logN = 16, MAXP = MAXN, MAXQ = MAXP;
struct Btype{int l, r, val;}; struct Query{int id, k, gain;};
struct Node {int x, y; Node(int x = 0,int y = 0):x(x),y(y){}};
struct Edge {int v, next; Edge(int v = 0,int next = 0):v(v),next(next){}};
struct Squ  {int xl, xr, yl, yr; Squ(int xl = 0,int xr = 0,int yl = 0,int yr = 0):xl(xl),xr(xr),yl(yl),yr(yr){}};   
struct Issue{int x, yl, yr, val; Issue(int x = 0,int yl = 0,int yr = 0,int val = 0):x(x),yl(yl),yr(yr),val(val){}};

int n, P, Q; 
Btype bowl[MAXP]; Query qu[MAXQ];
Squ ss[MAXP<<1]; int sl; Node node[MAXQ];

int read()
{
    int x = 0; char c = getchar();
    while(!(c >= '0' && c <= '9')) c = getchar();
    while(c >= '0' && c <= '9')
        x = (x<<1)+(x<<3)+(c-'0'), c = getchar();
    return  x;  
}
void write(int x)
{
    static char s[12];int sl = 0;
    while(x) s[++sl] = x%10 + '0',x /= 10;
    if(!sl) {putchar('0');return;}
    while(sl) putchar(s[sl--]);
}

namespace TreeSolve
{
    int dfn[MAXN], fc[MAXN], end[MAXN], dl;
    Edge edge[MAXN<<1];int el, head[MAXN];
    int fa[MAXN][logN], dep[MAXN];

    void NewEdge(int u, int v)
    {
        edge[++el] = Edge(v,head[u]), head[u] = el;
    }
    void Init()
    {
        n = read(), P = read(), Q = read();
        for(int i = 1, u, v; i < n; i++)
            u = read(), v = read(), 
            NewEdge(u,v), NewEdge(v,u);
    }
    void PreLca()
    {
        for(int j = 1; j < logN; j++)
            for(int i = 1; i <= n; i++)
                fa[i][j] = fa[fa[i][j-1]][j-1]; 
    }
    int GetLca(int u,int v)
    {
        if(dep[u] > dep[v]) std::swap(u,v);

        for(int i = logN - 1; i >= 0; i--)
            if(dep[fa[v][i]] >= dep[u]) v = fa[v][i];

        if(u == v) return u;

        for(int i = logN - 1; i >= 0; i--)
            if(fa[u][i] != fa[v][i])
                u = fa[u][i], v = fa[v][i]; 

        return fa[u][0];    
    }
    int LinkSon(int u,int v)
    {
        if(dep[u] > dep[v]) std::swap(u,v);

        for(int i = logN - 1; i >= 0; i--)
            if(dep[fa[v][i]] > dep[u]) v = fa[v][i];

        return v;   
    }
    void DFS(int a)
    {
        dfn[++dl] = a, fc[a] = dl;
        dep[a] = dep[fa[a][0]] + 1;

        for(int i = head[a], p; i; i = edge[i].next)
            if((p = edge[i].v) != fa[a][0]) 
                fa[p][0] = a, DFS(p);   

        end[a] = dl;        
    }
    void GetSqu()
    {
        for(int i = 1, u, v, k; i <= P; i++)
        {
            u = read(), v = read(), k = read();
            int t = GetLca(u, v);

            if(t == u || t == v)
            {
                bowl[i].l = sl + 1;

                if(u != t)  std::swap(u,v);

                int w = LinkSon(u,v);

                if(fc[w] > 1)
                    ss[++sl] = Squ(1,fc[w]-1,fc[v],end[v]);
                if(end[w] < n)
                    ss[++sl] = Squ(fc[v],end[v],end[w]+1,n);    

                bowl[i].r = sl;
            }
            else
            {
                bowl[i].l = sl + 1;

                if(fc[u] > fc[v])   std::swap(u,v);
                ss[++sl] = Squ(fc[u],end[u],fc[v],end[v]);

                bowl[i].r = sl;
            }
            bowl[i].val = k;
        }
    }
    void GetNode()
    {
        for(int i = 1, u, v, k; i <= Q; i++)
        {
            u = read(), v = read(), k = read();

            if(fc[u] > fc[v])   std::swap(u,v);
            node[i] = Node(fc[u],fc[v]);
            qu[i].id = i, qu[i].k = k - 1;
        }
    }
    void Main()
    {
        Init(), DFS(1), PreLca(), GetSqu(), GetNode();  
    }
}
namespace SegSolve
{
    #define L(x) ((x)<<1)
    #define R(x) (((x)<<1)|1)
    bool cmpb(const Btype &a, const Btype &b){return a.val < b.val;}
    bool cmpis(const Issue &a, const Issue &b){return a.x < b.x;}
    bool cmpid(const Query &a, const Query &b){return a.id < b.id;}
    bool cmpq(const Query &a, const Query &b){return node[a.id].x < node[b.id].x;}

    int tree[MAXN<<2];

    int lowbit(int x)
    {
        return x&-x;
    }
    void Add(int x,int c)
    {   
        while(x <= n)
        {
            tree[x] += c;
            x += lowbit(x);
        }
    }
    void Change(int l, int r, int val)
    {
        Add(l, val), Add(r+1, -val);
    }
    int Ask(int x)
    {
        int ret = 0;
        while(x > 0)
        {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    int segroll(int bl,int br,int ql,int qr)
    {
        static Issue hp[MAXP<<2]; int hl = 0;
        static Query tmp[MAXQ]; int tl = 0;

        for(int i = bl; i <= br; i++)
            for(int j = bowl[i].l; j <= bowl[i].r; j++)
            {
                hp[++hl] = Issue(ss[j].xl,ss[j].yl,ss[j].yr,1);
                hp[++hl] = Issue(ss[j].xr+1,ss[j].yl,ss[j].yr,-1);                  
            }
        std::sort(hp+1, hp+hl+1, cmpis);

        int p = ql, ret = ql - 1;

        for(int i = 1; i <= hl; i++)
        {
            while(p <= qr && node[qu[p].id].x < hp[i].x)
                qu[p++].gain = Ask(node[qu[p].id].y);

            Change(hp[i].yl,hp[i].yr,hp[i].val);
        }

        while(p <= qr) qu[p++].gain = 0;

        for(int i = ql; i <= qr; i++)
            if(qu[i].gain <= qu[i].k)
            {
                qu[i].k -= qu[i].gain;
                tmp[++tl] = qu[i];
            }
            else
                qu[++ret] = qu[i];

        for(int i = 1; i <= tl; i++)        
            qu[ret+i] = tmp[i];

        return ret; 
    }
    void Solve(int pl,int pr,int ql,int qr)
    {
        if(pl == pr)
        {
            for(int i = ql; i <= qr; i++)
                qu[i].gain = bowl[pl].val;
            return;
        }
        int mid = (pl + pr)>>1;
        int div = segroll(pl, mid, ql, qr);
        if(ql <= div) Solve(pl, mid, ql, div);
        if(div < qr) Solve(mid+1, pr, div+1, qr);
    }

    void Main()
    {
        std::sort(bowl+1,bowl+P+1,cmpb);
        std::sort(qu+1, qu+Q+1, cmpq);

        Solve(1,P,1,Q);

        std::sort(qu+1,qu+Q+1,cmpid);

        for(int i = 1; i <= Q; i++)
            write(qu[i].gain), putchar('\n');
    }
}

int main()
{
#ifndef ONLINE_JUDGE 
    freopen("bzoj4009.in","r",stdin);
    freopen("bzoj4009.out","w",stdout);
#endif 

    TreeSolve::Main();

    SegSolve::Main();

#ifndef ONLIE_JUDGE 
    fclose(stdin);
    fclose(stdout);
#endif 
    return 0;
}

版权声明：本文为博主原创文章，未经博主允许不得转载。