SammyChu @ 2019-10-01 18:33:34
我要被
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
const int N=1e5;
inline void read(int &x)
{
int w=x=0;
char ch=getchar();
while(ch<'0'||'9'<ch)
w|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')
x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
x=w?-x:x;
}
int n,m,num[N|1],a,b;
int root,tot,L,R;
struct Treap
{
int val,siz;
bool rev;
int lc,rc,rnd;
}tr[N|1];
#define lid tr[id].lc
#define rid tr[id].rc
void upon(int id)
{
tr[id].siz=tr[lid].siz+tr[rid].siz+1;
}
int New(int x)
{
tr[++tot].rnd=rand();
tr[tot].val=x,tr[tot].siz=1;
return tot;
}
int top,stk[N|1];
void build(int x)
{
for(int i=1,id,now,ch;i<=x;++i)
{
id=New(num[i]),now=stk[top],ch=0;
while(top&&tr[id].rnd<=tr[now].rnd)
ch=stk[top],now=stk[--top];
lid=ch,upon(id);
if(top)
tr[now].rc=id,upon(now);
else
root=id;
stk[++top]=id;
}
}
void deal(int id)
{
tr[id].rev^=1,swap(lid,rid);
}
void down(int id)
{
if(!tr[id].rev)
return;
deal(lid),deal(rid);
tr[id].rev=0;
}
void split(int id,int x,int &l,int &r)
{
if(!id)
l=r=0;
else
{
down(id);
int y=x-tr[lid].siz-1;
if(y>=0)
l=id,split(rid,y,rid,r);
else
r=id,split(lid,x,l,lid);
upon(id);
}
}
int merge(int l,int r)
{
if(!l||!r)
return l+r;
int id=tr[l].rnd<=tr[r].rnd?l:r;
down(id);
if(id==l)
rid=merge(rid,r),upon(id);
else
lid=merge(l,lid),upon(id);
return id;
}
void reverse(int x,int y)
{
int id;
split(root,y,L,R),split(L,x-1,L,id);
deal(id),root=merge(merge(L,id),R);
}
void print(int id)
{
down(id);
if(lid)
print(lid);
printf("%d ",tr[id].val);
if(rid)
print(rid);
}
int main()
{
srand(time(0));
read(n),read(m);
for(int i=1;i<=n;++i)
num[i]=i;
build(n);
while(m--)
read(a),read(b),reverse(a,b);
print(root);
return 0;
}by _Album_ @ 2019-10-01 18:45:12
加三目运算符
by _Album_ @ 2019-10-01 18:47:05
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<deque>
#include<queue>
#include<stack>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<vector>
#include<cmath>
#define ll long long
#define N 1000010
#define I inline
using namespace std;
struct Treap{
int cnt , root;
#define lson(x) node[x].l
#define rson(x) node[x].r
struct Node{
int dis;
int rd;
int size;
int l , r;
Node(int dis = 0) : dis(dis) , rd(rand()) , size(1) , l(0) , r(0){}
}node[N];
I void update(int x){
node[x].size = (lson(x) ? node[lson(x)].size : 0) + (rson(x) ? node[rson(x)].size : 0) + 1; //这些三目运算符不加会出错
}
void split(int n , int k , int &x , int &y){
if(!n) x = y = 0;
else if(node[n].dis >= k){
split(lson(n) , k , x , y);
lson(n) = y;
update(y = n);
}
else {
split(rson(n) , k , x , y);
rson(n) = x;
update(x = n);
}
}
int merge(int x , int y){
if(!x || !y){
return x + y;
}
if(node[x].rd < node[y].rd){
rson(x) = merge(rson(x) , y);
update(x);
return x;
}
else{
lson(y) = merge(x , lson(y));
update(y);
return y;
}
}
I void insert(int k){
int x , y;
split(root , k , x , y);
node[++ cnt] = Node(k);
root = merge(merge(x , cnt) , y);
}
I void remove(int k){
int x , y , z;
split(root , k , x , y);
split(y , k + 1 , y , z);
y = merge(lson(y) , rson(y));
root = merge(merge(x , y) , z);
}
I int rank(int k){
int x , y , ans;
split(root , k , x , y);
ans = (x ? node[x].size : 0) + 1;
root = merge(x , y);
return ans;
}
int search(int n , int r){
int rank = (lson(n) ? node[lson(n)].size : 0) + 1; //还有这里
if(r == rank) return node[n].dis;
else if(r < rank) return search(lson(n) , r);
else return search(rson(n) , r - rank);
}
inline int lower(int k) {
int x, y, t;
split(root, k, x, y);
t = x;
while (rson(t)) t = rson(t);
root = merge(x, y);
return node[t].dis;
}
inline int upper(int k) {
int x, y, t;
split(root, k + 1, x, y);
t = y;
while (lson(t)) t = lson(t);
root = merge(x, y);
return node[t].dis;
}
}treap;
int main(){
int n , opt , x;
scanf("%d" , &n);
for(int i = 1; i <= n; i ++){
scanf("%d%d" , &opt , &x);
switch(opt){
case 1 :
treap.insert(x);
break;
case 2 :
treap.remove(x);
break;
case 3 :
printf("%d\n" , treap.rank(x));
break;
case 4 :
printf("%d\n" , treap.search(treap.root , x));
break;
case 5 :
printf("%d\n" , treap.lower(x));
break;
case 6 :
printf("%d\n" , treap.upper(x));
break;
}
}
return 0;
}by SammyChu @ 2019-10-01 19:26:05
@Payphone—X 多谢
by SammyChu @ 2019-10-01 19:27:15
不过好像还是错的……
by Zofia @ 2019-10-02 09:24:55
不要再学用处不大的知识点！
不要再学用处不大的知识点！
不要再学用处不大的知识点！
by 千瑞 @ 2019-11-25 18:16:09
多了一个人？
by Richard21477 @ 2020-07-17 09:53:00
split写错了
void split(int loc,int sze,int &x,int &y){
if (loc==0){
x=y=0;
return;
}
down(loc);
if (all[all[loc].l].s>=sze){
y=loc;
split(all[loc].l,sze,x,all[loc].l);
}
else{
x=loc;
split(all[loc].r,sze,all[loc].r,y);
}
update(loc);
}（不保证我是对的）
by Richard21477 @ 2020-07-17 10:16:07
倒数第四行改一下，sze-all[all[loc].l].s-1