Purslane @ 2022-01-22 11:35:28
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline bool id(const char ch) {
return ch>='0'&&ch<='9';
}
inline int read(void) {
int s=0,f=0;
char ch=getchar();
while(!id(ch)) f=(ch=='-'),ch=getchar();
while(id(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return f?-s:s;
}
const int MAXN=80000+10;
int n,ANS,ans,root,idx,A,B,C,D,op,sze;
struct TREE {
int l,r,key,val;
}tr[MAXN<<1];
inline int get_node(const int key) {
return tr[++idx]=TREE{0,0,key,rand()},idx;
}
void split(const int u,const int key,int &x,int &y) {
if(!u) return x=y=0,void();
if(tr[u].key<=key) x=u,split(tr[u].r,key,tr[u].r,y);
else y=u,split(tr[u].l,key,x,tr[u].l);
return ;
}
int merge(const int x,const int y) {
if(!x||!y) return x|y;
if(tr[x].val>=tr[y].val) return tr[x].r=merge(tr[x].r,y),x;
return tr[y].l=merge(x,tr[y].l),y;
}
inline void insert(const int key) {
return split(root,key,A,B),root=merge(merge(A,get_node(key)),B),void();
}
inline void remove(const int key) {
return split(root,key-1,A,B),split(B,key,C,D),merge(A,D),void();
}
int get_mx(const int u) {
if(tr[u].r) return get_mx(tr[u].r);
return tr[u].key;
}
int get_mn(const int u) {
if(tr[u].l) return get_mn(tr[u].l);
return tr[u].key;
}
inline int pre(const int k) {
return split(root,k,A,B),ans=get_mx(A),root=merge(A,B),ans;
}
inline int nxt(const int k) {
return split(root,k-1,A,B),ans=get_mn(B),root=merge(A,B),ans;
}
signed main() {
n=read();
insert(-INT_MAX*2ll),insert(INT_MAX*2ll);
for(int i=1,a,b;i<=n;i++) {
a=read(),b=read();
if(sze==0) op=a,sze++,insert(b);
else if(op==a) insert(b),sze++;
else {
int P=pre(b),N=nxt(b);
if(abs(b-P)<=abs(b-N)) sze--,remove(P),ANS+=abs(b-P);
else sze--,remove(N),ANS+=abs(b-N);
ANS%=1000000;
}
}
printf("%lld\n",ANS);
return 0;
}0 分！！！！！！！！
by 幽灵特工 @ 2022-01-22 11:39:07
入门
by MatrixCascade @ 2022-01-22 11:40:33
？
by xuorange @ 2022-01-22 11:55:12
《入门题》
by Purslane @ 2022-01-22 11:57:51
扩句：（平衡树的）入门题
by ABANDON_AC @ 2022-01-22 11:58:39
《入门题》??《入土题》
by ABANDON_AC @ 2022-01-22 11:59:38
蒟蒻才学到STL
by Falsecx @ 2022-01-23 10:23:04
请马西斯大佬停止凡学行为
by Purslane @ 2022-01-24 09:22:54
@☞§chuxu§☜ 您可以看看这两份代码有什么区别吗 ？
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline bool id(const char ch) {
return ch>='0'&&ch<='9';
}
inline int read(void) {
int s=0,f=0;
char ch=getchar();
while(!id(ch)) f=(ch=='-'),ch=getchar();
while(id(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return f?-s:s;
}
const int MAXN=1e5+10;
struct Node {
int l,r,key,val;
}tr[MAXN];
int n,ANS,sze,op,ans,root,idx,A,B,C,D;
inline int get_node(const int key) {
return tr[++idx]=Node{0,0,key,rand()},idx;
}
void split(const int u,const int k,int &x,int &y) {
if(u==0) return x=y=0,void();
if(tr[u].key<=k) return x=u,split(tr[u].r,k,tr[u].r,y),void();
return y=u,split(tr[u].l,k,x,tr[u].l),void();
}
int merge(const int x,const int y) {
if(!x||!y) return x|y;
if(tr[x].val>=tr[y].val) return tr[x].r=merge(tr[x].r,y),x;
return tr[y].l=merge(x,tr[y].l),y;
}
inline void insert(const int val) {
return split(root,val,A,B),root=merge(merge(A,get_node(val)),B),void();
}
inline void remove(const int val) {
return split(root,val-1,A,B),split(B,val,C,D),root=merge(A,D),void();
}
int get_mx(const int u) {
if(tr[u].r) return get_mx(tr[u].r);
return tr[u].key;
}
int get_mn(const int u) {
if(tr[u].l) return get_mn(tr[u].l);
return tr[u].key;
}
inline int pre(const int val) {
return split(root,val,A,B),ans=get_mx(A),root=merge(A,B),ans;
}
inline int nxt(const int val) {
return split(root,val-1,A,B),ans=get_mn(B),root=merge(A,B),ans;
}
signed main() {
n=read();
insert(-INT_MAX*10ll),insert(INT_MAX*10ll);
for(int i=1;i<=n;i++) {
int a=read(),b=read();
if(sze==0) op=a,sze++,insert(b);
else if(op==a) insert(b),sze++;
else {
int P=pre(b),N=nxt(b);
if(b-P<=N-b) remove(P),sze--,ANS+=b-P;
else remove(N),sze--,ANS+=N-b;
ANS%=1000000;
}
}
cout<<ANS%1000000;
return 0;
}