首页 > 代码库 > BZOJ1251 序列终结者
BZOJ1251 序列终结者
传送门
为了这道题浪费了一天的时间。然而明天就要月考了
先是不停的TLE，然后查了半天才发现是数组下标打错了，但是数组下标打错不应该是RE吗...，因为这个查了一中午，肉查真的很重要..
然后又是随意内存的锅，没有注意0节点之类的，对拍什么的搞了很长时间，平衡树的处理应该要注意到这个点，很重要。
剩下的没什么好说了，代码实现还是比较直观的吧。
1 //BZOJ 1251 2 //by Cydiater 3 //2016.9.7 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <cstring> 8 #include <string> 9 #include <algorithm> 10 #include <queue> 11 #include <map> 12 #include <ctime> 13 #include <iomanip> 14 #include <cmath> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n) for(int i=j;i<=n;i++) 18 #define down(i,j,n) for(int i=j;i>=n;i--) 19 const int MAXN=1e6+5; 20 const int oo=0x3f3f3f3f; 21 inline int read(){ 22 char ch=getchar();int x=0,f=1; 23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25 return x*f; 26 } 27 int N,M,tol=1,root=1,op,leftt,rightt,v,cnt=0; 28 struct SplayTree{ 29 int son[2],siz,fa,v,tag,delta,id,max_value; 30 }t[MAXN]; 31 namespace solution{ 32 void debug(int now){ 33 printf("now=%d t[now].id=%d t[now].max_value=http://www.mamicode.com/%d t[now].delta=%d t[now].tag=%d t[now].son[0]=%d t[now].son[1]=%d t[now].siz=%d t[now].fa=%d t[now].v=%d/n",now,t[now].id,t[now].max_value,t[now].delta,t[now].tag,t[now].son[0],t[now].son[1],t[now].siz,t[now].fa,t[now].v); 34 if(t[now].son[0])debug(t[now].son[0]); 35 if(t[now].son[1])debug(t[now].son[1]); 36 } 37 inline int get(int x){return t[t[x].fa].son[1]==x;} 38 inline void updata(int x){ 39 if(x){ 40 t[x].siz=1; 41 if(t[x].son[0])t[x].siz+=t[t[x].son[0]].siz; 42 if(t[x].son[1])t[x].siz+=t[t[x].son[1]].siz; 43 t[x].max_value=http://www.mamicode.com/t[x].v; 44 if(t[x].son[0])t[x].max_value=http://www.mamicode.com/max(t[x].max_value,t[t[x].son[0]].max_value); 45 if(t[x].son[1])t[x].max_value=http://www.mamicode.com/max(t[x].max_value,t[t[x].son[1]].max_value); 46 } 47 } 48 inline void downit(int node){ 49 if(t[node].tag){ 50 t[t[node].son[0]].tag^=1;t[t[node].son[1]].tag^=1; 51 swap(t[node].son[1],t[node].son[0]); 52 t[node].tag=0; 53 } 54 if(t[node].delta!=0){ 55 t[t[node].son[0]].delta+=t[node].delta; t[t[node].son[1]].delta+=t[node].delta; 56 t[t[node].son[0]].v+=t[node].delta; t[t[node].son[1]].v+=t[node].delta; 57 t[t[node].son[0]].max_value+=t[node].delta; t[t[node].son[1]].max_value+=t[node].delta; 58 t[node].delta=0; 59 } 60 } 61 inline void rotate(int x){//rotate now node to root 62 int old=t[x].fa,oldf=t[old].fa,which=get(x); 63 t[old].son[which]=t[x].son[which^1];t[t[old].son[which]].fa=old; 64 t[old].fa=x;t[x].son[which^1]=old; 65 t[x].fa=oldf; 66 if(oldf)t[oldf].son[t[oldf].son[1]==old]=x; 67 updata(old);updata(x); 68 } 69 void splay(int node,int aim){ 70 for(int fa;(fa=t[node].fa);rotate(node)){ 71 if(node==aim)break; 72 if(fa==aim){ 73 rotate(node); 74 break; 75 } 76 if(t[fa].fa==aim){ 77 rotate(get(node)==get(fa)?fa:node); 78 rotate(node);break; 79 } 80 else if(t[fa].fa!=aim)rotate(get(node)==get(fa)?fa:node); 81 } 82 if(aim==root)root=node; 83 } 84 inline int find(int num){ 85 int now=root; 86 while(1){ 87 downit(now); 88 int tmp=(t[now].son[0]?t[t[now].son[0]].siz:0); 89 if(num<=tmp)now=t[now].son[0]; 90 else{ 91 if(num==tmp+1)return now; 92 num-=(tmp+1); 93 now=t[now].son[1]; 94 } 95 } 96 } 97 inline void build(int leftt,int rightt,int node,int fa){ 98 if(leftt==rightt){ 99 t[node].fa=fa;t[node].v=0;t[node].delta=0;t[node].tag=0;100 t[node].son[0]=t[node].son[1]=0;t[node].siz=1;t[node].id=leftt;101 return;102 }103 int mid=(leftt+rightt)>>1;104 t[node].fa=fa;t[node].v=0;t[node].tag=0;t[node].delta=0;t[node].siz=1;105 t[node].id=mid;106 if(mid-1>=leftt){107 tol++;t[node].son[0]=tol;108 build(leftt,mid-1,tol,node);109 t[node].siz+=t[t[node].son[0]].siz;110 }111 if(mid+1<=rightt){112 tol++;t[node].son[1]=tol;113 build(mid+1,rightt,tol,node);114 t[node].siz+=t[t[node].son[1]].siz;115 }116 updata(node);117 }118 void init(){119 N=read();M=read();120 build(1,N+2,1,0);121 }122 inline void Add(int leftt,int rightt,int v){123 int left_id=find(leftt),right_id=find(rightt+2);124 splay(left_id,root);splay(right_id,t[root].son[1]);125 int node=t[right_id].son[0];126 t[node].delta+=v;t[node].v+=v;t[node].max_value+=v;127 }128 inline void Reverse(int leftt,int rightt){129 int left_id=find(leftt),right_id=find(rightt+2);130 splay(left_id,root);splay(right_id,t[root].son[1]);131 int node=t[right_id].son[0];132 t[node].tag^=1;133 }134 inline int Max(int leftt,int rightt){135 int left_id=find(leftt),right_id=find(rightt+2);136 splay(left_id,root);splay(right_id,t[root].son[1]);137 int node=t[right_id].son[0];138 return t[node].max_value;139 }140 inline void slove(){141 while(M--){142 op=read();leftt=read();rightt=read();143 if(op==1){144 v=read();145 Add(leftt,rightt,v);146 }147 if(op==2)Reverse(leftt,rightt);148 if(op==3){149 int ans=Max(leftt,rightt);150 printf("%d\n",ans);151 }152 //debug(root);puts("");153 //printf("Time has passed:%d ms!\n",clock());154 }155 }156 }157 int main(){158 //freopen("input.in","r",stdin);159 //freopen("out1.out","w",stdout);160 using namespace solution;161 init();162 slove();163 //cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;164 return 0;165 }
BZOJ1251 序列终结者
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。