問題：n個點，對於每個點i，都有一條連向i+1的有向邊，另外有m條其他的有向邊，有q個詢問（u，v）求u到v的最短路
將m條有向邊和q個詢問對所表示的點對一起排序，（u，v）u大的排前，u一樣的v小的排前，u和v一樣大的先處理插入的再處理詢問的；
邊插入邊詢問；
樹狀陣列裡存的是右端點在v之後的詢問的結果的差值
（1）對於（u，v）uv) 的那些還沒插入，樹狀陣列存mat[u1][v1]-(d[v1]-d[u1])的最小值，查詢時在加上(d[v]-d[u])
（2）對於（u，v）u>v的這種邊，保證在查詢到（u，v）之前，所有(u2,v2) v2
所以要通過排序來操作
#include #include #include #include using namespace std;typedef long long ll;
const int maxn = 100005;
const int maxm = 200010;
const int maxt = 200010;
const ll inf = (1ll<<60);
struct node
}p[maxn+maxm+maxt];
ll s[maxn],res[maxt];
ll b[maxn];
int n;
int lowbit(int x)
void update(int x,ll val)
}ll query(int x)
return res;
}int main()
for(i = 0; i < m; i++)
int t;scanf("%d",&t);
for( ; i < m+t; i ++)
sort(p,p+m+t);
// for(int i = 0; i < m+t; i++)cout << p[i].u << " " << p[i].v << " " << p[i].ind << " " << p[i].kind << endl;
memset(b,0,sizeof(b));
memset(res,0,sizeof(res));//當u == v時距離為0
for(int i = 0; i < m+t; i++)
for(int i = 0; i <= n+1;i++)b[i] = inf;
for(int i = 0; i < m+t; i++)
}for(int i = 0; i < t; i++)
printf("%lld\n",res[i]);
}return 0;}/*
5 31 2 3 4
2 4 2
1 3 2
5 1 3
51 4
4 23 1
1 31 5
*/