2020-2021:teams:legal_string:jxm2001:可持久化数据结构_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:可持久化数据结构_1 [2020/07/05 12:47] jxm2001 |
2020-2021:teams:legal_string:jxm2001:可持久化数据结构_1 [2020/08/17 15:23] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 35: | 行 35: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e6+5; | const int MAXN=1e6+5; | ||
| struct Node{ | struct Node{ | ||
| 行 139: | 行 116: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e6+5; | const int MAXN=1e6+5; | ||
| struct Node{ | struct Node{ | ||
| 行 247: | 行 201: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e5+5; | const int MAXN=1e5+5; | ||
| struct Node{ | struct Node{ | ||
| int lef,rig,fa,d; | int lef,rig,fa,d; | ||
| }; | }; | ||
| - | Node node[MAXN*20]; | + | Node node[MAXN*30]; |
| int cnt,root[MAXN<<1],n,q; | int cnt,root[MAXN<<1],n,q; | ||
| inline int nodecopy(int k){ | inline int nodecopy(int k){ | ||
| 行 300: | 行 231: | ||
| update_fa(node[k].lef,node[p].lef,lef,mid,pos,F); | update_fa(node[k].lef,node[p].lef,lef,mid,pos,F); | ||
| } | } | ||
| - | void update_dep(int k,int lef,int rig,int pos){ | + | void update_dep(int &k,int p,int lef,int rig,int pos){ |
| + | k=nodecopy(p); | ||
| if(lef==rig){ | if(lef==rig){ | ||
| node[k].d++; | node[k].d++; | ||
| 行 307: | 行 239: | ||
| int mid=lef+rig>>1; | int mid=lef+rig>>1; | ||
| if(mid<pos) | if(mid<pos) | ||
| - | update_dep(node[k].rig,mid+1,rig,pos); | + | update_dep(node[k].rig,node[p].rig,mid+1,rig,pos); |
| else | else | ||
| - | update_dep(node[k].lef,lef,mid,pos); | + | update_dep(node[k].lef,node[p].lef,lef,mid,pos); |
| } | } | ||
| int query_id(int k,int lef,int rig,int pos){ | int query_id(int k,int lef,int rig,int pos){ | ||
| 行 332: | 行 264: | ||
| update_fa(rt,p,1,n,node[x].fa,node[y].fa); | update_fa(rt,p,1,n,node[x].fa,node[y].fa); | ||
| if(node[x].d==node[y].d) | if(node[x].d==node[y].d) | ||
| - | update_dep(rt,1,n,node[y].fa); | + | update_dep(rt,rt,1,n,node[y].fa); |
| } | } | ||
| int main() | int main() | ||
2020-2021/teams/legal_string/jxm2001/可持久化数据结构_1.1593924426.txt.gz · 最后更改: 2020/07/05 12:47 由 jxm2001
