首页 > 其他 > 详细

xxx

时间:2017-11-24 23:43:12      阅读:38      评论:0      收藏:0      [点我收藏+]

标签:spl   .so   find   nload   sca   clu   root   single   ++   

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
//#include<iostream>
using namespace std;

int n,q;
#define maxn 400011
#define LL long long
struct Edge{int to;LL v;int next;}edge[maxn<<1],eve[maxn];int first[maxn],feve[maxn],le=2,lee=2;
void in(int x,int y,int v,Edge *edge,int *first,int &le) {Edge &e=edge[le];e.to=y;e.next=first[x];first[x]=le++;}
void insert(int x,int y,int v,Edge *edge,int *first,int &le) {in(x,y,v,edge,first,le);in(y,x,v,edge,first,le);}

LL val[maxn];
void dfs(int x,int fa)
{
    val[x]=0;
    for (int i=first[x];i;i=edge[i].next)
    {
        const Edge &e=edge[i];if (e.to==fa) continue;
        val[e.to]=e.v;
        dfs(e.to,x);
    }
}

struct Splay
{
    struct Node
    {
        int size;LL sum;
        LL add;
        LL v;
        int fa,son[2];
        Node() {fa=son[0]=son[1]=v=add=sum=size=0;}
    }a[maxn];
    int size;
    Splay() {size=0;}
    void up(int x)
    {
        if (!x) return;
        const int &p=a[x].son[0],&q=a[x].son[1];
        a[x].size=a[p].size+a[q].size+1;
        a[x].sum=a[p].sum+a[q].sum+a[x].v;
    }
    void Addsingle(int x,LL v)
    {
        if (!x) return;
        a[x].add+=v;
        a[x].v+=v;
        a[x].sum+=a[x].size*v;
    }
    void down(int x)
    {
        if (!x) return;
        const int &p=a[x].son[0],&q=a[x].son[1];
        if (a[x].add)
        {
            Addsingle(p,a[x].add);
            Addsingle(q,a[x].add);
            a[x].add=0;
        }
    }
    int sta[maxn],top;
    void download(int x)
    {
        top=0;
        for (int i=x;i;i=a[x].fa) sta[++top]=i;
        for (;top;top--) down(sta[top]);
    }
    void rotate(int x)
    {
        if (!x) return;
        const int y=a[x].fa,z=a[y].fa;
        bool w=(x==a[y].son[0]);
        a[x].fa=z;
        if (z) a[z].son[y==a[z].son[1]]=x;
        a[y].son[w^1]=a[x].son[w];
        if (a[x].son[w]) a[a[x].son[w]].fa=y;
        a[x].son[w]=y;
        a[y].fa=x;
        up(y);up(z);
    }
    void splay(int x)
    {
        if (!x) return;
        download(x);
        while (a[x].fa)
        {
            const int y=a[x].fa,z=a[y].fa;
            if (z)
            {
                if ((x==a[y].son[0])^(y==a[z].son[0])) rotate(x);
                else rotate(y);
            }
        }
        up(x);
    }
    void insert(int &root,LL id)
    {
        if (!root)
        {
            root=++size;
            a[size].v=id;
            a[size].size=1;
            a[size].sum=id;
        }
        else
        {
            int x=root,last,from;
            while (x)
            {
                last=x;
                if (a[x].id>id) x=a[x].son[from=0];
                else x=a[x].son[from=1];
            }
            size++;
            download(last);
            a[last].son[from]=size;
            a[size].fa=last;
            a[size].v=a[size].sum=id;
            a[size].size=1;
            up(last);
        }
    }
    int findpre(int rt,LL id)
    {
        int ans=0,now=rt;
        while (now)
        {
            if (a[now].v<id) ans=now,now=a[now].son[1];
            else now=a[now].son[0];
        }
        splay(ans);
        return ans;
    }
    int findsuc(int rt,LL id)
    {
        int ans=0,now=rt;
        while (now)
        {
            if (a[now].v>id) ans=now,now=a[now].son[0];
            else now=a[now].son[1];
        }
        splay(ans);
        return ans;
    }
    LL query(int rt,LL id)
    {
        int now=findsuc(rt,id);
        now=
}t;

int root[maxn];
void solve(int x,int fa)
{
    int base=0;
    for (int i=first[x];i;i=edge[i].next)
    {
        const Edge &e=edge[i];if (e.to==fa) continue;
        if (!base) base=root[e.to];
        else
        {
            if (t.a[base].size>t.a[root[e.to]].size)
                t.combine(base,root[e.to]);
            else
            {
                t.combine(root[e.to],base);
                base=root[e.to];
            }
        }
    }
    root[x]=base;
    for (int i=feve[x];i;i=eve[i].next)
    {
        const Edge &e=eve[i];
        eve[i].v=t.query(base,eve[i].to);
    }
    t.add(base,val[x]);
    t.Delete(base,1e6+1);
    t.insert(base,0);
}

int main()
{
    scanf("%d",&n);
    for (int i=2,x,y;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        insert(x,i,y,edge,first,le);
    }
    dfs(1,0);
    scanf("%d",&q);
    for (int i=1,x,y;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        in(x,y,0,eve,feve,lee);
    }
    solve(1,0);
    for (int i=2;i<lee;i++) printf("%lld\n",eve[i].v);
    return 0;
}

 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;

int n;
#define maxn 200011
struct Point
{
    int x,y;
    bool operator < (const Point &b) const {return x<b.x;}
}a[maxn];

#define LL long long
LL ans=0;
int ord[maxn],rank[maxn],tmpord[maxn],sta[maxn],top,pre[maxn],suc[maxn];
void solve(int L,int R)
{
    if (L==R) {ord[L]=L;rank[L]=L;return;}
    const int mid=(L+R)>>1;
    solve(L,mid);
    cout<<L<< <<R<<:<<endl;
    top=0;
    for (int i=mid+1;i<=R;i++)
        if (!top || sta[top]>a[i].y) sta[++top]=a[i].y;
    for (int i=1;i<=top;i++) cout<<sta[i]<< ;cout<<"sta"<<endl;
    for (int i=L;i<=mid;i++) cout<<rank[i]<< ;cout<<"rank"<<endl;
    for (int i=L;i<=mid;i++) cout<<ord[i]<< ;cout<<"ord"<<endl;
    for (int i=L-1;i<=mid;i++) suc[i]=i+1;
    for (int i=L;i<=mid+1;i++) pre[i]=i-1;
    for (int i=L;i<=mid;i++)
    {
        int ul=1,ur=top+1;
        if (suc[rank[i]]<=mid) while (ul<ur)
        {
            int mid=(ul+ur)>>1;
            if (sta[mid]<a[ord[suc[rank[i]]]].y) ur=mid;
            else ul=mid+1;
        }
        else ul=1;
        int dl=0,dr=top;
        while (dl<dr)
        {
            int mid=(dl+dr+1)>>1;
            if (sta[mid]>a[i].y) dl=mid;
            else dr=mid-1;
        }
        cout<<a[i].y<< <<a[ord[suc[rank[i]]]].y<<:<<dl<< <<ul<<endl;
        ans+=dl-ul+1;
        suc[pre[rank[i]]]=suc[rank[i]];
        pre[suc[rank[i]]]=pre[rank[i]];
    }
        
    solve(mid+1,R);
    int i=L,j=mid+1,k=L;
    while (i<=mid && j<=R)
    {
        if (a[ord[i]].y<a[ord[j]].y) tmpord[k++]=ord[i++];
        else tmpord[k++]=ord[j++];
    }
    while (i<=mid) tmpord[k++]=ord[i++];
    while (j<=R) tmpord[k++]=ord[j++];
    for (int x=L;x<=R;x++) ord[x]=tmpord[x],rank[ord[x]]=x;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+1+n);
    for (int i=1;i<=n;i++) cout<<a[i].x<< <<a[i].y<<endl;cout<<endl;
    solve(1,n);
    printf("%lld\n",ans);
    return 0;
}

 

xxx

标签:spl   .so   find   nload   sca   clu   root   single   ++   

原文:http://www.cnblogs.com/Blue233333/p/7892555.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号