50求救,结构体开5e6后是个数据RE,开6e6后十个数据爆内存

P1908 逆序对

白手 @ 2020-09-28 17:25:07

#include<bits/stdc++.h>
#define INF 2147483647
#define  ll long long
using namespace std;
const int Max=5e5+20;
const int Maxn=5e6+20;
const int mod=10007;
inline int read()
{
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');    return x*f;
}
struct edgu
{

    ll v,lr,rr;
}tree[Maxn];
int cnt=1;
ll search_tree(int l,int L,int R,int nood)
{
    if(nood==0) return 0;
    if(L>R) return 0;
    if(l<=L) return tree[nood].v;
    int mid=(L+R)>>1;
    ll num=0;
    if(l<=mid) num+=search_tree(l,L,mid,tree[nood].lr);
    num+=search_tree(l,mid+1,R,tree[nood].rr);
    return num;
}
void insert_tree(int pos,int l,int r,int nood)
{
    if(l==r) {tree[nood].v++;return;}
    if(l>r) return;
    int mid=(l+r)>>1;
    if(pos<=mid)
    {
        if(tree[nood].lr==0) tree[nood].lr=++cnt;
            insert_tree(pos,l,mid,tree[nood].lr);
    }
    else
    {
        if(tree[nood].rr==0) tree[nood].rr=++cnt;
        insert_tree(pos,mid+1,r,tree[nood].rr);
    }
    tree[nood].v=tree[tree[nood].lr].v+tree[tree[nood].rr].v;
}
int main()
{
  int n=read(),a;
  ll ans=0;
  for(int i=1;i<=n;i++)
  {
      a=read();
      ans+=search_tree(a+1,1,1000000000,1);
      insert_tree(a,1,1000000000,1);
  }
  cout<<ans<<endl;
}

by fresh_boy @ 2020-09-28 17:39:52

废话,相当于你存了3个10^6的longlong 数组,能不爆?


by xiejinhao @ 2020-09-28 18:11:07

明明可以归并或者树状数组,为啥用线段树?

再说了 5e5 的数据线段树的空间也开不下啊,就算开的下时间上也不允许啊?


by xiejinhao @ 2020-09-28 18:12:33

@白手


by 白手 @ 2020-09-28 18:48:11

@xiejinhao 都试试嘛,改int过了


by 白手 @ 2020-09-28 18:49:24

@xiejinhao 这是动态开点,是能存下的哦


|