列队 总结——调了我几十天的平衡树题
Sweetlemon
2018-10-16 08:38:14
列队，是$\text{NOIP 2017 TG Day 2 T3}$。去年由于我~~什么数据结构都不懂~~极其蒟蒻，直接打了$30$分的暴力。
今年我学了$\text{Treap}$~~（但依然极其蒟蒻）~~，于是试着拿这道题来练手。
本题我根据$\text{Splay}$的分裂-合并的思想，自己~~意淫~~了一种“节点分裂$\text{Treap}$”，主要是为了解决$nm$过大，空间无法适应的问题，即一个节点代表连续的若干个人，储存在$\text{Treap}$中，如果这个节点所代表的区间中有人出队，则把这个节点分裂成$3$份。
思想很简单，但是代码实现起来极其困难。主要是排序关键字的赋值问题，在这个参数上我调试了很久，也找~~（偷）~~了很多的测试数据，终于调试成功。其实这个参数应该是在纸上计算得出的，因此今后写代码还是应该多用草稿纸推导呢。
下面附上~~极丑的~~代码，代码中罕见地写了注释，可见我不停地揣测代码逻辑的痛苦。最慢的点跑了$1340\text{ms}$，终于明白这题为什么要$2s$时限了。
另外，这份代码有$247$行，真可谓又臭又长。当然最后的getrr()是调试函数。
```cpp
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#define MAXN 300005
#define MAXNOD 4000005
#define INF 12345678901234ll
typedef long long ll;
using namespace std;
struct Node{
ll l;
ll lx;
int pr;
int lc,rc;
int sz,cnt;
#define L(x) ((tr[(x)]).l)
#define LC(x) ((tr[(x)]).lc)
#define RC(x) ((tr[(x)]).rc)
#define X(x) ((tr[(x)]).lx)
#define PR(x) ((tr[(x)]).pr)
#define SZ(x) ((tr[(x)]).sz)
#define CN(x) ((tr[(x)]).cnt)
};
Node tr[MAXNOD];
int troot[MAXN];
int pcnt=0;
int mpos;
ll maxl[MAXN]={0};
int build(void);
int new_node(ll pos,ll x,int cnt);
void insert(int &root,ll pos,ll x,int cnt);
void del(int &root,ll x);
ll split(int treenum,int node,int x); //Split the node from x
void del_rank(int& root,int treenum,int rank);
//1...x-1;x;x+1...CN(node)
ll get_rank(int root,int treenum,int rank);
int get_rr(int root,int rank);
void zig(int &x);
void zag(int &x);
void calcsz(int x);
void updatesz(int root,ll x);
int main(void){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
troot[0]=build();
mpos=0;
srand(time(0));
for (int i=1;i<=n;i++){
troot[i]=build();
insert(troot[i],1,ll(i-1)*m+1,m-1);
maxl[i]=m;
insert(troot[0],++mpos,ll(i)*m,1);
}
for (int i=0;i<q;i++){
int x,y;
scanf("%d%d",&x,&y);
if (y==m){
printf("%lld\n",get_rank(troot[0],0,x+1));
}
else {
printf("%lld\n",get_rank(troot[x],x,y+1));
}
}
return 0;
}
int new_node(ll pos,ll x,int cnt){
int root;
pcnt++;
root=pcnt;
LC(root)=RC(root)=0;
L(root)=pos,X(root)=x,SZ(root)=CN(root)=cnt;
PR(root)=rand();
return root;
}
int build(void){
int pninf,pinf;
pninf=new_node(-INF,0,1);
pinf=new_node(INF,0,1);
LC(pinf)=pninf,SZ(pinf)=2;
if (PR(LC(pinf))>PR(pinf))
zig(pinf);
return pinf;
}
void zig(int &x){
int y=LC(x);
LC(x)=RC(y),RC(y)=x;
calcsz(x),calcsz(y);
x=y;
}
void zag(int &x){
int y=RC(x);
RC(x)=LC(y),LC(y)=x;
calcsz(x),calcsz(y);
x=y;
}
void calcsz(int x){
SZ(x)=CN(x)+SZ(LC(x))+SZ(RC(x));
}
void insert(int &root,ll pos,ll x,int cnt){
if (!root){
root=new_node(pos,x,cnt);
return;
}
if (L(root)==pos)
//Impossible
return;
if (pos<L(root)){
insert(LC(root),pos,x,cnt);
if (PR(LC(root))>PR(root))
zig(root);
else
calcsz(root);
}
else { //pos>L(root)
insert(RC(root),pos,x,cnt);
if (PR(RC(root))>PR(root))
zag(root);
else
calcsz(root);
}
}
void del(int &root,ll x){
if (!root)
return;
if (L(root)==x){
if (LC(root) && RC(root)){
if (PR(LC(root))>PR(RC(root))){
zig(root);
del(RC(root),x);
}
else {
zag(root);
del(LC(root),x);
}
calcsz(root);
}
else
root=(LC(root)|RC(root));
return;
}
if (x<L(root)){
del(LC(root),x);
calcsz(root);
}
else {
del(RC(root),x);
calcsz(root);
}
}
ll split(int treenum,int node,int x){
if (!node)
return INF;
if (CN(node)==1){
ll ans=X(node);
del(troot[treenum],L(node));
if (treenum){
del_rank(troot[0],treenum,treenum+1);
//Move to the treenum column.
}
insert(troot[0],++mpos,ans,1);
return ans;
}
if (x<CN(node)){ //Back part
insert(troot[treenum],L(node)+x,X(node)+x,CN(node)-x);
}
CN(node)=x-1;
updatesz(troot[treenum],L(node));//Update the size from the root.
ll ans=X(node)+x-1;
insert(troot[0],++mpos,ans,1);
if (treenum){
del_rank(troot[0],treenum,treenum+1);
}
if (!CN(node)) //Delete the front part if it doesn't exist
del(troot[treenum],L(node));
return ans;
}
ll get_rank(int root,int treenum,int rank){
if (!root)
return INF;
if (rank<=SZ(LC(root))){
ll ans=get_rank(LC(root),treenum,rank);
calcsz(root);
return ans;
}
if (rank<=SZ(LC(root))+CN(root))
return split(treenum,root,rank-SZ(LC(root)));
ll ans=get_rank(RC(root),treenum,rank-SZ(LC(root))-CN(root));
calcsz(root);
return ans;
}
void del_rank(int& root,int treenum,int rank){
if (!root)
return;
if (rank<=SZ(LC(root))){
del_rank(LC(root),treenum,rank);
calcsz(root);
return;
}
if (rank<=SZ(LC(root))+CN(root)){
//insert:root,position(ll),x,cnt
insert(troot[treenum],++maxl[treenum],X(root),CN(root));
del(root,L(root));
return;
}
del_rank(RC(root),treenum,rank-SZ(LC(root))-CN(root));
calcsz(root);
return;
}
void updatesz(int root,ll x){
if (!root)
return;
if (x==L(root)){
calcsz(root);
return;
}
if (x<L(root)){
updatesz(LC(root),x);
calcsz(root);
return;
}
//x>L(root)
updatesz(RC(root),x);
calcsz(root);
}
int get_rr(int root,int rank){
if (!root)
return -1;
if (rank<=SZ(LC(root))){
return get_rr(LC(root),rank);
}
if (rank<=SZ(LC(root))+CN(root)){
return X(root);
}
return get_rr(RC(root),rank-SZ(LC(root))-CN(root));
}
```