本地对的交上去RE

@eee_hoho  2019-04-28 08:43 回复
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct ff
{
    int lc,rc,val;  
}s[40000500];
int n,m,a[40000500],rt[40000500],node_cnt;
int build(int &k,int l,int r)
{
    k=++node_cnt;
    if (l==r)
    {
        s[k].val=a[l];
        return 0;
    }
    int mid=l+r>>1;
    build(s[k].lc,l,mid);
    build(s[k].rc,mid+1,r);
}
int change(int k,int l,int r,int x,int cnt)
{
    int root=++node_cnt;
    s[root]=s[k];
    if (l==r)
    {
        s[root].val=cnt;
        return root;
    }
    int mid=l+r>>1;
    if (x<=mid)s[root].lc=change(s[root].lc,l,mid,x,cnt);
    else s[root].rc=change(s[root].rc,mid+1,r,x,cnt);
    return root;
}
int query(int k,int l,int r,int x)
{
    if (l==r)return s[k].val;
    int mid=l+r>>1;
    if (x<=mid)return query(s[k].lc,l,mid,x);
    else return query(s[k].rc,mid+1,r,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(rt[0],1,n);
    int vi,num,loc,value;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&vi,&num,&loc);
        if (num==1)
        {
            scanf("%d",&value);
            rt[i]=change(rt[vi],1,n,loc,value);
        }
        else
        {
            cout<<query(rt[vi],1,n,loc)<<endl;;
            rt[i]=rt[vi];
        }
    }
    return 0;
}
@Tian_Xing  2019-04-28 08:57 回复 举报

各位路过的大佬,此讨论的楼主是初中学到主席树的大佬%%%%%

@Soulist  2019-04-28 09:07 回复 举报
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
struct ff
{
    int lc,rc,val;  
}s[N*25];
int n,m,a[N],rt[N],node_cnt;
void build(int &k,int l,int r)
{
    k=++node_cnt;
    if (l==r)
    {
        s[k].val=a[l]; return ;
    }
    int mid=(l+r)>>1;
    build(s[k].lc,l,mid);
    build(s[k].rc,mid+1,r);
}
void change(int &k, int vi, int l,int r,int x,int cnt)
{
    k=++node_cnt;
    if (l==r)
    {
        s[k].val=cnt;
        return ;
    }
    int mid=(l+r)>>1;
    if (x<=mid) change(s[k].lc,s[vi].lc,l,mid,x,cnt), s[k].rc = s[vi].rc;
    else change(s[k].rc, s[vi].rc,mid+1,r,x,cnt), s[k].lc = s[vi].lc;
}
int query(int k,int l,int r,int x)
{
    if (l==r)return s[k].val;
    int mid=(l+r)>>1;
    if (x<=mid)return query(s[k].lc,l,mid,x);
    else return query(s[k].rc,mid+1,r,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(rt[0],1,n);
    int vi,num,loc,value;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&vi,&num,&loc);
        if (num==1)
        {
            scanf("%d",&value);
            change(rt[i], rt[vi],1,n,loc,value);
        }
        else
        {
            cout<<query(rt[vi],1,n,loc)<<endl;;
            rt[i] = rt[vi];
        }
    }
    return 0;
}

帮你改了一下,貌似是change的锅。

以及楼上,貌似$memset0,lk,chenzhe$这些神仙也都是初中的....

@Soulist  2019-04-28 10:02 回复 举报

@qwaszx 不清楚QAQ,都改了,理论上说$build$存在一个$int$的返回值不会对答案造成影响。

@qwaszx  2019-04-28 10:15 回复 举报

@Mital 但改成void就过了QAQ可能是原来结尾没返回值造成了一些奇奇怪怪的问题

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。