题解 P6011 【[SCOI2006]动态最值】
小菜鸟
2020-01-31 15:29:45
裸的平衡树（我并不知道不用线段树咋做
只要用到区间删除和区间查找。。。
---
有人写过splay了，这里给个fhq-treap供参考。（我终于渐渐有了平衡树不调试一遍过的能力，开心w
速度极慢，不开O2需15s过所有点，开了大幅下降至5s。
---
```cpp
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<algorithm>
struct Node
{
int val,min_s,max_s,size,pri;
Node *lc,*rc;
Node(int _Value):
val(_Value),
min_s(val),
max_s(val),
size(1),
pri(rand()),
lc(NULL),
rc(NULL)
{}
void maintain()
{
size=1;
min_s=val;
max_s=val;
if(lc!=NULL)
{
size+=lc->size;
min_s=std::min(min_s,lc->min_s);
max_s=std::max(max_s,lc->max_s);
}
if(rc!=NULL)
{
size+=rc->size;
min_s=std::min(min_s,rc->min_s);
max_s=std::max(max_s,rc->max_s);
}
}
};
Node *root;
auto merge(Node *l,Node *r)
{
if(l==NULL)return r;
if(r==NULL)return l;
if(l->pri>r->pri)
{
l->rc=merge(l->rc,r);
l->maintain();
return l;
}
else
{
r->lc=merge(l,r->lc);
r->maintain();
return r;
}
}
void split(Node *rt,int k,Node *&l,Node *&r)
{
if(rt==NULL)
{
l=NULL;
r=NULL;
return;
}
int s=1;
if(rt->lc!=NULL)s+=rt->lc->size;
if(s<k)
{
l=rt;
split(l->rc,k-s,l->rc,r);
l->maintain();
}
else
{
r=rt;
split(r->lc,k,l,r->lc);
r->maintain();
}
}
void erase(int pos)
{
Node *p1,*p2,*p3;
split(root,pos+1,p2,p3);
split(p2,pos,p1,p2);
root=merge(p1,p3);
delete p2;
}
auto query(int l,int r)
{
Node *p1,*p2,*p3;
split(root,r+1,p2,p3);
split(p2,l,p1,p2);
auto res=std::make_pair(p2->min_s,p2->max_s);
root=merge(merge(p1,p2),p3);
return res;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
{
int x;
scanf("%d",&x);
root=merge(root,new Node(x));
}
while(m--)
{
int op;
scanf("%d",&op);
if(op==1)
{
int pos;
scanf("%d",&pos);
erase(pos);
}
if(op==2)
{
int l,r;
scanf("%d%d",&l,&r);
auto res=query(l,r);
printf("%d %d\n",res.first,res.second);
}
}
}
```