本文共 1934 字，大约阅读时间需要 6 分钟。
任意找一个点做根， 然后找到距离这个根最远的点，然后以这个点做根，再找距离这个根最远的点，两个距离和就是 树的直径。
#include #include #include #include #include #include using namespace std;typedef long long LL;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 1000000 + 1000;int sum[maxn << 2];const int INF = 1<<30;int ncnt;int val[maxn];int pos[maxn];void up(int rt){ sum[rt] = min(sum[rt << 1], sum[rt << 1 | 1]);}void build(int l, int r, int rt){ sum[rt] = INF; if (l == r){ return; } int mid = (l + r) >> 1; build(lson); build(rson); up(rt);}void update(int key, int l, int r, int rt){ if (l == r){ sum[rt] = key; return; } int mid = (l + r) >> 1; if (key <= mid) update(key, lson); else update(key, rson); up(rt);}int ask(int L, int R, int l, int r, int rt){ if (L <= l&&r <= R) return sum[rt]; int ans = INF; int mid = (l + r) >> 1; if (L <= mid) ans = min(ans, ask(L, R, lson)); if (R > mid) ans = min(ans, ask(L, R, rson)); return ans;}void gao(int x){ int Min = INF; int ans=INF; for (int i = ncnt - 1; i >= 1; i--){ if (val[i] % x == 0) { printf("%d\n", i); return ; } if (val[i] % x < Min){ Min = val[i] % x; ans = i; } } printf("%d\n", ans);}void gao1(int x){ int l = 0; int r = x - 1; int ans = -1; while (l <= maxn){ if (r > maxn) r = maxn; int temp = ask(l, r, 0, maxn, 1); if(temp!=INF){ if (ans==-1||temp%x < ans%x) ans = temp; else if (temp%x == ans%x&&pos[temp]>pos[ans]) ans = temp; } l += x; r += x; } printf("%d\n", pos[ans]);}int main(){ char str[100]; int k; int cnt = 0; int T; while (scanf("%d",&T),T){ if(cnt) puts(""); ncnt = 1; build(0, maxn, 1); printf("Case %d:\n", ++cnt); while (T--){ scanf("%s%d", str, &k); if (str[0] == 'B'){ val[ncnt] = k; pos[k] = ncnt++; update(k, 0, maxn, 1); } else{ if(ncnt==1){ printf("-1\n"); } else if (k < 10000) gao(k); else gao1(k); } } } return 0;}
转载于:https://www.cnblogs.com/yigexigua/p/4072671.html