关于内存问题

樱洛CHANGE @ 2021-09-07 16:09:14

const int N=1e6+5,M=1e9+5;
int n,m,a[N];
class SegmentTree{
    private:
        int cnt;
        class Node{
            public:
                int ls,rs,val;
                ll sum;
                Node():ls(0),rs(0),val(0),sum(0){}
        }t[N*5];
        #define mid (l+((r-l)>>1))
        inline void Pushup(rint p){
            t[p].val=t[t[p].ls].val+t[t[p].rs].val;
            t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
        }
    public:
        int root;
        SegmentTree():cnt(0),root(0){}
        inline void Change(rint &p,rint l,rint r,rint pos,rint k){
            if(l>pos||r<pos) return ;
            if(!p) p=++cnt;
            if(l==r) return t[p].val+=k,t[p].sum+=(ll)pos*k,void();
            Change(t[p].ls,l,mid,pos,k),Change(t[p].rs,mid+1,r,pos,k),Pushup(p);
        }
        inline int Asknum(rint p,rint l,rint r,rint x,rint y){
            if(l>y||r<x||!p) return 0;
            if(l>=x&&r<=y) return t[p].val;
            return Asknum(t[p].ls,l,mid,x,y)+Asknum(t[p].rs,mid+1,r,x,y);
        }
        inline ll Asksum(rint p,rint l,rint r,rint x,rint y){
            if(l>y||r<x||!p) return 0ll;
            if(l>=x&&r<=y) return t[p].sum;
            return Asksum(t[p].ls,l,mid,x,y)+Asksum(t[p].rs,mid+1,r,x,y);
        }
}t;

#define int long long
#define mid ((l+r)>>1)
using namespace std;
int n,m,s[10000001];
int L[10000001],R[10000001],siz[10000001],val[10000001],tot=1,rt=1;
void push_up(int x)
{
    siz[x]=siz[L[x]]+siz[R[x]];
    val[x]=val[L[x]]+val[R[x]];
}
void add(int &x,int l,int r,int to,int v)
{
    if(r<to||l>to)return ;
    if(x==0)x=++tot;
    if(l==r)
    {
        siz[x]+=v;
        val[x]+=l*v;
        return ;
    }
    add(L[x],l,mid,to,v);
    add(R[x],mid+1,r,to,v);
    push_up(x);
}
int query(int x,int l,int r,int v)
{
    if(r<=v)return 0;
    if(l>v)return siz[x];
    if(!x)return 0;
    return query(L[x],l,mid,v)+query(R[x],mid+1,r,v);
}
int query_(int x,int l,int r,int v)
{
    if(r<=v)return val[x];
    if(l>v)return 0;
    if(!x)return 0;
    return query_(L[x],l,mid,v)+query_(R[x],mid+1,r,v);
}

by 樱洛CHANGE @ 2021-09-07 17:11:36

@KnightL 您要不去提交记录看看我die码/dk

by KEBrantily @ 2021-09-07 17:15:05

在看了在看了

by 樱洛CHANGE @ 2021-09-07 17:24:57

@KnightL 多谢您了/qq/qq

by KEBrantily @ 2021-09-07 17:51:02

找到问题了！！！

你把 class Node 里的四个变量开成四个全局数组就行了！！！

by KEBrantily @ 2021-09-07 17:51:53

我猜大概是放到里面和外面计内存的方式不同。

by KEBrantily @ 2021-09-07 17:53:29

您的代码被我蹂躏成这个样子我才发现了问题。

还用小号贡献了 114514+ 次提交。

人都麻了

#include<bits/stdc++.h>
#define awa 2147483647
#define zhale exit(0)
#define re register
#define rint re int

using namespace std;
/*Shioiri Kukuri*/
typedef long long ll;
#define rll re ll
#define rqwq re qwq

int read(){
  int s=0,w=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
  return s*w;
}

const int N=1e6+5,M=1e9+10;
int n,m,a[N],cnt;
int ls[N<<2],rs[N<<2],val[N<<2];
ll sum[N<<2];
#define mid (l+((r-l)>>1))
inline void Pushup(rint p){
    val[p]=val[ls[p]]+val[rs[p]];
    sum[p]=sum[ls[p]]+sum[rs[p]];
}
int root=0;
inline void Change(rint &p,rint l,rint r,rint pos,rint k){
    if(l>pos||r<pos) return ;
    if(!p) p=++cnt;
    if(l==r) return val[p]+=k,sum[p]+=(ll)pos*k,void();
    if(pos<=mid) Change(ls[p],l,mid,pos,k);
  else Change(rs[p],mid+1,r,pos,k);
  Pushup(p);
}
inline int Asknum(rint p,rint l,rint r,rint x,rint y){
    if(l>y||r<x||!p) return 0;
    if(l>=x&&r<=y) return val[p];
    return Asknum(ls[p],l,mid,x,y)+Asknum(rs[p],mid+1,r,x,y);
}
inline ll Asksum(rint p,rint l,rint r,rint x,rint y){
    if(l>y||r<x||!p) return 0;
    if(l>=x&&r<=y) return sum[p];
    return Asksum(ls[p],l,mid,x,y)+Asksum(rs[p],mid+1,r,x,y);
}

inline bool Ask(rint c,rint s)
 {
  int num=0;ll sum=0;
    num=Asknum(1,1,M,s,M),sum=s?Asksum(1,1,M,1,s-1):0;
    return sum>=(c-num)*1ll*s;
}

signed main(){
  n=read(),m=read();
    for(rint i=1,c,s;i<=m;++i)
    {
        re char op;
        cin>>op,c=read(),s=read();
        if(op=='U')
        {
            if(a[c]) Change(root,1,M,a[c],-1);
            a[c]=s;
            if(a[c]) Change(root,1,M,a[c],1);
        }
        else puts(Ask(c,s)?"TAK":"NIE");
    }
    return (0-0);
}

by ftiasch @ 2021-09-07 18:03:55

@樱洛CHANGE 我其实不确定您说的『小』和『大』相对来说是多少。

但是目前可以公开的情报是，因为内存对齐的召唤，sizeof(Node) == 24. 而 3 个 int 和 1 个 long long 只占 3 * sizeof(int) + 1 * sizeof(long long) = 20.

所以放在 struct 里面确实会大一点儿。

by 樱洛CHANGE @ 2021-09-07 19:40:11

@ftiasch 大是指实际内存比计算出来的理论内存大了两倍多。。

by 樱洛CHANGE @ 2021-09-07 19:41:31

@ftiasch 所以也不至于这么离谱啊。。。

by 樱洛CHANGE @ 2021-09-07 19:43:42

@KnightL 麻烦您了/qq，话说这么离谱的吗，我之前一直这么写。。。