http://www.rqnoj.cn/problem/707

做法如下:

1,求每个点,A和B出发,会到哪里

这里可以用set做一下,也可以向我一样写个链表[Line 23-36/110-208]

类似线段树的东西,按高度排序,然后搞个链表,每次删掉一个点,然后找它左右的最小/最大

set和上面的差不多....不过复杂度会高一点,我这个是O(n)的,我怕set T掉了...

RQNOJ还是挺慢的

2,组建树

把每个点拆分成两个形态,一个是A开始走,一个是B开始走

建个图,发现是三个树(最后一个点/倒数第二个点A出发)

3,dfs,计算树上各点的权值(A走了多少/B走了多少),并倍增

4,每次询问一个距离和一个起点,这时候只要用倍增来判定一下是不是超过了(和二分差不多的样子)规定的距离就行了

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int next1[100005],next2[100005];
int h[100005];
struct place
{
    int height;
    int id;
    place * last;
    place * next;
    friend bool operator < (const place &a,const place &b)
    {
        return a.height<b.height;
    }
};
place t[100005];
place * null;
place * p[100005];
struct edge
{
    int y;
    edge * next;
};
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
edge * li[200005];
void insert_edge(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
long long sum[200005][2];
int up[200005][25];
void dfs(int x,int c)
{
    int i;
    for (i=1;i<19;i++)
    {
        if (up[x][i-1]==-1)
        {
            up[x][i]=-1;
        }
        else
        {
            up[x][i]=up[up[x][i-1]][i-1];
        }
    }
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        sum[t->y][!c]=sum[x][!c]+abs(h[t->y/2]-h[x/2]);
        sum[t->y][c]=sum[x][c];
        up[t->y][0]=x;
        dfs(t->y,!c);
    }
}
int q_ans1,q_ans2;
void query(int x,int s)
{
    if (sum[s][0]+sum[s][1]<=x)
    {
        q_ans1=sum[s][0];
        q_ans2=sum[s][1];
    }
    int now=s;
    int i;
    for (i=18;i>=0;i--)
    {
        if (up[now][i]==-1) continue;
        int t=up[now][i];
        if (sum[s][0]+sum[s][1]-sum[t][0]-sum[t][1]<=x)
        {
            now=t;
        }
    }
    q_ans1=sum[s][0]-sum[now][0];
    q_ans2=sum[s][1]-sum[now][1];
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&h[i]);
        t[i].id=i;
        t[i].height=h[i];
    }
    sort(t,t+n);
    null=&t[n];
    for (i=0;i<n;i++)
    {
        if (i!=0)
        {
            t[i].last=&t[i-1];
        }
        else
        {
            t[i].last=null;
        }
        if (i!=n-1)
        {
            t[i].next=&t[i+1];
        }
        else
        {
            t[i].next=null;
        }
        p[t[i].id]=&t[i];
    }
    for (i=0;i<n;i++)
    {
        p[i]->last->next=p[i]->next;
        p[i]->next->last=p[i]->last;
        if (p[i]->next==null)
        {
            if (p[i]->last==null)
            {
                next1[i]=-1;
                next2[i]=-1;
                continue;
            }
            else
            {
                next1[i]=p[i]->last->id;
                p[i]->last=p[i]->last->last;
            }
        }
        else
        {
            if (p[i]->last==null)
            {
                next1[i]=p[i]->next->id;
                p[i]->next=p[i]->next->next;
            }
            else
            {
                if (p[i]->next->height-p[i]->height<p[i]->height-p[i]->last->height)
                {
                    next1[i]=p[i]->next->id;
                    p[i]->next=p[i]->next->next;
                }
                else
                {
                    next1[i]=p[i]->last->id;
                    p[i]->last=p[i]->last->last;
                }
            }
        }
        if (p[i]->next==null)
        {
            if (p[i]->last==null)
            {
                next2[i]=-1;
            }
            else
            {
                next2[i]=p[i]->last->id;
            }
        }
        else
        {
            if (p[i]->last==null)
            {
                next2[i]=p[i]->next->id;
            }
            else
            {
                if (p[i]->next->height-p[i]->height<p[i]->height-p[i]->last->height)
                {
                    next2[i]=p[i]->next->id;
                }
                else
                {
                    next2[i]=p[i]->last->id;
                }
            }
        }
    }
    for (i=0;i<n;i++)
    {
        if (next1[i]!=-1) insert_edge(next1[i]*2+1,i*2+0);
        if (next2[i]!=-1) insert_edge(next2[i]*2+0,i*2+1);
    }
    memset(up,-1,sizeof(up));
    dfs(n*2-1,1);
    dfs(n*2-2,0);
    if (n!=1) dfs(n*2-3,1);
    int x0;
    scanf("%d",&x0);
    int b_ans1=0,b_ans2=1,b_ans_id=0;
    for (i=0;i<n;i++)
    {
        query(x0,i*2+1);
        if ((q_ans1==0)&&(q_ans2==0)) continue;
        if ((long long)b_ans1*q_ans2<(long long)b_ans2*q_ans1)
        {
            b_ans_id=i;
            b_ans1=q_ans1;
            b_ans2=q_ans2;
        }
        else if ((long long)b_ans1*q_ans2==(long long)b_ans2*q_ans1)
        {
            if (h[i]>h[b_ans_id])
            {
                b_ans_id=i;
                b_ans1=q_ans1;
                b_ans2=q_ans2;
            } 
        }
    }
    printf("%d\n",b_ans_id+1);
    int m;
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        int s,x;
        scanf("%d%d",&s,&x);
        s--;
        query(x,s*2+1);
        printf("%d %d\n",q_ans2,q_ans1);
    }
    return 0;
}