@[hyfhaha](/space/show?uid=58711) 我帮你算了算内存占用情况。
在`tree`结构体数组中,一个变量占用的空间就有11个`int`,因此这个数组总的占用空间就达到了 $ 11 \times 4 \times 10^6 = 4.4 times 10^7 $ 个`int`变量。
128M的内存空间大约能开 $ 2.5 \times 10^7 $ 个`int`变量。
by StudyingFather @ 2019-04-17 13:25:01
是 $ 4.4 \times 10^7 $ 个`int`变量。
by StudyingFather @ 2019-04-17 13:25:23
@[StudyingFather](/space/show?uid=22030) 不太对吧
那么请问下面这份代码的空间?
https://www.luogu.org/recordnew/show/14831019
修改了一点,不要在意代码长度,所有类型我都改成了int,没有垃圾回收了
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define _Print(X, Y)
const int MAXN = 4000000 + 10; // 空间一样
const int TAG_NONE = 1000000000;
struct Treap {
struct Node {
int l,r;
int pri;
int val;
int sum;
int lm, rm, mm; // left-max_sum; right-max_sum; middle-max_sum;
int rev; // 改成int
int tag;
int siz;
} tree[MAXN];
stack<int> S;
int root;
Treap() {
for(int i = MAXN - 1; i >= 1; i --) {
S.push(i);
}
}
int random() {
return rand() ^ (rand() << 4) ^ (rand() << 8) ^ (rand() << 12);
}
int newnode(int k) {
int top = S.top();
S.pop();
tree[top].val = k;
tree[top].pri = random();
tree[top].l = tree[top].r = 0;
tree[top].rev = false;
tree[top].tag = TAG_NONE;
tree[top].sum = k;
tree[top].lm = tree[top].rm = max(k, 0);
tree[top].mm = k;
tree[top].siz = 1;
return top;
}
void delnode(int node) { // 删掉了
}
...
} T;
int n, m;
int main() {
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i = 1; i <= n; i ++) {
int a;
cin>>a;
T.root = T.merge(T.root, T.newnode(a));
}
string mode;
int pos, tot;
for(int i = 1; i <= m; i ++) {
//T._Print(T.root, "(Main)");
cin>>mode;
if(mode == "INSERT") {
cin>>pos>>tot;
int node = 0;
for(int i = 1; i <= tot; i ++) {
int a;
cin>>a;
node = T.merge(node, T.newnode(a));
}
T.insert(pos, node);
}
else if(mode == "DELETE") {
cin>>pos>>tot;
T.erase(pos, pos + tot - 1);
}
else if(mode == "MAKE-SAME") {
cin>>pos>>tot;
int val;
cin>>val;
T.make_same(pos, pos + tot - 1, val);
}
else if(mode == "REVERSE") {
cin>>pos>>tot;
T.reverse(pos, pos + tot - 1);
}
else if(mode == "GET-SUM") {
cin>>pos>>tot;
int ans = T.get_sum(pos, pos + tot - 1);
// if(ans == 984)
// cout<<">>> Warning: GET-SUM"<<endl;
// if(last_ans == 984)
// cout<<">>> Error: GET-SUM"<<endl;
cout<<ans<<endl;
}
else if(mode == "MAX-SUM") {
int ans = T.max_sum();
// if(ans == 984)
// cout<<">>> Warning: MAX-SUM"<<endl;
// if(last_ans == 984)
// cout<<">>> Error: MAX-SUM"<<endl;
// if(ans == 0 && last_ans == 984) {
// cout<<">>> Catch: MAX-SUM"<<endl;
// T.Print(T.root, "Catch");
// }
cout<<ans<<endl;
}
else if(mode == "EXIT")
break;
}
return 0;
}
```
by longlongzhu123 @ 2019-04-17 13:35:04
然而@[hyfhaha](/space/show?uid=58711) 好像是M在了构造函数上?(逃)
by longlongzhu123 @ 2019-04-17 13:41:12
写了垃圾回收,空间降下来了,谢谢各位大佬
@[command_block](/space/show?uid=58705) @[longlongzhu123](/space/show?uid=57525) @[StudyingFather](/space/show?uid=22030)
by hyfhaha @ 2019-04-17 13:53:23
Good luck!
by 666yuchen @ 2019-04-17 14:00:49