我发现大家推歌都不带歌词那我也不带了
推歌：歌行四方
这不是我们天依游学记的歌吗，怎么上最美的夜了，下次记得标明出处
英文名居然是\(yalahula\)有点实力
今天还是照常补\(splay\)的题
splay板子题，思路上很简单
就是设\(ans\)表示结果，插入第一天时直接让\(ans+a_1\)，往后\([2\sim n]\)天直接让\(ans+\sum_{i=2}^{n}\min(|pre_i-a_i|,|nxt_i-a_i|)\)
那么可以就得出
\[ans=a_1+\sum_{i=2}^{n}\begin{cases} \min(|pre_i-a_i|,|nxt_i-a_i|)&cnt_i=1\\0&cnt_i>1\end{cases}
\]
其中\(pre_i\)是\(i\)的前驱，\(nxt_i\)是\(i\)的后继，\(cnt_i\)表示这个数在\(\{1\sim i\}\)天中出现的次数
那么代码就显而易见了
$My\ code$
#include<bits/stdc++.h>
#define int long long
namespace IO{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen("data.in","r",stdin);freopen("data.out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
#define close IO::close
#define Fire IO::Fire
#define read IO::read
#define write IO::write
#define cin std::cin
#define cout std::cout
#define endl '\n'
const int N=1000005;
const int INF=0x66CCFF0712;
class Spaly{
private:
int f[N],ch[N][2],sz;
public:
int key[N],lazytag=0,root,totf=0,cnt[N],siz[N];
inline void clear(int x){
ch[x][0]=ch[x][1]=f[x]=cnt[x]=key[x]=siz[x]=0;
}
inline int get(int x){
return ch[f[x]][1]==x;
}
inline void update(int x){
if(x){
siz[x]=cnt[x];
if(ch[x][0]){
siz[x]+=siz[ch[x][0]];
}
if(ch[x][1]){
siz[x]+=siz[ch[x][1]];
}
}
}
inline void rotate(int x){
int old=f[x],oldf=f[old],which=get(x);
ch[old][which]=ch[x][which^1];
f[ch[old][which]]=old;
ch[x][which^1]=old;
f[old]=x;f[x]=oldf;
if(oldf)
ch[oldf][ch[oldf][1]==old]=x;
update(old);
update(x);
return;
}
inline void splay(int x){
for(int fa;fa=f[x];rotate(x))
if(f[fa])
rotate(get(x)==get(fa)? fa : x);
root=x;
}
inline void insert(int v){
if(root==0){
++sz;
root=sz;
ch[root][0]=ch[root][1]=f[root]=0;
key[root]=v;
cnt[root]=siz[root]=1;
return;
}
int cur=root,fa=0;
while(1){
if(key[cur]==v){
++cnt[cur];
update(cur);
update(fa);
splay(cur);
break;
}
fa=cur;
cur=ch[cur][key[cur]<v];
if(cur==0){
++sz;
ch[sz][0]=ch[sz][1]=0;
key[sz]=v;
siz[sz]=1;
cnt[sz]=1;
f[sz]=fa;
ch[fa][key[fa]<v]=sz;
update(fa);
splay(sz);
break;
}
}
}
inline int find(int v){
int ans=0,cur=root;
while(1){
if(v<key[cur])
cur=ch[cur][0];
else {
ans+=(ch[cur][0] ? siz[ch[cur][0]] : 0);
if(v==key[cur]){
splay(cur);
return ans+1;
}
ans+=cnt[cur];
cur=ch[cur][1];
}
}
}
inline int findth(int k){
int cur=root;
while(1){
if(ch[cur][0] && k<=siz[ch[cur][0]])
cur=ch[cur][0];
else {
int tem=(ch[cur][0] ? siz[ch[cur][0]] : 0) +cnt[cur];
if(k<=tem)
return key[cur];
k-=tem;
cur=ch[cur][1];
}
}
}
inline int pre(int k){
insert(k);
int cur=ch[root][0];
while(ch[cur][1])
cur=ch[cur][1];
return cur;
del(k);
}
inline int nxt(int k){
insert(k);
int cur=ch[root][1];
while(ch[cur][0])
cur=ch[cur][0];
return cur;
del(k);
}
inline void del(int v){
find(v);
if(cnt[root]>1){
--cnt[root];
update(root);
return;
}
if(!ch[root][0] && !ch[root][1]){
clear(root);
root=0;
sz=0;
return;
}
if(!ch[root][0]){
int oldroot=root;
root=ch[root][1];
f[root]=0;
clear(oldroot);
--sz;
return;
}
else if(!ch[root][1]){
int oldroot=root;
root=ch[root][0];
f[root]=0;
clear(oldroot);
--sz;
return;
}
int lpre=pre(root),oldroot=root;
splay(lpre);
f[ch[oldroot][1]]=root;
ch[root][1]=ch[oldroot][1];
update(root);
return;
}
}TrEE;
#define TrEE_push(a) TrEE.insert(a)
#define TrEE_top() TrEE.findth(2)
#define TrEE_pop() TrEE.del(TrEE.findth(2))
#define TrEE_empty() ((TrEE.findth(2)==INF)?1:0)
#define TrEE_size() (TrEE.find(INF)-2)
signed main(){
// Fire();
TrEE.insert(INF);
TrEE.insert(-INF);
int n=read()-1,ans=read();
TrEE.insert(ans);
while(n--){
int m=read();
TrEE.insert(m);
if(TrEE.cnt[TrEE.root]>1) continue;
ans+=std::min(abs(m-TrEE.key[TrEE.pre(m)]),abs(m-TrEE.key[TrEE.nxt(m)]));
}
cout<<ans;
}
破防了，看错题调了快(1e2-1e1)/60.0小时
思路其实不太难，就是维护一颗\(splay\)，表示剩余的宠物或人
听起来好像很奇怪...呃呃就是说如果splay里啥也没有了就直接把后面的输入给插入进来
接下来直接对数在平衡树里找前驱后继然后一顿乱写最后都加到\(ans\)里就莫名其妙过了
注：把题看成了和上题差不多然后一顿乱维护就\(0pts\)了但是样例过了全真模拟CCF样例
$My\ Code$
#include<bits/stdc++.h>
#define int long long
namespace IO{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen("data.in","r",stdin);freopen("data.out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
#define close IO::close
#define Fire IO::Fire
#define read IO::read
#define write IO::write
#define cin std::cin
#define cout std::cout
#define endl '\n'
#define min(a,b) ((a)<(b))?(a):(b)
#define max(a,b) ((a)>(b))?(a):(b)
const int N=1000005;
const int INF=0x66CCFF0712;
class Spaly{
private:
int f[N],ch[N][2];
public:
int key[N],lazytag=0,sz,root,totf=0,cnt[N],siz[N];
inline void clear(int x){
ch[x][0]=ch[x][1]=f[x]=cnt[x]=key[x]=siz[x]=0;
}
inline int get(int x){
return ch[f[x]][1]==x;
}
inline void update(int x){
if(x){
siz[x]=cnt[x];
if(ch[x][0]){
siz[x]+=siz[ch[x][0]];
}
if(ch[x][1]){
siz[x]+=siz[ch[x][1]];
}
}
}
inline void rotate(int x){
int old=f[x],oldf=f[old],which=get(x);
ch[old][which]=ch[x][which^1];
f[ch[old][which]]=old;
ch[x][which^1]=old;
f[old]=x;f[x]=oldf;
if(oldf)
ch[oldf][ch[oldf][1]==old]=x;
update(old);
update(x);
return;
}
inline void splay(int x){
for(int fa;fa=f[x];rotate(x))
if(f[fa])
rotate(get(x)==get(fa)? fa : x);
root=x;
}
inline void insert(int v){
if(root==0){
++sz;
root=sz;
ch[root][0]=ch[root][1]=f[root]=0;
key[root]=v;
cnt[root]=siz[root]=1;
return;
}
int cur=root,fa=0;
while(1){
if(key[cur]==v){
++cnt[cur];
update(cur);
update(fa);
splay(cur);
break;
}
fa=cur;
cur=ch[cur][key[cur]<v];
if(cur==0){
++sz;
ch[sz][0]=ch[sz][1]=0;
key[sz]=v;
siz[sz]=1;
cnt[sz]=1;
f[sz]=fa;
ch[fa][key[fa]<v]=sz;
update(fa);
splay(sz);
break;
}
}
}
inline int find(int v){
int ans=0,cur=root;
while(1){
if(v<key[cur])
cur=ch[cur][0];
else {
ans+=(ch[cur][0] ? siz[ch[cur][0]] : 0);
if(v==key[cur]){
splay(cur);
return ans+1;
}
ans+=cnt[cur];
cur=ch[cur][1];
}
}
}
inline int findth(int k){
int cur=root;
while(1){
if(ch[cur][0] && k<=siz[ch[cur][0]])
cur=ch[cur][0];
else {
int tem=(ch[cur][0] ? siz[ch[cur][0]] : 0) +cnt[cur];
if(k<=tem)
return key[cur];
k-=tem;
cur=ch[cur][1];
}
}
}
inline int pre(){
int cur=ch[root][0];
while(ch[cur][1])
cur=ch[cur][1];
return cur;
}
inline int nxt(){
int cur=ch[root][1];
while(ch[cur][0])
cur=ch[cur][0];
return cur;
}
inline void del(int v){
find(v);
if(cnt[root]>1){
--cnt[root];
update(root);
return;
}
if(!ch[root][0] && !ch[root][1]){
clear(root);
root=0;
sz=0;
return;
}
if(!ch[root][0]){
int oldroot=root;
root=ch[root][1];
f[root]=0;
clear(oldroot);
--sz;
return;
}
else if(!ch[root][1]){
int oldroot=root;
root=ch[root][0];
f[root]=0;
clear(oldroot);
--sz;
return;
}
int lpre=pre(),oldroot=root;
splay(lpre);
f[ch[oldroot][1]]=root;
ch[root][1]=ch[oldroot][1];
update(root);
return;
}
inline int PRE(int k){
insert(k);
int a=pre();
del(k);
return a;
}
inline int NXT(int k){
insert(k);
int a=nxt();
del(k);
return a;
}
}TrEE;
signed main(){
// Fire();
TrEE.insert(-INF);
TrEE.insert (INF);
int n=read(),ans=0;
for(int i=1;i<=n;i++){
int opt=read(),m=read(),q;
if(TrEE.siz[TrEE.root]==2){
q=opt;
TrEE.insert(m);
}
else if(opt!=q){
int pre=TrEE.key[TrEE.PRE(m)],nxt=TrEE.key[TrEE.NXT(m)];
if(abs(pre)==INF)
(ans+=abs(m-nxt))%=(int)1e6,
TrEE.del(nxt);
else if(abs(nxt)==INF)
(ans+=abs(m-pre))%=(int)1e6,
TrEE.del(pre);
else{
int min=min(abs(m-pre),abs(m-nxt));
(ans+=min)%=(int)1e6;
TrEE.del((min==abs(m-pre))?pre:nxt);
}
}
else{
TrEE.insert(m);
}
}
cout<<ans<<endl;
}
往后就是树套树了，也就是高贵的二逼平衡树
至少我不会然后我就破防了但是我发现貌似没有强制在线，所以可以CDQ分治?
算了不整活了不用树套树A掉的话似乎意义是很不大的样子，不会树套树万一强制在线我不就似了
但是我不会所以先咕了明天晚上再写，今晚先研究一下树套树的一些概念
