wh__ @ 2024-08-05 16:59:04
#include <bits/stdc++.h>
#define mod 1000000007
typedef long long LL;
typedef double D;
using namespace std;
const int SIZE=1000010;
// mt19937 Rand(time(0));
int n,m;
int tot;
int root,l,r,p;
struct treap
{
int ls,rs,val,ran;
int siz;
bool tag;
}t[SIZE<<1];
int read()
{
int res=0,x=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')x=-1;ch=getchar();}
while(isdigit(ch)){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
return x*res;
}
void up(int id)
{
t[id].siz=t[t[id].ls].siz+t[t[id].rs].siz+1;
return;
}
void pushDown(int id)
{
if(t[id].tag)
{
t[id].tag=0;
swap(t[id].ls,t[id].rs);
t[t[id].ls].tag^=1;
t[t[id].rs].tag^=1;
}
return;
}
void split(int id,int x,int &l,int &r)
{
if(!id)
{
l=r=0;
return ;
}
if(t[t[id].ls].siz<=x)
{
pushDown(id);
l=id;
split(t[id].rs,x-t[t[id].ls].siz-1,t[id].rs,r);
up(id);
}
else
{
pushDown(id);
r=id;
split(t[id].ls,x,l,t[id].ls);
up(id);
}
return;
}
int merge(int l,int r)
{
if(!l || !r) return l+r;
if(t[l].ran<=t[r].ran)
{
pushDown(l);
t[l].rs=merge(t[l].rs,r);
up(l);
return l;
}
else
{
pushDown(r);
t[r].ls=merge(l,t[r].ls);
up(r);
return r;
}
}
void insert(int i)
{
t[++tot].val=i;
t[tot].siz=1;
t[tot].ran=rand();
t[tot].tag=0;
split(root,i,l,r);
root=merge(merge(l,tot),r);
return;
}
void reversal(int x,int y)
{
split(root,x-2,l,r);
split(r,y-x,r,p);
t[r].tag^=1;
root=merge(l,merge(r,p));
return;
}
void midout(int id)
{
if(!id) return ;
pushDown(id);
midout(t[id].ls);
printf("%d ",t[id].val);
midout(t[id].rs);
return;
}
signed main()
{
srand(time(0));
n=read(),m=read();
for(int i=1;i<=n;i++) insert(i);
while(m--)
{
int x=read(),y=read();
reversal(x,y);
}
midout(root);
return 0;
}
先试了mt19937 time(0),又试了rand(),但结果都随机。
PS: 不是很懂随机数
by Luliuyan114514 @ 2024-08-05 19:43:41
@wh__ 用这个试一下（需要引入<chrono>和<random>）：
mt19937 mt;
mt.seed((chrono::system_clock::now().time_since_epoch().count()));
double x=uniform_real_distribution<double>(/*下界*/,/*上界*/)(mt);by wh__ @ 2024-08-05 19:51:12
@Luliuyan114514 感谢dalao!
by wh__ @ 2024-08-05 19:59:09
@Luliuyan114514 但是具体咋用？我自己试了还是能被自己的对拍数据hack掉。。。hack数据还是随机结果。。。
hack：
22 28
12 13
14 20
7 13
8 19
5 20
19 20
8 14
3 16
11 15
19 19
19 19
2 3
20 20
3 19
8 19
5 9
5 18
6 11
2 9
18 22
8 11
6 21
10 18
1 21
3 19
1 1
6 22
4 15
#include <bits/stdc++.h>
#define mod 1000000007
typedef long long LL;
typedef double D;
using namespace std;
const int SIZE=1000010;
// mt19937 Rand(time(0));
int n,m;
int tot;
int root,l,r,p;
struct treap
{
int ls,rs,val,ran;
int siz;
bool tag;
}t[SIZE<<1];
int read()
{
int res=0,x=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')x=-1;ch=getchar();}
while(isdigit(ch)){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
return x*res;
}
void up(int id)
{
t[id].siz=t[t[id].ls].siz+t[t[id].rs].siz+1;
}
void pushDown(int id)
{
if(t[id].tag)
{
t[id].tag=0;
swap(t[id].ls,t[id].rs);
t[t[id].ls].tag^=1;
t[t[id].rs].tag^=1;
}
}
void split(int id,int x,int &l,int &r)
{
if(!id)
{
l=r=0;
return ;
}
if(t[t[id].ls].siz<=x)
{
pushDown(id);
l=id;
split(t[id].rs,x-t[t[id].ls].siz-1,t[id].rs,r);
up(id);
}
else
{
pushDown(id);
r=id;
split(t[id].ls,x,l,t[id].ls);
up(id);
}
}
int merge(int l,int r)
{
if(!l || !r) return l+r;
if(t[l].ran<=t[r].ran)
{
pushDown(l);
t[l].rs=merge(t[l].rs,r);
up(l);
return l;
}
else
{
pushDown(r);
t[r].ls=merge(l,t[r].ls);
up(r);
return r;
}
}
mt19937 mt;
void insert(int i)
{
t[++tot].val=i;
// t[tot].ran=Rand()%mod;
// t[tot].ran=rand()%mod;
double x=uniform_real_distribution<double>(0,mod)(mt);
t[tot].ran=(LL)x;
// printf("%d->%d\n",tot,t[tot].ran);
t[tot].siz=1;
t[tot].tag=0;
split(root,i,l,r);
root=merge(merge(l,tot),r);
}
void reversal(int x,int y)
{
split(root,x-2,l,r);
split(r,y-x,p,r);
t[p].tag^=1;
root=merge(l,merge(p,r));
}
void midout(int id)
{
if(!id) return ;
pushDown(id);
midout(t[id].ls);
printf("%d ",t[id].val);
midout(t[id].rs);
}
signed main()
{
mt.seed((chrono::system_clock::now().time_since_epoch().count()));
// double x=uniform_real_distribution<double>(/*下界*/,/*上界*/)(mt);
// freopen("data.in","r",stdin);
// freopen("1.out","w",stdout);
// srand(time(0));
n=read(),m=read();
for(int i=1;i<=n;i++) insert(i);
while(m--)
{
int x=read(),y=read();
reversal(x,y);
}
midout(root);
return 0;
}