Gypsophila @ 2018-12-23 17:47:21
自己测了几个小样例没啥毛病，交上去就是过不了
有神仙帮忙挑个错吗？
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int n, m, cnt;
struct node {
int tag, siz, d, rnd; node *ch[2];
inline void upd() {
int ret = 1;
if(ch[0]) ret += ch[0]->siz;
if(ch[1]) ret += ch[1]->siz;
siz = ret;
}
inline void pushd() {
if(!tag) return ; swap(ch[0], ch[1]);
if(ch[0]) ch[0]->tag ^= 1;
if(ch[1]) ch[1]->tag ^= 1;
tag = 0;
}
} pool[N];
inline int siz(node *r) {
if(r) return r->siz; return 0;
}
struct FhqTreap {
node *root;
inline node* merge(node *p, node *q) {
if(!p) return q; if(!q) return p;
if(p->rnd < q->rnd) { p->pushd(); p->ch[1] = merge(p->ch[1], q); p->upd(); return p; }
else { q->pushd(); q->ch[0] = merge(q->ch[0], p); q->upd(); return q; }
}
inline void split(node *r, int k, node *&p, node *&q) {
if(!r) { p = q = NULL; return ; } r->pushd();
if(siz(r->ch[0]) < k) p = r, split(r->ch[1], k - siz(r->ch[0]) - 1, r->ch[1], q);
else q = r, split(r->ch[0], k, p, r->ch[0]);
r->upd();
}
inline void output(node *r) {
r->pushd();
if(r->ch[0]) output(r->ch[0]);
printf("%d ", r->d);
if(r->ch[1]) output(r->ch[1]);
}
} T;
int main() {
scanf("%d %d", &n, &m);
T.root = &pool[0]; T.root->siz = 1; T.root->d = 1;
for(int i = 2; i <= n; i++) {
node *p = &pool[++cnt];
p->siz = 1, p->rnd = rand();
p->d = i, p->ch[0] = p->ch[1] = NULL;
T.root = T.merge(T.root, p);
}
for(int i = 1; i <= m; i++) {
int l, r; scanf("%d %d", &l, &r);
node *p, *q, *s;
T.split(T.root, l - 1, p, q);
T.split(q, r - l + 1, q, s);
q->tag ^= 1;
T.merge(p, T.merge(q, s));
} T.output(T.root);
return 0;
}by 雪幽幽 @ 2018-12-23 18:36:27
%%%
by flowerletter @ 2018-12-24 22:11:06
%%%
by flowerletter @ 2018-12-24 22:13:33
稍微压了一下行就5多行了
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
const int inf = 2147483647;
#define Int register int
#define lson tree[x].son[0]
#define rson tree[x].son[1]
struct Node{
int lazy,size,rnd,son[2],sum;
}tree[MAXN];
int n,q,cnt,root,tmp;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
inline void Reverse_One(int x){tree[x].lazy^=1,swap(lson,rson);}
inline void Up(int x){if(x) tree[x].size=tree[lson].size+tree[rson].size+1;}
inline void Build(int &x,int delta){tree[x=++cnt].rnd=rand()<<15|rand();tree[x].sum=delta;tree[x].size=1;}
inline void Down(int x){if(x){if(tree[x].lazy) Reverse_One(lson),Reverse_One(rson);tree[x].lazy=0;}}
inline void Merge(int &x,int l,int r){
if(!l || !r) x=l+r;
else if(tree[l].rnd<tree[r].rnd) Down(x=l),Merge(rson,rson,r),Up(x);
else Down(x=r),Merge(lson,l,lson),Up(x);
}
inline void Split(int x,int &l,int &r,int k){
if(!k) l=0,r=x;
else if(tree[x].size==k) l=x,r=0;
else if(k<=tree[lson].size) Down(r=x),Split(lson,l,lson,k),Up(x);
else Down(l=x),Split(rson,rson,r,k-tree[lson].size-1),Up(x);
}
inline void Reverse(int l,int r){
int x,y,z;
Split(root,x,y,r),Split(x,z,x,l-1);
Reverse_One(x);
Merge(x,z,x),Merge(root,x,y);
}
inline void Out(int x){
if(!x) return ;Down(x);
Out(lson),printf("%d ",tree[x].sum);Out(rson);
}
int main(){
srand(1021*1210);
n=read(),q=read();tree[0].sum=tree[0].rnd=inf;
for(Int i=1;i<=n;++i) Build(tmp,i),Merge(root,root,tmp);
for(Int i=1;i<=q;++i){
int x=read(),y=read();
Reverse(x,y);
}Out(root);
return 0;
}by flowerletter @ 2018-12-24 22:13:51
50多行……
by COUPDETAT @ 2019-02-13 10:15:35
using namespace std;
const int MAXN=100101;
int n,m,root=0;
void read(int &n)
{
char c='+';int x=0;bool flag=0;
while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
flag==1?n=-x:n=x;
}
int ch[MAXN][3],val[MAXN],pri[MAXN],siz[MAXN],tag[MAXN],sz;
void update(int x)
{
siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];
}
void pushdown(int x)
{
if (x&&tag[x])
{
tag[x]^=1;
swap(ch[x][0],ch[x][1]);
if (ch[x][0])
tag[ch[x][0]]^=1;
if (ch[x][1])
tag[ch[x][1]]^=1;
}
}
int new_node(int v)
{
siz[++sz]=1;
val[sz]=v;
pri[sz]=rand();
return sz;
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
pushdown(x),pushdown(y);
if(pri[x]<pri[y])
{
ch[x][1]=merge(ch[x][1],y);
update(x);
return x;
}
else
{
ch[y][0]=merge(x,ch[y][0]);
update(y);
return y;
}
}
void split(int now,int k,int &x,int &y)
{
if(!now) x=y=0;
else
{
pushdown(now);
if(val[now]<=k)
x=now,split(ch[now][1],k,ch[now][1],y);
else
y=now,split(ch[now][0],k,x,ch[now][0]);
update(now);
}
}
int kth(int now,int k)
{
while(1)
{
if(k<=siz[ch[now][0]])
now=ch[now][0];
else if(k==siz[ch[now][0]]+1)
return now;
else k-=siz[ch[now][0]]+1,now=ch[now][1];
}
}
void rever(int l,int r)
{
int a,b,c,d;
split(root,r,a,b);
split(a,l-1,c,d);
tag[d]^=1;
root=merge(merge(c,d),b);
}
void print(int x)
{
if(!x) return ;
pushdown(x);
print(ch[x][0]);
printf("%d ",val[x]);
print (ch[x][1]);
}
int main()
{
srand((unsigned)time(NULL));
read(n),read(m);
for(int i=1;i<=n;i++)
{
root=merge(root,new_node(i));
}
while(m--)
{
int a,b;
read(a),read(b);
rever(a,b);
}
print(root);
return 0; }
by COUPDETAT @ 2019-02-13 10:16:11
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100101;
int n,m,root=0;
void read(int &n)
{
char c='+';int x=0;bool flag=0;
while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
flag==1?n=-x:n=x;
}
int ch[MAXN][3],val[MAXN],pri[MAXN],siz[MAXN],tag[MAXN],sz;
void update(int x)
{
siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];
}
void pushdown(int x)
{
if (x&&tag[x])
{
tag[x]^=1;
swap(ch[x][0],ch[x][1]);
if (ch[x][0])
tag[ch[x][0]]^=1;
if (ch[x][1])
tag[ch[x][1]]^=1;
}
}
int new_node(int v)
{
siz[++sz]=1;
val[sz]=v;
pri[sz]=rand();
return sz;
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
pushdown(x),pushdown(y);
if(pri[x]<pri[y])
{
ch[x][1]=merge(ch[x][1],y);
update(x);
return x;
}
else
{
ch[y][0]=merge(x,ch[y][0]);
update(y);
return y;
}
}
void split(int now,int k,int &x,int &y)
{
if(!now) x=y=0;
else
{
pushdown(now);
if(val[now]<=k)
x=now,split(ch[now][1],k,ch[now][1],y);
else
y=now,split(ch[now][0],k,x,ch[now][0]);
update(now);
}
}
int kth(int now,int k)
{
while(1)
{
if(k<=siz[ch[now][0]])
now=ch[now][0];
else if(k==siz[ch[now][0]]+1)
return now;
else k-=siz[ch[now][0]]+1,now=ch[now][1];
}
}
void rever(int l,int r)
{
int a,b,c,d;
split(root,r,a,b);
split(a,l-1,c,d);
tag[d]^=1;
root=merge(merge(c,d),b);
}
void print(int x)
{
if(!x) return ;
pushdown(x);
print(ch[x][0]);
printf("%d ",val[x]);
print (ch[x][1]);
}
int main()
{
srand((unsigned)time(NULL));
read(n),read(m);
for(int i=1;i<=n;i++)
{
root=merge(root,new_node(i));
}
while(m--)
{
int a,b;
read(a),read(b);
rever(a,b);
}
print(root);
return 0;
} by COUPDETAT @ 2019-02-13 10:16:41
同fhq求救