ZOJ Monthly, July 2015-H

这题先把边按起点排序，再把询问排序，从大到小处理询问，并且不断加入需要的边，保存终点的最大值和次大值，询问点-次大值就是该询问的答案。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<functional>
#include<vector>
using namespace std;
int team[5],tail,i,j,n,q,m,node[50005],a[50005],ans[50005];
struct rec
{
    int x,y;
}edg[50005];
bool cmp1(int i,int j){return a[i]<a[j];}
bool cmp2(rec a,rec b){return a.x<b.x;}
void add(int i)
{
    if (tail==0){team[++tail]=edg[i].y;return;}
    if (tail==1)
    {
        team[++tail]=edg[i].y;
        if (team[2]<team[1]){int t=team[1]; team[1]=team[2];team[2]=t;}
        return;
    }
    if (edg[i].y<team[2]) team[2]=edg[i].y;
    if (team[2]<team[1]){int t=team[1]; team[1]=team[2];team[2]=t;}
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&q))
    {
        for (i=1;i<=m;i++) scanf("%d%d",&edg[i].x,&edg[i].y);
        for (i=1;i<=q;i++) scanf("%d",&a[i]),node[i]=i;
        sort(node+1,node+q+1,cmp1);
        sort(edg+1,edg+m+1,cmp2);
        j=m; tail=0; memset(ans,0,sizeof(ans));
        for (i=q;i>=1;i--)
        {
            int now=a[node[i]];
            while(j>=0&&edg[j].x>=now) add(j),j--;
            while(tail>0&&team[tail]>now) tail--;
            if (tail==2) ans[node[i]]=now-team[tail];
        }
        for (i=1;i<=q;i++) printf("%d\n",ans[i]);
    }
}