Liveddd's Blog

愛にできることはまだあるかい

P3960 [NOIP2017 提高组] 列队

发表于 更新于 分类于
本文字数： 3k 阅读时长 ≈ 7 分钟

平衡树的应用。

我们很容易将模型抽象成有 $n+1$ 个序列，然后我们对其进行区间移动操作。这似乎很容易用平衡树解决。但是发现空间根本开不下。

一个有用的 trick：我们可以尝试用每个节点储存一个区间。我们需要用这个区间中的子区间时，我们只需要将这个区间拆开就行。这样我们可以保证点的个数始终是 $\mathcal O(n+q)$ 的。

实现用 FHQ-Treap 或 Splay 都可以。FHQ-Treap 写起来似乎要简单一点，但是我却因为某个 merge 中变量写反了而调了很久。。。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<iostream>
#include<cstdio>
#include<ctime>
#define ll long long
using namespace std;
const int N=3e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct Node
{
    ll l,r;
    int son[2];
    int val,cnt;
}tr[N<<2];
int n,m,q;
int tot,rt[N],x,y,z;
inline void pushup(int x)
{
    tr[x].cnt=tr[tr[x].son[0]].cnt+tr[tr[x].son[1]].cnt+(tr[x].r-tr[x].l+1);
}
inline int insert(ll l,ll r)
{
    tr[++tot].cnt=r-l+1;
    tr[tot].l=l;
    tr[tot].r=r;
    tr[tot].val=rand();
    return tot;
}
int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(tr[x].val<tr[y].val)
    {
        tr[x].son[1]=merge(tr[x].son[1],y);
        pushup(x);
        return x;
    }
    else
    {
        tr[y].son[0]=merge(x,tr[y].son[0]);
        pushup(y);
        return y;
    }
}
void split(int p,int k,int &x,int &y)
{
    if(!p)return x=y=0,void();
    if(tr[tr[p].son[0]].cnt>=k)
        y=p,split(tr[p].son[0],k,x,tr[p].son[0]);
    else
    {
        int res=k-tr[tr[p].son[0]].cnt;
        int len=tr[p].r-tr[p].l+1;
        if(res<len)
        {
            int q=insert(tr[p].l+res,tr[p].r);
            tr[p].r=tr[p].l+res-1;
            tr[p].son[1]=merge(q,tr[p].son[1]);
            pushup(p);
        }
        x=p,split(tr[p].son[1],res-len,tr[p].son[1],y);
    }
    pushup(p);
}

int main()
{
    srand(time(0));
    read(n,m,q);
    for(int i=1;i<=n;i++)
        rt[i]=insert(1ll*(i-1)*m+1,1ll*i*m-1);
    for(int i=1;i<=n;i++)
        rt[n+1]=merge(rt[n+1],insert(1ll*i*m,1ll*i*m));
    while(q--)
    {
        int a,b;
        read(a,b);
        if(b==m)
        {
            split(rt[n+1],a,x,y);
            split(x,a-1,x,z);
            printf("%lld\n",tr[z].l);
            rt[n+1]=merge(x,merge(y,z));
        }
        else
        {
            split(rt[a],b,x,y);
            split(x,b-1,x,z);
            printf("%lld\n",tr[z].l);
            int x1,y1,z1;
            split(rt[n+1],a,x1,y1);
            split(x1,a-1,x1,z1);
            rt[a]=merge(x,merge(y,z1));
            rt[n+1]=merge(x1,merge(y1,z));
        }
    }
    return 0;
}