(Zj) d712: The 3n + 1 problem

http://zerojudge.tw/ShowProblem?problemid=d712

這題是UVA加強版

我們要把每次做好的值紀錄下來

再開線段樹優化

就好了

對了, 如果值>1000000,不要傻傻的開map去存,會爛掉!!!

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <assert.h>
#include <map>
using namespace std;

int dp[20000002];
map<long long int, int> dp2;



struct Node {
Node* lc;
Node* rc;
int val;
int tag;
Node() {
lc=rc=NULL;
val=-1;
tag=0;
}
void pull() {
val=max(lc->val,rc->val);
tag=(lc->tag & rc->tag);
}
};

Node* root;

Node* Build(int L,int R) {
Node* node = new Node();
if (L==R) {
if (L!=1)node->val=1000;
else node->val=1;
return node;
}
int mid=(L+R)>>1;
node->lc=Build(L,mid);
node->rc=Build(mid+1,R);
node->pull();
return node;
}

void modify(Node* node,int L,int R,int pos,int Val) {
if (L==R) {
node->val=Val;
node->tag=1;
return;
}
int mid=(L+R)>>1;
if (node->lc->tag==0&&mid>=pos) modify(node->lc,L,mid,pos,Val);
if (node->rc->tag==0&&mid<pos) modify(node->rc,mid+1,R,pos,Val);
node->pull();
}

int query(Node* node,int L,int R,int l,int r) {
// cout<<L<<" ~ "<<R<<endl;
if (R<l || L>r) return -1;
else if (l<=L && R<=r) return node->val;
int mid=(L+R)>>1;
return max(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

int get_ans(long long int id) {
// cout<<id<<endl;
// cout<<id<<endl;
if (id<20000000&&dp[id]!=0) return dp[id];
// else if (dp2[id]!=0) return dp2[id];
else if (id > 10000000 && id%2==0) {
return get_ans(id/2)+1;
}
else if (id > 10000000 && id%2==1) return get_ans(3*id+1)+1;
else if (id==1) return dp[id] = 1;
else if (id%2==0) {
dp[id] = get_ans(id/2)+1;
if (id<=1000000) modify(root,1,1000000,id,dp[id]);
return dp[id];
}
else {
dp[id] = 2+get_ans((3*id+1)/2);
if (id<=1000000) modify(root,1,1000000,id,dp[id]);
return dp[id];
}
}

void swap(int& a,int &b) {
int t=a;
a=b;
b=t;
}

int main () {
root = Build(1,1000000);
int i,j;
while (scanf("%d %d",&i,&j) != EOF) {
bool log=false;
if (i>j) swap(i,j),log=true;
if (query(root,1,1000000,i,j) == 1000) {
for (int x=i;j>=x;x++) {
if (dp[x]==0) {
get_ans(x);
// modify(root,1,1000000,x,dp[x]);
}
}

}
printf("%d %d %d\n",(log?j:i),(log?i:j),query(root,1,1000000,i,j));
}
}