{"id":62,"date":"2010-01-01T23:36:00","date_gmt":"2010-01-01T15:36:00","guid":{"rendered":"http:\/\/localhost\/?p=62"},"modified":"2010-01-01T23:36:00","modified_gmt":"2010-01-01T15:36:00","slug":"sgu_187","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=62","title":{"rendered":"sgu 187"},"content":{"rendered":"

\u5c31\u662f\u8bf4\u7ed9\u4f601\u5230n\u4e00\u6392\u6570\u6bcf\u6b21\u628a\u4ecel\u5230r\u7684\u6570\u53cd\u8fc7\u6765\u3002\u3002\u8ba9\u4f60\u8f93\u51fa\u6700\u540e\u7684\u90a3\u5217\u6570\u3002\u3002
\u52a8\u6001\u8868\u3002\u3002\u660e\u663e\u7528splay\u3002\u3002\u6700\u8fd1\u521a\u5b66\u4e86splay\uff0c\u723d\u963f\u3002\u3002
Code\uff1a
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=~0U>>1;
class splay
{
int n;
struct node
{
int k,s;
bool d,rev;
node*c[2],*p;
node(){c[0]=c[1]=p=0;}
void sc(node*_c,bool d)
{c[d]=_c;_c->p=this;_c->d=d;}
}*root,*Null,*Now,Data[130100];
typedef node* Node;
Node new_node(int k)
{
Now->c[0]=Now->c[1]=Null;
Now->rev=false;Now->s=1;
Now->k=k;return Now++;
}
void rev(Node t)
{
if(t==Null) return;
t->rev^=1;
swap(t->c[0],t->c[1]);
t->c[0]->d=0;
t->c[1]->d=1;
}
void pus(Node t)
{
if(t->rev)
rev(t->c[0]),rev(t->c[1]);
t->rev=false;
}
void upd(Node t)
{
t->s=t->c[0]->s+t->c[1]->s+1;
}
void rot(Node t)
{
Node p=t->p;
pus(p);pus(t);bool d=t->d;
p->sc(t->c[!d],d);
p->p->sc(t,p->d);
t->sc(p,!d);
upd(p);upd(t);
if(p==root) root=t;
}
void spl(Node x,Node f)
{
for(pus(x);x->p!=f;)
{
if(x->p->p==f) rot(x);
else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );
}
}
Node sel(int k)
{
int r;
for(Node t=root;;)
{
pus(t);
r=t->c[0]->s;
if(r==k) return t;
t=t->c[k>r];
if(k>r) k-=r+1;
}
}
void print(Node t)
{
if(t==Null||!t) return;
pus(t);
print(t->c[0]);
if(t->k)printf<\/a>("%d ",t->k),fflush(stdout);
print(t->c[1]);
}
public:
void out()
{
print(root);
}
splay(int n):n(n)
{
Now=Data;
Null=new node;Null->s=0;
root=new_node(0);root->p=Null;
Node p,q=root;
for(int i=1;i<=n;i++)
{
p=new_node(i);
q->sc(p,1);
q=p;
}
Node last=new_node(0);
q->sc(last,1);
spl(last,Null);
}
void reverse(int l,int r)
{
Node x,y;
x=sel(l-1);
spl(x,Null);
y=sel(r+1);
spl(y,root);
rev(y->c[0]);
}
}*sp;
int main()
{
int n,m,l,r;cin>>n>>m;
sp=new splay(n);
while(m–)
{
scanf("%d %d",&l,&r);
sp->reverse(l,r);
}
sp->out();
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u5c31\u662f\u8bf4\u7ed9\u4f601\u5230n\u4e00\u6392\u6570\u6bcf\u6b21\u628a\u4ecel\u5230r\u7684\u6570\u53cd\u8fc7\u6765\u3002\u3002\u8ba9\u4f60\u8f93\u51fa\u6700\u540e\u7684\u90a3\u5217\u6570\u3002\u3002\u52a8\u6001\u8868\u3002\u3002\u660e\u663e\u7528splay\u3002\u3002\u6700\u8fd1\u521a\u5b66\u4e86splay\uff0c\u723d\u963f\u3002\u3002Code\uff1a#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int inf=~0U>>1;class splay{ int n; struct node { int k,s; bool d,rev; node*c[2],*p; node(){c[0]=c[1]=p=0;} void sc(node*_c,bool d) {c[d]=_c;_c->p=this;_c->d=d;} }*root,*Null,*Now,Data[130100]; typedef node* Node; Node new_node(int k) { Now->c[0]=Now->c[1]=Null; Now->rev=false;Now->s=1; Now->k=k;return Now++; } void rev(Node t) { if(t==Null) return; t->rev^=1; swap(t->c[0],t->c[1]); t->c[0]->d=0; t->c[1]->d=1; } void pus(Node t) { if(t->rev) rev(t->c[0]),rev(t->c[1]); t->rev=false; } void upd(Node […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/62"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=62"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/62\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=62"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=62"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=62"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}