Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这题难道不是dp+线段树吗。。

Posted by Flowersea at 2017-05-05 23:42:56 on Problem 1207
```#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
const ll MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e8 + 7;

ll dp[MAXN];

ll dfs(ll x) {
if (dp[x]) return dp[x];
if (x & 1) dp[x] = dfs(x * 3 + 1) + 1;
else dp[x] = dfs(x / 2) + 1;
return dp[x];
}

ll tree[MAXN];

void pushup(int rt) {
tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}

void build(int l, int r, int rt) {
if (l == r) {
tree[rt] = dp[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}

int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return tree[rt];
int m = (l + r) >> 1;
int res = 0;
if (L <= m) res = max(res, query(L, R, lson));
if (R > m) res = max(res, query(L, R, rson));
return res;
}

int main() {
ios::sync_with_stdio(false), cin.tie(0);
dp[1] = 1;
rep(i, 2, 10001) if (!dp[i]) dfs(i);
build(1, 10000, 1);
int l, r;
while (cin >> l >> r) {
cout << l << ' ' << r << ' ';
if (l > r) swap(l, r);
cout << query(l, r, 1, 10000, 1) << endl;
}
return 0;
}```

Followed by: