| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
求各路大神帮忙看看哪里有问题……过了所有能找到的数据,但是WA#include <iostream> #include <cstdio> #include <cstdlib> #include <string.h> #define inf 2147483648 using namespace std; struct Splay { long long pre; long long ch[2]; long long bh; long long number; long long lazy; long long size; long long lazynum; long long min; }t[600005]; long long root,rf=0; long long cnt; void pushdown(long long a) { if(a==0) return; t[a].lazy=t[a].lazy%2; if(t[a].lazy==1) { long long swap=t[a].ch[0]; t[a].ch[0]=t[a].ch[1]; t[a].ch[1]=swap; if(t[a].ch[1]) t[t[a].ch[1]].lazy+=1; if(t[a].ch[0]) t[t[a].ch[0]].lazy+=1; t[a].lazy=0; } if(t[a].lazynum!=0) { t[a].number+=t[a].lazynum; t[a].min+=t[a].lazynum; if(t[a].ch[0]) t[t[a].ch[0]].lazynum+=t[a].lazynum; if(t[a].ch[1]) t[t[a].ch[1]].lazynum+=t[a].lazynum; t[a].lazynum=0; } } void update(long long a) { pushdown(a); t[a].size=1; t[a].size+=t[t[a].ch[0]].size; t[a].size+=t[t[a].ch[1]].size; t[a].min=t[a].number; long long lm,rm; lm=rm=inf; if(t[a].ch[0]) lm=t[t[a].ch[0]].min+t[t[a].ch[0]].lazynum; if(t[a].ch[1]) rm=t[t[a].ch[1]].min+t[t[a].ch[1]].lazynum; if(t[a].min>lm) t[a].min=lm; if(t[a].min>rm) t[a].min=rm; } void insert(long long a,long long b) { if(t[a].bh>t[b].bh) { if(t[a].ch[0]==0) { t[b].pre=a; t[a].ch[0]=b; update(b); } else { insert(t[a].ch[0],b); } } else { if(t[a].ch[1]==0) { t[b].pre=a; t[a].ch[1]=b; update(b); } else { insert(t[a].ch[1],b); } } update(a); } void rotate(long long a,long long type) { long long fa=t[a].pre; long long gfa=t[fa].pre; if(fa==root) root=a; pushdown(a); t[a].pre=gfa; t[gfa].ch[t[gfa].ch[1]==fa]=a; long long son=t[a].ch[type]; t[fa].ch[!type]=son; t[son].pre=fa; t[a].ch[type]=fa; t[fa].pre=a; update(fa); update(a); } void splay(long long a,long long b) { while(t[a].pre!=b) { pushdown(t[a].pre); pushdown(a); long long fa=t[a].pre; if(t[fa].pre==b) { long long k; if(t[fa].ch[1]==a) k=1; else k=0; rotate(a,(k+1)%2); } else { long long gfa=t[fa].pre; long long apl=(t[fa].ch[1]==a); long long fapl=(t[gfa].ch[1]==fa); if(apl==fapl) { rotate(fa,(fapl+1)%2); rotate(a,(apl+1)%2); } else { rotate(a,(apl+1)%2); rotate(a,(fapl+1)%2); } } } } long long find(long long a,long long b) { pushdown(a); long long lsize; if(t[a].ch[0]!=0) lsize=t[t[a].ch[0]].size; else lsize=0; if(lsize+1>b) return find(t[a].ch[0],b); if(lsize+1==b) { return t[a].bh; } if(lsize+1<b) return find(t[a].ch[1],b-lsize-1); } void reverse(long long a,long long b) { long long afind=find(root,a-1); splay(afind,rf); long long bfind=find(root,b+1); splay(bfind,root); t[t[bfind].ch[0]].lazy++; } void remove(long long a) { long long afind=find(root,a-1); splay(afind,rf); long long bfind=find(root,a+1); splay(bfind,root); t[bfind].ch[0]=0; update(bfind); update(afind); } void newsplay(long long a) { t[a].ch[0]=t[a].ch[1]=t[a].lazy=t[a].lazynum=0; t[a].size=1; t[a].number=inf; t[a].min=inf; t[a].bh=a; } void add(long long a,long long b) { cnt++; newsplay(cnt); t[cnt].bh=cnt; t[cnt].number=b; t[cnt].min=b; long long afind=find(root,a); splay(afind,rf); afind=find(root,a+1); splay(afind,root); t[afind].ch[0]=cnt; t[cnt].pre=afind; update(cnt); update(afind); update(t[afind].pre); } void revolve(long long a,long long b,long long c) { c=c%(b-a+1); while(c<0) c+=(b-a+1); if(c==0) return; reverse(a,b); reverse(a,a+c-1); reverse(a+c,b); } void inorder(long long a) { pushdown(a); if(t[a].ch[0]!=0) inorder(t[a].ch[0]); if(t[a].ch[1]!=0) inorder(t[a].ch[1]); } void addlazynum(long long a,long long b,long long c) { long long afind=find(root,a-1); long long bfind=find(root,b+1); splay(afind,rf); splay(bfind,root); t[t[bfind].ch[0]].lazynum+=c; update(t[bfind].ch[0]); update(bfind); update(afind); } long long getmin(long long a,long long b) { long long afind=find(root,a-1); splay(afind,rf); long long bfind=find(root,b+1); splay(bfind,root); pushdown(afind); pushdown(bfind); return t[t[bfind].ch[0]].min; } int main() { long long a; cin>>a; cnt=a+1; root=1; newsplay(1); for(long long i=2;i<=a+1;i++) { cin>>t[i].number; t[i].ch[0]=t[i].ch[1]=t[i].lazy=t[i].lazynum=0; t[i].size=1; t[i].min=t[i].number; t[i].bh=i; insert(root,i); } newsplay(a+2); insert(root,a+2); cnt=a+2; long long czs; cin>>czs; for(long long i=0;i<czs;i++) { char op[100]; cin>>op; long long x,y,z; if(strcmp(op,"MIN")==0) { cin>>x>>y; cout<<getmin(x+1,y+1)<<endl; } else if(strcmp(op,"ADD")==0) { cin>>x>>y>>z; addlazynum(x+1,y+1,z); } else if(strcmp(op,"INSERT")==0) { cin>>x>>y; add(x+1,y); } else if(strcmp(op,"REVERSE")==0) { cin>>x>>y; reverse(x+1,y+1); } else if(strcmp(op,"REVOLVE")==0) { cin>>x>>y>>z; revolve(x+1,y+1,z); } else if(strcmp(op,"DELETE")==0) { cin>>x; remove(x+1); } } system("pause"); return 0; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator