BZOJ3192: [JLOI2013]删除物品(splay)

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define lll tr[spc].ch[0]
  5 #define rrr tr[spc].ch[1]
  6 #define ls ch[0]
  7 #define rs ch[1]
  8 using std::swap;
  9 const int N=1000000;
 10 typedef long long lnt;
 11 struct data{
 12     lnt Max_val;
 13     lnt Where_is_Max_Val;
 14     bool friend operator < (data x,data y)
 15     {
 16         return x.Max_val<y.Max_val;
 17     }
 18     lnt wp()
 19     {
 20         return Where_is_Max_Val;
 21     }
 22 };
 23 struct trnt{
 24     int ch[2];
 25     int fa;
 26     int lzt;
 27     lnt val;
 28     data mxs;
 29     lnt wgt;
 30 }tr[N];
 31 int siz;
 32 int n1,n2;
 33 int root1,root2;
 34 int fst1,lst1;
 35 int fst2,lst2;
 36 lnt ans=0;
 37 lnt num[N];
 38 data max(data a,data b)
 39 {
 40     if(a.Max_val<b.Max_val)
 41         return b;
 42     return a;
 43 }
 44 bool whc(int spc)
 45 {
 46     return tr[tr[spc].fa].rs==spc;
 47 }
 48 void res(int spc)
 49 {
 50     tr[spc].wgt=1;
 51     tr[spc].mxs=(data){tr[spc].val,spc};
 52     return ;
 53 }
 54 void pushup(int spc)
 55 {
 56     res(spc);
 57     if(lll)
 58     {
 59         tr[spc].wgt+=tr[lll].wgt;
 60         tr[spc].mxs=max(tr[spc].mxs,tr[lll].mxs);
 61     }
 62     if(rrr)
 63     {
 64         tr[spc].wgt+=tr[rrr].wgt;
 65         tr[spc].mxs=max(tr[spc].mxs,tr[rrr].mxs);
 66     }
 67     return ;
 68 }
 69 void trr(int spc)
 70 {
 71     if(!spc)
 72         return ;
 73     tr[spc].lzt^=1;
 74     swap(lll,rrr);
 75     return ;
 76 }
 77 void pushdown(int spc)
 78 {
 79     if(tr[spc].lzt)
 80     {
 81         trr(lll);
 82         trr(rrr);
 83         tr[spc].lzt=0;
 84     }
 85     return ;
 86 }
 87 void recal(int spc)
 88 {
 89     if(tr[spc].fa)
 90         recal(tr[spc].fa);
 91     pushdown(spc);
 92     return ;
 93 }
 94 void rotate(int spc)
 95 {
 96     int f=tr[spc].fa;
 97     bool k=whc(spc);    
 98     tr[f].ch[k]=tr[spc].ch[!k];
 99     tr[spc].ch[!k]=f;
100     tr[tr[f].fa].ch[whc(f)]=spc;
101     tr[spc].fa=tr[f].fa;
102     tr[f].fa=spc;
103     tr[tr[f].ch[k]].fa=f;
104     pushup(f);
105     pushup(spc);
106     return ;
107 }
108 int splay(int spc,int f)
109 {
110     recal(spc);
111     while(tr[spc].fa!=f)
112     {
113         int ft=tr[spc].fa;
114         if(tr[ft].fa==f)
115         {
116             rotate(spc);
117             break;
118         }
119         if(whc(spc)^whc(ft))
120             rotate(spc);
121         else
122             rotate(ft);
123         rotate(spc);
124     }
125     return spc;
126 }
127 void build(int &spc,int l,int r,int f)
128 {
129     if(l>r)
130         return ;
131     spc=++siz;
132     int mid=(l+r)>>1;
133     tr[spc].fa=f;
134     tr[spc].val=num[mid];
135     res(spc);
136     build(lll,l,mid-1,spc);
137     build(rrr,mid+1,r,spc);
138     pushup(spc);
139     return ;
140 }
141 int fstfind(int spc)
142 {
143     while(lll)
144         spc=lll;
145     return spc;
146 }
147 int lstfind(int spc)
148 {
149     while(rrr)
150         spc=rrr;
151     return spc;
152 }
153 int maxmin(int spc)
154 {
155     pushdown(spc);
156     spc=lll;
157     pushdown(spc);
158     while(rrr)
159     {
160         spc=rrr;
161         pushdown(spc);
162     }
163     return spc;
164 }
165 int minmax(int spc)
166 {
167     pushdown(spc);
168     spc=rrr;
169     pushdown(spc);
170     while(lll)
171     {
172         spc=lll;
173         pushdown(spc);
174     }
175     return spc;
176 }
177 int lstmax(int spc)
178 {
179     pushdown(spc);
180     if(lll)
181         return maxmin(spc);
182     recal(spc);
183     while(whc(spc)==0)
184         spc=tr[spc].fa;
185     return tr[spc].fa;
186 }
187 int main()
188 {
189     scanf("%d%d",&n1,&n2);
190     for(int i=1;i<=n1;i++)
191         scanf("%lld",&num[n1-i+1]);
192     build(root1,0,n1+1,0);
193     fst1=fstfind(root1);
194     lst1=lstfind(root1);
195     for(int i=1;i<=n2;i++)
196         scanf("%lld",&num[n2-i+1]);
197     build(root2,0,n2+1,0);
198     fst2=fstfind(root2);
199     lst2=lstfind(root2);
200     for(int i=1;i<=n1+n2;i++)
201     {
202         root1=splay(fst1,0);
203         splay(lst1,root1);
204         root2=splay(fst2,0);
205         splay(lst2,root2);
206         int spc1,spc2;
207         spc1=tr[tr[root1].rs].ls;
208         spc2=tr[tr[root2].rs].ls;
209         if(tr[spc1].mxs<tr[spc2].mxs)
210         {
211             root2=splay(tr[spc2].mxs.wp(),0);
212             splay(lst2,root2);
213             int tmp=tr[tr[root2].rs].ls;
214             tr[tr[root2].rs].ls=0;
215             pushup(tr[root2].rs);
216             pushup(root2);
217             ans+=tr[tmp].wgt;
218             trr(tmp);
219             int temp=root2;
220             root2=splay(maxmin(temp),0);
221             splay(minmax(temp),root2);
222             tr[tr[root2].rs].ls=0;
223             pushup(tr[root2].rs);
224             pushup(root2);
225             root1=splay(lstmax(lst1),0);
226             splay(lst1,root1);
227             tr[tr[root1].rs].ls=tmp;
228             tr[tmp].fa=tr[root1].rs;
229             pushup(tr[root1].rs);
230             pushup(root1);
231         }else{
232             root1=splay(tr[spc1].mxs.wp(),0);
233             splay(lst1,root1);
234             int tmp=tr[tr[root1].rs].ls;
235             tr[tr[root1].rs].ls=0;
236             pushup(tr[root1].rs);
237             pushup(root1);
238             ans+=tr[tmp].wgt;
239             trr(tmp);
240             int temp=root1;
241             root1=splay(maxmin(temp),0);
242             splay(minmax(temp),root1);
243             tr[tr[root1].rs].ls=0;
244             pushup(tr[root1].rs);
245             pushup(root1);
246             root2=splay(lstmax(lst2),0);
247             splay(lst2,root2);
248             tr[tr[root2].rs].ls=tmp;
249             tr[tmp].fa=tr[root2].rs;
250             pushup(tr[root2].rs);
251             pushup(root2);
252         }
253     }
254     printf("%lld\n",ans);
255     return 0;
256 }