KMP和KMP是好朋友
BZOJ 1251: 序列终结者 splay模板题,再写一遍找手感!Wa了一次!splay对无用节点的处理真的很重要!(其实是你自己偷懒没有判断到底存不存在子节点吧!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=50010; int n,m; int k,l,r,v; int id[Maxn]; struct Btree{ int fa; int ch[2]; int val; int max; int siz; int tag; bool rev; }; Btree tree[Maxn]; int root; inline void update(int x){ int l=tree[x].ch[0],r=tree[x].ch[1]; tree[x].siz=tree[l].siz+1+tree[r].siz; tree[x].max=max(tree[x].val,max(tree[l].max,tree[r].max)); } inline void clean(int x){ //printf("%d\n",x); int l=tree[x].ch[0],r=tree[x].ch[1]; if (tree[x].tag){ if (l){ tree[l].max+=tree[x].tag; tree[l].val+=tree[x].tag; tree[l].tag+=tree[x].tag; } if (r){ tree[r].max+=tree[x].tag; tree[r].val+=tree[x].tag; tree[r].tag+=tree[x].tag; } tree[x].tag=0; } if (tree[x].rev){ swap(tree[x].ch[0],tree[x].ch[1]); if (l){ tree[l].rev^=1; } if (r){ tree[r].rev^=1; } tree[x].rev=false; } } inline void rotate(int x,int &k){ int y=tree[x].fa,z=tree[y].fa; int l=(tree[y].ch[1]==x),r=l^1; if (k==y) k=x; else tree[z].ch[tree[z].ch[1]==y]=x; tree[tree[x].ch[r]].fa=y; tree[y].fa=x; tree[x].fa=z; tree[y].ch[l]=tree[x].ch[r]; tree[x].ch[r]=y; update(y); update(x); } inline void splay(int x,int &k){ while(x!=k){ int y=tree[x].fa,z=tree[y].fa; if (y!=k){ if (tree[y].ch[0]==x ^ tree[z].ch[0]==y) rotate(x,k); else rotate(y,k); } rotate(x,k); } } int find(int x,int rank){ clean(x); int l=tree[x].ch[0],r=tree[x].ch[1]; if (tree[l].siz+1==rank) return x; if (tree[l].siz>=rank) return find(l,rank); return find(r,rank-tree[l].siz-1); } inline void add(int l,int r,int val){ int x=find(root,l),y=find(root,r+2); splay(x,root);splay(y,tree[x].ch[1]); int z=tree[y].ch[0]; tree[z].tag+=val; tree[z].val+=val; tree[z].max+=val; } inline void rev(int l,int r){ int x=find(root,l),y=find(root,r+2); splay(x,root);splay(y,tree[x].ch[1]); int z=tree[y].ch[0]; tree[z].rev^=1; } inline int query(int l,int r){ int x=find(root,l),y=find(root,r+2); splay(x,root);splay(y,tree[x].ch[1]); int z=tree[y].ch[0]; return tree[z].max; } int build(int l,int r,int fa){ if (l>r) return 0; int mid=(l+r)/2; int now=id[mid]; tree[now].tag=0; tree[now].rev=false; tree[now].fa=id[fa]; if (l==r){ tree[now].val=tree[now].max=0; tree[now].siz=1; }else{ tree[now].ch[0]=build(l,mid-1,mid); tree[now].ch[1]=build(mid+1,r,mid); update(now); } return now; } inline void print(){ for (int i=1;i<=n;i++){ printf("%d ",tree[find(root,i+1)].val); } printf("\n"); } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n+2;i++) id[i]=i; tree[0].max=tree[0].val=-2100000000; tree[0].siz=0; root=build(1,n+2,0); //printf("Root : %d\n",root); for (int i=1;i<=m;i++){ scanf("%d%d%d",&k,&l,&r); //printf("%d %d %d\n",k,l,r); if (k==1) {scanf("%d",&v);add(l,r,v);} if (k==2) rev(l,r); if (k==3) printf("%d\n",query(l,r)); //print(); } return 0; } |
HDU 5147 Sequence II 树状数组!枚举C，顺带统 […]
