虽然看起来是求最短路，但因为条件的限制，可以转化为区间求最小值。
对于一条small path [a, b]，假设它的长度是len，它对区间[a, b]的影响就是：len-( sum[b]-sum[a-1] );(使区间[a,b]的原有长度变长或者变短，变长没有意义，所以我们只考虑变短的情况)，因为只能选择一条small path，所以对于每个查询[u, v]，就是要选择在区间[u, v]内，让原有长度减少最多的那条small path，即求区间最小值。
离线处理：
将查询和small path放在一起排序，按u从大到小，v从小到大排。
因为我们要从后往前扫，对于每个查询[u, v]，我们应当保证在本查询之前的所有[u', v']已经更新进去。
当u < v时，u < u', v' < v，树状数组minv[i]中记录的是以i为区间右端点的所有small path中len-( sum[b]-sum[a-1] )的最小值，答案为[u, v]的区间和+该最小值。
当u > v时，v' < v, u < u'，树状数组minv[i]中记录的是从i点走回i点（走了一个圈）的最小值。答案为最小值减去[u, v]的区间和。
------------------------以下吐槽--------------------------
本来以为不是很难的一道树状数组，结果折腾了一晚上……主要是对查询中u>v的情况处理总是各种出问题，之前我是想把1-N扩大一倍变成1-2N，这样对于查询中u>v的情况就可以转换成查询[ u, N+v ]。事实证明这样转换是不对的……画画图看看就知道为啥了。
然后我又想关于N轴对称把点翻转过去，还是1-2N，只不过把查询变成了[ u, 2N - v ]。还是各种出错orz……
最后实在没办法，老老实实的分开处理了……
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> #define LL long long int using namespace std; const int MAXN = << ;
const int INF = ;
long long int one = ; LL sum[MAXN]; //区间和
LL minv[MAXN];
LL ans[]; int N, M; struct node
{
int l, r;
LL val;
int id;
}; node D[ MAXN << ]; int lowbit( int x )
{
return x & ( -x );
} void Add( int x, LL val )
{
while ( x <= N )
{
minv[x] = min( minv[x], val );
x += lowbit(x);
}
return;
} LL Query( int x )
{
LL res = one << ;
while ( x > )
{
res = min( res, minv[x] );
x -= lowbit(x);
}
return res;
} bool cmp( node a, node b )
{
if ( a.l != b.l ) return a.l > b.l;
if ( a.r != b.r ) return a.r < b.r;
return a.id < b.id;
} int main()
{
//freopen( "in.txt", "r", stdin );
//freopen( "out.txt", "w", stdout );
while ( scanf( "%d%d", &N, &M ) == )
{
memset( minv, , sizeof(minv) ); sum[] = ;
for ( int i = ; i < N; ++i )
{
scanf( "%I64d", &sum[i] );
sum[i] += sum[i - ];
}
sum[N] = INF; int cnt = ;
for ( int i = ; i < M; ++i )
{
int a, b, c;
scanf( "%d%d%d", &a, &b, &c );
LL tmp;
if ( a > b )
tmp = (LL)c + sum[a - ] - sum[b - ];
else
tmp = (LL)c - sum[b - ] + sum[a - ];
D[cnt].l = a;
D[cnt].r = b;
D[cnt].val = tmp;
D[cnt].id = -;
++cnt;
} int Q;
scanf( "%d", &Q );
for ( int i = ; i < Q; ++i )
{
int a, b;
scanf( "%d%d", &a, &b );
D[cnt].id = i;
D[cnt].val = ;
D[cnt].l = a;
D[cnt].r = b;
++cnt;
} memset( ans, , sizeof(ans) );//之前少了这个，一直WA…好像上组数据会影响到下组数据中u=v的情况
sort( D, D + cnt, cmp ); for ( int i = ; i < cnt; ++i )
{
if ( D[i].l < D[i].r )
{
Add( D[i].r, D[i].val );
if ( D[i].id != - )
ans[ D[i].id ] = sum[ D[i].r - ] - sum[ D[i].l - ] + Query( D[i].r );
}
} for ( int i = ; i <= N; ++i )
minv[i] = one << ; for ( int i = ; i < cnt; ++i )
{
if ( D[i].l > D[i].r )
{
if ( D[i].id == - ) Add( D[i].r, D[i].val );
if ( D[i].id != - )
ans[ D[i].id ] = Query( D[i].r ) - sum[ D[i].l - ] + sum[ D[i].r - ];
}
} for ( int i = ; i < Q; ++i )
printf( "%d\n", (int)ans[i] );
}
return ;
}