真ikun,代码求hackQAQ
查看原帖
真ikun,代码求hackQAQ
670584
Zhangikun楼主2023/10/20 21:04
#include<bits/stdc++.h>
#define lt(cur) tree[cur].ls
#define rt(cur) tree[cur].rs
#define int long long 
using namespace std;
const int cxk=2e5+5;
int root,tot,m;
struct ikun
{
    int lt,rt,pt,ls,rs,sz;
}tree[cxk];
int newpt(int lt,int rt)
{
    tree[++tot]={lt,rt,rand(),0,0,1};
    return tot;
}
void pushup(int cur)
{
    tree[cur].sz=tree[lt(cur)].sz+tree[rt(cur)].sz+1;
}
void split_lt(int cur,int&x,int&y,int val) 
{
    if(cur==0)
    {
        x=y=0;
        return;
    }
    if(tree[cur].lt<=val)
    {
        x=cur;
        split_lt(rt(cur),rt(cur),y,val);
    }
    else
    {
        y=cur;
        split_lt(lt(cur),x,lt(cur),val);
    }
    pushup(cur);
}
void split_rt(int cur,int&x,int&y,int val) 
{
    if(cur==0)
    {
        x=y=0;
        return;
    }
    if(tree[cur].rt<=val)
    {
        x=cur;
        split_rt(rt(cur),rt(cur),y,val);
    }
    else
    {
        y=cur;
        split_rt(lt(cur),x,lt(cur),val);
    }
    pushup(cur);
}
void merge(int&cur,int x,int y)
{
    if(x==0||y==0)
    {
        cur=x+y;
        return;
    }
    if(tree[x].pt<=tree[y].pt)
    {
        cur=x;
        merge(rt(cur),rt(cur),y);
    }
    else
    {
        cur=y;
        merge(lt(cur),x,lt(cur));
    }
    pushup(cur);
}
void insert(int x,int y)
{
    int r1=0,r2=0,r3=newpt(x,y);
    split_lt(root,r1,r2,x);
    merge(r1,r1,r3);
    merge(root,r1,r2);
}
int erase(int lt,int rt)
{
	int r1=0,r2=0,r3=0,lst=tree[root].sz;
	split_lt(root,r1,r2,lt-1); 
	split_lt(r2,r3,r2,rt); 
	merge(root,r1,r2);
	r1=r2=r3=0;
	split_rt(root,r1,r2,lt-1);
	split_rt(r2,r3,r2,rt);
	merge(root,r1,r2);
	insert(lt,rt);
	return lst-tree[root].sz+1;
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	srand(time(0));
    cin>>m;
    char opt;
    for(int lt,rt;m--;)
    {
    	cin>>opt;
    	if(opt=='B')
    		cout<<tree[root].sz<<"\n";
    	else
    	{
    		cin>>lt>>rt;
    		cout<<erase(lt,rt)<<"\n";
		}
	}
}
2023/10/20 21:04
加载中...