zoj 3724 樹狀陣列經典

2022-11-27 14:07:56 字數 1419 閱讀 1335

問題: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

*/