codevs p1285

codevs p1285"/>

codevs p1285

数据结构模板题

set

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int INF = 0x7fffffff;
const int MOD = 1000000;
int main()
{set<int> s;s.clear();s.insert(INF);s.insert(-INF);int n;int ans=0;int type;scanf("%d",&n);while(n--){int op,v;scanf("%d%d",&op,&v);if(s.size()==2){s.insert(v);type=op;}else if(op!=type){int l=*--s.lower_bound(v);int r=*s.lower_bound(v);if(l!=-INF && v-l<r-v){ans+=v-l;s.erase(l);}else{ans+=r-v;s.erase(r);}ans%=MOD;}else s.insert(v);}printf("%d\n",ans);return 0;
}

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 10000 + 5;
const int INF = 0x7fffffff;
const int MOD = 1000000;
int cnt_find=0,cnt_del=0,cnt_ins=0;
int v[MAXN<<1],next[MAXN<<1],down[MAXN<<1],head[MAXN],tail[MAXN];
int max_lev=0,sz=0;
int rand_lev()
{int ret=1;while((rand()&0xFFFF) < (0.3678 * 0xFFFF))ret++;return ret;
}
//previous value of val
int find(int val)
{int now=head[max_lev];while(true){while(v[next[now]]<val)now=next[now],++cnt_find;if(!down[now])return now;now=down[now];}
}
void insert(int val)
{int k=rand_lev();for(int i=max_lev+1;i<=k;i++){if(!head[i]){head[i]=++sz;tail[i]=++sz;next[head[i]]=tail[i];next[tail[i]]=0;down[head[i]]=head[i-1];v[head[i]]=-INF;v[tail[i]]=INF;}++cnt_ins;}max_lev=max(max_lev,ret);int now=head[max_lev];int s[50],top=0;while(true){while(v[next[now]]<val)now=next[now],++cnt_ins;s[top++]=now;if(!down[now])break;now=down[now];}for(int i=1;i<=k;i++){int p=s[--top];next[++sz]=next[p];next[p]=sz;down[sz]= i==1 ? 0:sz-1;v[sz]=val;++cnt_ins;}
}
void del(int val)
{int s[50],top=0;int now=head[max_lev];while(true){while(v[next[now]]<val)now=next[now],++cnt_del;if(v[next[now]]==val)s[top++]=now;if(!down[now])break;now=down[now];}while(top--)next[s[top]]=next[next[s[top]]],++cnt_del;
}
int main()
{int n,type,ans=0;scanf("%d",&n);while(n--){int a,b;scanf("%d%d",&a,&b);if(!max_lev){insert(b);type=a;}else if(a!=type){int l=find(b);int r=next[l];if(v[l]!=-INF && b-v[l]<=v[r]-b){ans+=b-v[l];del(v[l]);}else{ans+=v[r]-b;del(v[r]);}ans%=MOD;}else insert(b);}//printf("%d\n,find=%d,ins=%d,del=%d",ans,cnt_find,cnt_ins,cnt_del);printf("%d\n",ans);return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int MAXN = 80005;
const int MOD=1000000;
const int INF=0x7fffffff;
using namespace std;
int ch[MAXN][2];
int v[MAXN],s[MAXN],p[MAXN];
int rt=0,sz=0;
int l,r;
inline int cmp(int a,int b){if(a==b)return -1;return a<b?0:1;}
inline void up(int o){s[o]=s[ch[o][0]]+s[ch[o][1]]+1;}
inline void rot(int &o,int d)
{int tmp=ch[o][d^1];ch[o][d^1]=ch[tmp][d];ch[tmp][d]=o;up(o);up(tmp);o=tmp;
}
void ins(int &o,int val)
{if(!o){o=++sz;v[o]=val;p[o]=rand();s[o]=1;memset(ch[o],0,sizeof(ch[o]));return;}int d=cmp(val,v[o]);if(d==-1)return;ins(ch[o][d],val);if(p[ch[o][d]]<p[o])rot(o,d^1);
}
void del(int &o,int val)
{if(!o)return;int d=cmp(val,v[o]);if(d==-1){if(!ch[o][0])o=ch[o][1];else if(!ch[o][1])o=ch[o][0];else{int d2=p[ch[o][0]]>p[ch[o][1]] ? 1:0;rot(o,d2);del(ch[o][d2],val);}}else {del(ch[o][d],val);up(o);}}
int que(int o,int val)
{while(o){int d=cmp(val,v[o]);if(d==-1)l=r=v[o];else if(!d)r=min(r,v[o]);else l=max(l,v[o]);o=ch[o][d];}
}
int dfs(int o)
{if(ch[o][0])dfs(ch[o][0]);printf("node %d val=%d\n",o,v[o]);if(ch[o][1])dfs(ch[o][1]);
}
int main()
{int n,a,b,ans=0,type=0;memset(ch,0,sizeof(ch));rt=0;ins(rt,INF);ins(rt,-INF);scanf("%d",&n);while(n--){l=-INF,r=INF;scanf("%d%d",&a,&b);if(s[rt]==2){ins(rt,b);type=a;}else if(a!=type){que(rt,b);if(l!=-INF && b-l <= r-b){ans+=(b-l);ans%=MOD;del(rt,l);}else{ans+=(r-b);ans%=MOD;del(rt,r);}}else ins(rt,b);}cout<<ans<<endl;return 0;
}