@[我是傻逼](/space/show?uid=68387) ~~id可以~~
by Juanzhang @ 2018-08-23 22:22:48
@[我是傻逼](/space/show?uid=68387) 空间$O(n\;log\;n)$
by Juanzhang @ 2018-08-23 22:24:38
@[我是傻逼](/space/show?uid=68387) 你本地评测指的是什么？你主函数不对啊
by Juanzhang @ 2018-08-23 22:25:38
对不起我智障了，请忽略上一行
by Juanzhang @ 2018-08-23 22:26:26
@[小光](/space/show?uid=73934) 样例2很小，n连10都不到
by lamboo @ 2018-08-24 17:53:09
@[小光](/space/show?uid=73934) 把++cnt另写一条语句可以过第二个点，但三个点答案错了
by lamboo @ 2018-08-24 18:00:50
不过为什么会这样？？？
by lamboo @ 2018-08-24 18:03:40
@[我是傻逼](/space/show?uid=68387) 你试一下这份
``` cpp
#include <bits/stdc++.h>
#define N 1000001
using namespace std;
struct SegmentTree
{
int lson,rson,val;
};
SegmentTree tree[4*N];
int root[N],tot;
inline void read(int &x)
{
x=0;
int k=1;
char ch=getchar();
while (!isdigit(ch)) { if (ch=='-') k=-1; ch=getchar(); }
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
x*=k;
}
inline int build(int l,int r)
{
int p=++tot;
if (l==r) { read(tree[p].val); return p; }
int mid=(l+r)>>1;
tree[p].lson=build(l,mid),tree[p].rson=build(mid+1,r);
tree[p].val=tree[tree[p].lson].val+tree[tree[p].rson].val;
return p;
}
inline int ask(int p,int l,int r,int loc)
{
if (l==r) return tree[p].val;
int mid=(l+r)>>1;
if (loc<=mid) return ask(tree[p].lson,l,mid,loc);
else return ask(tree[p].rson,mid+1,r,loc);
}
inline int add(int now,int l,int r,int x,int value)
{
int p=++tot;
tree[p]=tree[now];
if (l==r) { tree[p].val=value; return p; }
int mid=(l+r)>>1;
if (x<=mid) tree[p].lson=add(tree[now].lson,l,mid,x,value);
else tree[p].rson=add(tree[now].rson,mid+1,r,x,value);
tree[p].val=tree[tree[p].lson].val+tree[tree[p].rson].val;
return p;
}
int main()
{
int n,m,cnt=0;
scanf("%d%d",&n,&m);
root[0]=build(1,n);
for (int i=1;i<=m;i++)
{
int v,p,loc,value;
scanf("%d%d%d",&v,&p,&loc);
if (p==1) scanf("%d",&value),root[i]=add(root[v],1,n,loc,value);
if (p==2) printf("%d\n",ask(root[v],1,n,loc)),root[i]=root[v];
}
return 0;
}
```
by Juanzhang @ 2018-08-24 18:48:56
@[小光](/space/show?uid=73934) 这份可以
大佬改了什么？？？
root[i]=root[v]，我只改了这个还是错
by lamboo @ 2018-08-24 18:53:52
```cpp
//改完以后20分
#include <bits/stdc++.h>
#define N 1000001
using namespace std;
struct SegmentTree
{
int lson,rson,val;
};
SegmentTree tree[4*N];
int root[N],tot;
inline void read(int &x)
{
x=0;
int k=1;
char ch=getchar();
while (!isdigit(ch)) { if (ch=='-') k=-1; ch=getchar(); }
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
x*=k;
}
inline int build(int l,int r)
{
int p=++tot;
if (l==r) { read(tree[p].val); return p; }
int mid=(l+r)>>1;
tree[p].lson=build(l,mid),tree[p].rson=build(mid+1,r);
return p;
}
inline int ask(int p,int l,int r,int x)
{
if (l==r) return tree[p].val;
int mid=(l+r)>>1;
if (x<=mid) return ask(tree[p].lson,l,mid,x);
else return ask(tree[p].rson,mid+1,r,x);
}
inline int add(int now,int l,int r,int x,int value)
{
int p=++tot;
tree[p]=tree[now];
if (l==r) { tree[p].val=value; return p; }
int mid=(l+r)>>1;
if (x<=mid) tree[p].lson=add(tree[now].lson,l,mid,x,value);
else tree[p].rson=add(tree[now].rson,mid+1,r,x,value);
return p;
}
int main()
{
int n,m,cnt=0;
scanf("%d%d",&n,&m);
root[0]=build(1,n);
for (int i=1;i<=m;i++)
{
int v,p,loc,value;
scanf("%d%d%d",&v,&p,&loc);
if (p==1) scanf("%d",&value),root[i]=add(root[i-1],1,n,loc,value);
if (p==2) printf("%d\n",ask(root[v],1,n,loc)),root[i]=root[v];
}
return 0;
}
```
by lamboo @ 2018-08-24 18:54:21