蒟蒻求助:为什么左右儿子用数组存就能AC,用结构体就会连样例都过不去

P2839 [国家集训队] middle

5_Lei @ 2022-09-23 07:41:06

数组版:

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e4+5;

typedef long long ll;

#define ls(rt) son[rt][0]
#define rs(rt) son[rt][1]

ll R()
{
    ll x = 0,f = 1;
    char c = getchar();
    while(c>'9' || c<'0')
    {
        if(c=='-')f=-1;
        c = getchar();
    }
    while(c>='0' && c<='9')
    {
        x = (x<<1)+(x<<3)+(c^48);
        c = getchar();
    }
    return x*f;
}

struct Tree
{
    ll sum,lmx,rmx;
    Tree(){sum = lmx = rmx = 0;}
}t[maxn<<5];

ll n,cnt,tot,a[maxn],b[maxn],c[10],rt[maxn],son[maxn<<5][2];

vector<ll>pos[maxn];

Tree operator + (const Tree &a,const Tree &b)
{
    Tree c;
    c.sum = a.sum + b.sum;
    c.lmx = max(a.lmx,a.sum + b.lmx);
    c.rmx = max(b.rmx,b.sum + a.rmx);
    return c;
}

void pushup(ll rt){t[rt] = t[ls(rt)] + t[rs(rt)];}

void build(ll &rt,ll l,ll r)
{
    int lst  = rt;rt = ++tot;
    t[rt] = t[lst];
    if(l==r)
    {
        t[rt].sum = 1,t[rt].lmx = 1,t[rt].rmx = 1;
        return;
    }
    ll mid = (l+r)>>1;
    build(ls(rt),l,mid);
    build(rs(rt),mid+1,r);
    pushup(rt);
}

void update(ll &rt,ll l,ll r,ll x,ll d)
{
    int lst = rt;rt = ++tot;
    t[rt] = t[lst];
    ls(rt) = ls(lst),rs(rt) = rs(lst);
    if(l == r)
    {
        t[rt].sum = t[rt].lmx = t[rt].rmx = d;
        return;
    }
    ll mid = (l+r)>>1;
    if(x <= mid)update(ls(rt),l,mid,x,d);
    else update(rs(rt),mid+1,r,x,d);
    pushup(rt);
}

Tree query(ll rt,ll l,ll r,ll L,ll R)
{
    if(L <= l && r <= R)return t[rt];
    ll mid = (l+r)>>1;
    if(R <= mid)return query(ls(rt),l,mid,L,R);
    else if(mid < L)return query(rs(rt),mid+1,r,L,R);
    else return query(ls(rt),l,mid,L,R) + query(rs(rt),mid+1,r,L,R);
}

bool Query(ll rt,ll a,ll b,ll c,ll d)
{
    ll sum = 0;
    if(b+1 <= c-1)sum += query(rt,1,n,b+1,c-1).sum;
    sum += query(rt,1,n,a,b).rmx;
    sum += query(rt,1,n,c,d).lmx;
    return sum >= 0;
}

void Lei()
{
    n = R();
    for(int i = 1 ; i <= n ; i++)a[i] = R(),b[i] = a[i];
    sort(b+1,b+n+1);
    cnt = unique(b+1,b+n+1)-b-1;
    for(int i = 1 ; i <= n ; i++)
    {
        a[i] = lower_bound(b+1,b+cnt+1,a[i])-b;
        pos[a[i]].push_back(i);
    }
    build(rt[1],1,n);

    for(int i = 2 ; i <= cnt ; i++)
    {
        rt[i] = rt[i-1];
        for(int j = 0 ; j < pos[i-1].size() ; j++)
            update(rt[i],1,n,pos[i-1][j],-1);
    }
    ll Q = R(),last = 0;
    for(int i = 1 ; i <= Q ; i++)
    {
        c[1] = (R()+last)%n;
        c[2] = (R()+last)%n;
        c[3] = (R()+last)%n;
        c[4] = (R()+last)%n;
        sort(c+1,c+5);
        c[1] += 1,c[2] += 1,c[3] += 1,c[4] += 1; 
        ll l = 1,r = n,ans = 1;
        while(l <= r)
        {
            ll mid = (l+r)>>1;
            if(Query(rt[mid],c[1],c[2],c[3],c[4]))l = mid+1,ans = mid;
            else r = mid-1;
        }
        printf("%lld\n",last = b[ans]);
    }
}

int main()
{
    Lei();
    return 0;
}

结构体版:

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e4+5;

typedef long long ll;

#define ls(rt) t[rt].lson
#define rs(rt) t[rt].rson

ll R()
{
    ll x = 0,f = 1;
    char c = getchar();
    while(c>'9' || c<'0')
    {
        if(c=='-')f=-1;
        c = getchar();
    }
    while(c>='0' && c<='9')
    {
        x = (x<<1)+(x<<3)+(c^48);
        c = getchar();
    }
    return x*f;
}

struct Tree
{
    ll lson,rson,sum,lmx,rmx;
    Tree(){lson = rson = sum = lmx = rmx = 0;}
}t[maxn<<8];

ll n,cnt,tot,a[maxn],b[maxn],c[10],rt[maxn];

vector<ll>pos[maxn];

Tree operator + (const Tree &a,const Tree &b)
{
    Tree c;
    c.sum = a.sum + b.sum;
    c.lmx = max(a.lmx,a.sum + b.lmx);
    c.rmx = max(b.rmx,b.sum + a.rmx);
    return c;
}

void pushup(ll rt){t[rt] = t[ls(rt)] + t[rs(rt)];}

void build(ll &rt,ll l,ll r)
{
    int lst  = rt;rt = ++tot;
    t[rt] = t[lst];
    if(l==r)
    {
        t[rt].sum = 1,t[rt].lmx = 1,t[rt].rmx = 1;
        return;
    }
    ll mid = (l+r)>>1;
    build(ls(rt),l,mid);
    build(rs(rt),mid+1,r);
    pushup(rt);
}

void update(ll &rt,ll l,ll r,ll x,ll d)
{
    int lst = rt;rt = ++tot;
    t[rt] = t[lst];
    if(l == r)
    {
        t[rt].sum = t[rt].lmx = t[rt].rmx = d;
        return;
    }
    ll mid = (l+r)>>1;
    if(x <= mid)update(ls(rt),l,mid,x,d);
    else update(rs(rt),mid+1,r,x,d);
    pushup(rt);
}

Tree query(ll rt,ll l,ll r,ll L,ll R)
{
    if(L <= l && r <= R)return t[rt];
    ll mid = (l+r)>>1;
    if(R <= mid)return query(ls(rt),l,mid,L,R);
    else if(mid < L)return query(rs(rt),mid+1,r,L,R);
    else return query(ls(rt),l,mid,L,R) + query(rs(rt),mid+1,r,L,R);
}

bool Query(ll rt,ll a,ll b,ll c,ll d)
{
    ll sum = 0;
    if(b+1 <= c-1)sum += query(rt,1,n,b+1,c-1).sum;
    sum += query(rt,1,n,a,b).rmx;
    sum += query(rt,1,n,c,d).lmx;
    return sum >= 0;
}

void Lei()
{
    n = R();
    for(int i = 1 ; i <= n ; i++)a[i] = R(),b[i] = a[i];
    sort(b+1,b+n+1);
    cnt = unique(b+1,b+n+1)-b-1;
    for(int i = 1 ; i <= n ; i++)
    {
        a[i] = lower_bound(b+1,b+cnt+1,a[i])-b;
        pos[a[i]].push_back(i);
    }
    build(rt[1],1,n);

    for(int i = 2 ; i <= cnt ; i++)
    {
        rt[i] = rt[i-1];
        for(int j = 0 ; j < pos[i-1].size() ; j++)
            update(rt[i],1,n,pos[i-1][j],-1);
    }
    ll Q = R(),last = 0;
    for(int i = 1 ; i <= Q ; i++)
    {
        c[1] = (R()+last)%n;
        c[2] = (R()+last)%n;
        c[3] = (R()+last)%n;
        c[4] = (R()+last)%n;
        sort(c+1,c+5);
        c[1] += 1,c[2] += 1,c[3] += 1,c[4] += 1; 
        ll l = 1,r = n,ans = 1;
        while(l <= r)
        {
            ll mid = (l+r)>>1;
            if(Query(rt[mid],c[1],c[2],c[3],c[4]))l = mid+1,ans = mid;
            else r = mid-1;
        }
        printf("%lld\n",last = b[ans]);
    }
}

int main()
{
    Lei();
    return 0;
}

by Error_Eric @ 2022-09-23 08:40:33

@5_Lei 你 lson 在哪里赋值过了.jpg


by Error_Eric @ 2022-09-23 08:43:53

@5_Lei 你要么左节点 (rt>>1) ,右节点 (rt>>1|1) ,要么维护一个 cntbuild() 往下递归之前先 t[rt].lson=++cnt,t[rt].rson=++cnt


by 5_Lei @ 2022-09-23 09:15:52

@Error_Eric 蒟蒻写的动态开点,问题已经解决了,是pushup写挂了,结构体没pushup左右儿子,但还是感谢大佬%%%


by Error_Eric @ 2022-09-23 10:54:28

@5_Lei 现在是我不会了/kk,动态开点不是要开点的时候手动维护左右儿子吗,为什么没见到你维护左右儿子呢/kk?


by Error_Eric @ 2022-09-23 10:57:14

我不是大佬,我才是蒟蒻/kk。


by 5_Lei @ 2022-09-23 10:58:41

@Error_Eric 数组版手动维护了,结构体直接用结构体赋值了


by 5_Lei @ 2022-09-23 10:59:51

结构体版的pushup因为重载了一下+运算符,忘了更新左右儿子,导致样例都过不去


|