_cyh_ @ 2024-06-15 20:10:32
评测记录
code:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
mt19937 myrand(time(0));
int n, m, root = 0;
struct node {
int val;
unsigned pri;
int cnt, size;
int lc, rc;
bool flag;
} nd[MAXN];
int num_node;
int New(int val) {
num_node++;
nd[num_node].val = val;
nd[num_node].pri = myrand();
nd[num_node].cnt = nd[num_node].size = 1;
nd[num_node].lc = nd[num_node].rc = 0;
nd[num_node].flag = false;
return num_node;
}
void Update(int x) {
nd[x].size = nd[nd[x].lc].size + nd[x].cnt + nd[nd[x].rc].size;
}
void Down(int x) {
if (!nd[x].flag)return;
swap(nd[x].lc, nd[x].rc);
nd[nd[x].lc].flag = !nd[nd[x].lc].flag;
nd[nd[x].rc].flag = !nd[nd[x].rc].flag;
nd[x].flag = false;
}
void split_val(int rt, int k, int &x, int &y) {
if (rt == 0) {
x = y = 0;
return;
}
Down(rt);
if (nd[rt].val <= k) {
x = rt;
split_val(nd[rt].rc, k, nd[rt].rc, y);
} else {
y = rt;
split_val(nd[rt].lc, k, x, nd[rt].lc);
}
Update(rt);
}
int merge(int x, int y) {
if (!x)return y;
if (!y)return x;
Down(x);
Down(y);
if (nd[x].pri > nd[y].pri) {
nd[x].rc = merge(nd[x].rc, y);
Update(x);
return x;
} else {
nd[y].lc = merge(x, nd[y].lc);
Update(y);
return y;
}
}
void split_rk(int rt, int rk, int &x, int &y) {
if (rt == 0) {
x = y = 0;
return;
}
Down(rt);
if (nd[nd[rt].lc].size + nd[rt].cnt >= rk) {
y = rt;
split_rk(nd[rt].lc, rk, x, nd[rt].lc);
} else {
x = rt;
split_rk(nd[rt].rc, rk - nd[nd[rt].lc].size - nd[rt].cnt, nd[rt].rc, y);
}
Update(rt);
}
void insert(int val) {
int a = 0, b = 0, c = 0;
split_val(root, val, a, c);
split_val(a, val - 1, a, b);
if (b) {
nd[b].cnt++;
Update(b);
} else {
b = New(val);
}
root = merge(merge(a, b), c);
}
void Rotate(int l, int r) {
int a, b, c;
split_rk(root, r, b, c);
split_rk(b, l - 1, a, b);
nd[b].flag = !nd[b].flag;
root = merge(merge(a, b), c);
}
void getans(int rt) {
if (rt == 0)return;
Down(rt);
getans(nd[rt].lc);
if (rt > 0)cout << rt - 0 << " ";
getans(nd[rt].rc);
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
insert(i);
}
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
Rotate(l, r);
}
getans(root);
return 0;
}by ACcepted917 @ 2024-06-15 20:29:30
#include<bits/stdc++.h>
using namespace std;
//P3391
const int N=1e6+10;
#define fup(l,r) for(int i=l;i<=r;i++)
//用静态数组来模拟树
int cnt,root;
std::mt19937 rnd(233);
struct node{
int val,pri,ls,rs,size,lazy;
}t[N];
int newNode(int x){
t[++cnt]={x,rnd(),0,0,1,0};//初始化一个新结点
return cnt;
}
void update(int u){
t[u].size=t[t[u].ls].size+t[t[u].rs].size+1;
}
//懒标记下移
void pushdown(int u){
if(t[u].lazy){
swap(t[u].ls,t[u].rs);
t[t[u].ls].lazy ^= 1;
t[t[u].rs].lazy ^= 1;
t[u].lazy=0;//清空懒标记
}
}
//排名分裂--按顺序分裂
void Split(int u,int x,int& L,int& R){
if(u==0){
L=R=0;
return;
}
pushdown(u);
if(t[t[u].ls].size+1<=x){
L=u;
Split(t[u].rs,x-(t[t[u].ls].size+1),t[u].rs,R);
}
else{
R=u;
Split(t[u].ls,x,L,t[u].ls);
}
update(u);
}
int Merge(int L,int R){
if(L==0||R==0) return L+R;
if(t[L].pri>t[R].pri){
pushdown(L);
t[L].rs=Merge(t[L].rs,R);
update(L);
return L;
}
else{
pushdown(R);
t[R].ls=Merge(L,t[R].ls);
update(R);
return R;
}
}
//中序遍历
void inorder(int u){
if(u==0) return ;
pushdown(u);
inorder(t[u].ls);
printf("%d ",t[u].val);
inorder(t[u].rs);
}
int x,y,l,r,p;
int main(){
int n,m;
cin>>n>>m;
fup(1,n){
root=Merge(root,newNode(i));
}
while(m--){
scanf("%d%d",&x,&y);
Split(root,x-1,l,p);
Split(p,y-x+1,p,r);
t[p].lazy^=1;
root=Merge(l,Merge(p,r));
}
inorder(root);
return 0;
}以上是我的代码，@_cyh_
你可以参考一下。
by ACcepted917 @ 2024-06-15 20:32:04
评测结果
by _cyh_ @ 2024-06-15 20:37:06
@ACcepted917 已过，谢谢
by _cyh_ @ 2024-06-15 20:37:35
已关