【题解】 [HNOI2002]营业额统计 （Splay）

Solution:

• \(Splay\)板子题，注意可以选择相等大小

Code:

//It is coded by Ning_Mew on 4.10
#include
#define ls(x) node[x].ch[0]
#define rs(x) node[x].ch[1]
#define fa(x) node[x].fa
#define root node[0].ch[1]
using namespace std;

const int maxn=32800,INF=1e9+7;

int n,tot=0,ans=0;
struct Node{
  int fa,ch[2],val,cnt,size;
}node[maxn];

void update(int x){node[x].size=node[ls(x)].size+node[rs(x)].size+node[x].cnt;}
void connect(int x,int fa,int how){node[x].fa=fa;node[fa].ch[how]=x;}
int ident(int x){return x==node[fa(x)].ch[0]?0:1;}
void rorate(int x){
  int Y=fa(x),R=fa(Y);int Yson=ident(x),Rson=ident(Y);
  connect(node[x].ch[Yson^1],Y,Yson);
  connect(Y,x,Yson^1);
  connect(x,R,Rson);
  update(Y);update(x);return;
}
void Splay(int x,int goal){
  int to=fa(goal);
  while(fa(x)!=to){
    if(fa(fa(x))==to)rorate(x);
    else if(ident(x)==ident(fa(x)))rorate(fa(x)),rorate(x);
    else rorate(x),rorate(x);
  }
}
int newnode(int x,int fa){
  node[++tot].val=x;node[tot].size=node[tot].cnt=1;node[tot].fa=fa;return tot;
}
void ins(int x){
  int now=root;
  if(!now){newnode(x,0);root=tot;return;}
  else{
    while(1){
      node[now].size++;
      if(node[now].val==x){node[now].cnt++;Splay(now,root);return;}
      int nxt=xx)ans=min(ans,node[now].val);
    if(node[now].val==x&&node[now].cnt!=1)ans=min(ans,node[now].val);
    int nxt=x