让蒟蒻见识到了常数大+滥用STL的危害。
<法一>很久之前的Splay
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 110000
#define INF 2147483647
int n,m,l,r,fa[maxn],c[maxn][2],val[maxn],head,tail,root,tot,siz[maxn];
bool delta[maxn];
inline void Maintain(int x)
{
if(x)
siz[x]=siz[c[x][0]]+siz[c[x][1]]+1;
}
inline void Pushdown(int x)
{
if(x&&delta[x])
{
if(c[x][0])
delta[c[x][0]]^=true;
if(c[x][1])
delta[c[x][1]]^=true;
swap(c[x][0],c[x][1]);
delta[x]=false;
}
}
inline void NewNode(int &x,int Fa,int key)
{
x=++tot;
fa[x]=Fa;
val[x]=key;
siz[x]=1;
}
inline void Rotate(int x,bool flag)//flag指左旋还是右旋；
{
int y=fa[x];
Pushdown(x);
Pushdown(y);
c[y][!flag]=c[x][flag];
fa[c[x][flag]]=y;
if(fa[y])
c[fa[y]][c[fa[y]][1]==y]=x;
fa[x]=fa[y];
c[x][flag]=y;
fa[y]=x;
Maintain(y);
}
inline void Splay(int x,int goal)//指要将x旋转为goal节点的子节点 :双旋！！！！
{
if(!x||x==goal)
return;
int y;
Pushdown(x);
while((y=fa[x])!=goal)
{
if(fa[y]==goal)
Rotate(x,c[y][0]==x);
else
{
if((c[y][0]==x)==(c[fa[y]][0]==y))
Rotate(y,c[fa[y]][0]==y);
else
{
Rotate(x,c[y][0]==x);
y=fa[x];
}
Rotate(x,c[y][0]==x);
}
}
Maintain(x);
if(!goal)
root=x;
}
inline int Find(int &root,int key)
{
int x=root;
while(c[x][val[x]<key])
{
if(val[x]==key)
return x;
x=c[x][val[x]<key];
}
return x;
}
inline void Insert(int &root,int key)
{
if(!root)
{
NewNode(root,0,key);
return;
}
int x=Find(root,key);
if(val[x]==key)
{
Splay(x,0);
return;
}
NewNode(c[x][val[x]<key],x,key);
Splay(c[x][val[x]<key],0);
}
inline int Kth(int &root,int K)
{
int x=root;
while(1)
{
Pushdown(x);
int Siz0=siz[c[x][0]];
if(K<=Siz0)
x=c[x][0];
else if(K==Siz0+1)
break;
else
{
K-=(Siz0+1);
x=c[x][1];
}
}
return x;
}
inline void Print(int x)
{
if(!x)
return;
Pushdown(x);
Print(c[x][0]);
printf("%d ",val[x]);
Print(c[x][1]);
Maintain(x);
return;
}
int main()
{
scanf("%d%d",&n,&m);
Insert(root,0);
for(int i=1;i<=n;i++)
Insert(root,i);
Insert(root,n+1);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
Splay(Kth(root,l),0);
Splay(Kth(root,r+2),root);
delta[c[c[root][1]][0]]^=true;
Pushdown(c[c[root][1]][0]);
}
Splay(Kth(root,1),0);
Splay(Kth(root,n+2),root);
Print(c[c[root][1]][0]);
return 0;
}
<法二>块状链表维护翻转标记，维护块形态。50'
#include<cstdio>
#include<list>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int f,c;
inline void Read(int &x){
c=0;f=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
x*=f;
}
void Write(int x){
if(x<10)putchar(x+'0');
else{Write(x/10);putchar(x%10+'0');}
}
typedef vector<int>::iterator VER;
struct Node
{
bool Reversed;
vector<int>v;
Node(){Reversed=0;}
};
list<Node>List;
int n,m,tmp[100001],x,y,sz,L,R;
typedef list<Node>::iterator LER;
typedef pair<LER,VER> Point;
inline Point Find(const int &p)
{
int cnt=0; LER i=List.begin();
for(;i!=List.end();++i)
{
cnt+=(*i).v.size();
if(cnt>=p)
{
cnt-=(*i).v.size();
for(VER j=(*i).v.begin();j!=(*i).v.end();++j)
if((++cnt)==p)
return make_pair(i,j);
}
}
--i; return make_pair(i,(*i).v.end());
}
void Makeblock()
{
sz=sqrt(n); int tot=1; if(!sz) sz=1;
for(;tot*sz<n;++tot)
{
LER End=List.insert(List.end(),Node());
(*End).v.assign(tmp+(tot-1)*sz+1,tmp+tot*sz+1);
}
LER End=List.insert(List.end(),Node());
(*End).v.assign(tmp+(tot-1)*sz+1,tmp+n+1);
}
inline void pushdown(const LER &p)
{
if((*p).Reversed)
{
reverse((*p).v.begin(),(*p).v.end());
(*p).Reversed=0;
}
}
inline LER Split(const int &p)
{
Point Pos=Find(p);
pushdown(Pos.first);
if(Pos.second==(*Pos.first).v.begin()) return Pos.first;
LER newB=List.insert(Pos.first,Node());
(*newB).v.assign((*Pos.first).v.begin(),Pos.second);
(*Pos.first).v.erase((*Pos.first).v.begin(),Pos.second);
return Pos.first;
}
void Printans()
{
for(LER i=List.begin();i!=List.end();++i)
{
if((*i).Reversed)
for(VER j=(*i).v.end()-1;j>=(*i).v.begin();--j)
Write(*j),putchar(' ');
else
for(VER j=(*i).v.begin();j!=(*i).v.end();++j)
Write(*j),putchar(' ');
}
puts("");
}
inline void Merge(LER &a,LER &b)
{
pushdown(a);
pushdown(b);
(*a).v.insert((*a).v.begin(),(*b).v.begin(),(*b).v.end());
List.erase(b);
}
inline void MaintainList()
{
LER curB=List.begin();
while(curB!=List.end())
{
LER nexB=curB; ++nexB;
while(nexB!=List.end()
&&(*curB).v.size()+(*nexB).v.size()<=(sz<<1))
{
Merge(nexB,curB);
curB=nexB;
++nexB;
}
++curB;
}
}
inline void Reverse()
{
Read(L); Read(R);
if(L==R) return;
Point Pl=Find(L),Pr=Find(R);
if(Pl.first==Pr.first)
{
pushdown(Pl.first);
reverse(Pl.second,++Pr.second);
return;
}
LER Lb=Split(L),Rb=Split(R+1);
for(LER i=Lb;i!=Rb;++i)
(*i).Reversed^=1;
reverse(Lb,Rb);
MaintainList();
}
int main()
{
Read(n);
Read(m);
for(int i=1;i<=n;++i)
tmp[i]=i;
Makeblock();
for(int i=1;i<=m;++i)
Reverse();
Printans();
return 0;
}