ZOJ3724 树状数组+离线处理

题目看似一个最短路问题，仔细分析一下会发现，问题可以转化为求区间最值问题。区间最值一直递增或者递减的话，可以直接用树状数组实现。

询问可以分为两种情况：

U>V 这是比较复杂的情况，然后路径只有一种:U->u->v->V，其中u>=U ,v<=V。u-v是选择的一条小路。

然后可以从后往前处理，从n到1枚举起点。这样能够保证处理到U的时候，u->v这些边都已经被处理了。处理U的时候，先把u=U的边用于更新[v,i]这段区间，因为所有在[v,i]内的V都可能受到u->v这条边的影响。边权为Sum[U]-Sum[v]+edge[u->v].cost。更新完成好，进行查询操作。单点查询V，区间[V,U]的最小值-(Sum[U]-Sum[V])就是答案。

U<V是比较好处理的情况。差不多的思想。从1到n枚举终点，进行离线处理。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std ;

#define SZ(x)  (int)((x).size())
#define For(i , forN) for(int i = 0 ; i < (forN) ; ++i)
#define Fori(i,si,forN) for(int i=(si);i < (forN); i++)
#define sf scanf
#define pf printf
#define pb push_back
#define showCase(x) printf("Case %d: ",(x));


//
#define lc l,mid,x<<1
#define rc mid+1,r,x<<1|1
#define cmax(x,y) ((x)>(y)?(x):(y))
#define cmin(x,y) ((x)>(y)?(y):(x))
#define mp(x,y) make_pair((x),(y))
#define lowbit(x) ((x)&(-x))

#define DEBUG

#ifdef DEBUG
#define Dctn(x) cout<<#x<<"="<<x<<"  "
#define Dct(x) cout<<x<<" "
#define Dl cout<<endl
#endif

//
typedef pair < int ,int > pii;
typedef pair < int , pii > piii;
typedef vector < int > vi;
typedef vector < pii > vpii;
typedef long long LL;

const LL Inf = (~0ull)>>1;
const int Maxn=110000;
vpii quest[Maxn][2];
vpii E[Maxn][2];//j表示是否以i为终点的边，第三维表示{起点，距离，问题的编号}。
LL sum[Maxn];
int n,m,Q;
LL node[Maxn],Res[Maxn<<2];

void updateBIT(int x,int val)
{
    while(x)
    {
        node[x]=cmin(node[x],val);
        x-=lowbit(x);
    }
}

LL queryBIT(int x)
{
    LL res=Inf;
    while(x<=n)
    {
        res=cmin(res,node[x]);
        x+=lowbit(x);
    }
    return res;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int tmp,u,v;
        Fori(i,2,n+1)
        {
            sf("%d",&tmp);
            sum[i]=sum[i-1]+tmp;
            E[i][0].clear();E[i][1].clear();
            quest[i][0].clear();    quest[i][1].clear();
        }
        For(i,m)
        {
            sf("%d%d%d",&u,&v,&tmp);
            if(u<v)
            E[v][1].pb(mp(u,tmp));
            else
            E[u][0].pb(mp(v,tmp));
        }
        sf("%d",&Q);
        For(i,Q)
        {
            sf("%d%d",&u,&v);
            if(u<v)         quest[v][1].pb(mp(u,i));
            else if(u==v)   Res[i]=0;
            else            quest[u][0].pb(mp(v,i));
        }
        Fori(i,1,n+1)   node[i]=Inf;
        for(int i=n;i>=1;i--)
        {
            For(j,SZ(E[i][0]))
            {
                v=E[i][0][j].first;
                updateBIT(n-v+1,sum[i]-sum[v]+E[i][0][j].second);
            }
            For(j,SZ(quest[i][0]))
            {
                v=quest[i][0][j].first;
                Res[quest[i][0][j].second]=queryBIT(n-v+1)-(sum[i]-sum[v]);
            }
        }
        Fori(i,1,n+1)   node[i]=0;
        Fori(i,1,n+1)
        {
            For(j,SZ(E[i][1]))
            {
                u=E[i][1][j].first;
                updateBIT(u,E[i][1][j].second-(sum[i]-sum[u]));
            }
            For(j,SZ(quest[i][1]))
            {
                u=quest[i][1][j].first;
                Res[quest[i][1][j].second]=sum[i]-sum[u]+queryBIT(u);
            }
        }
        For(i,Q)    pf("%lld
",Res[i]);
    }
    return 0;
}