OI - Play osu! on Your Tablet(HDU) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Play osu! on Your Tablet(HDU)

发表于 分类于 Valine：

什么都不会只能膜拜出题人的代码

# 题面

> HDU 6800

点击展开/折叠 题面翻译

你在玩音游(osu)。屏幕上会按顺序出现 $n$ 个节奏点 $(x_i,y_i)$，你需要移动手指去点击节奏点（你用左右手玩游戏）。

两个节奏点之间的距离定义为曼哈顿距离。你希望两只手移动的距离的总和最小，求这个最小值。

# 解析

不难想到DP—— $f_{i,j}$ 表示现在已经点击了前 $i$ 个点，此时当然有一只手在点 $i$，另一只手在点 $j$ （$j< i$）的最小总距离。这样可以有一个“我为人人”的转移方式（记 $d(i,j)$ 表示 $i,j$ 两点的曼哈顿距离）：

这样是 $O(n^2)$ 的 DP，状态和转移均无法优化，只能从一种名为“整体DP”的角度来优化——用数据结构维护DP数组，同时处理多次转移。

观察DP转移：

  • 第一个转移的第二维不变，且对于同一个 $i$，DP值的增加量都是固定的$d(i,i+1)$；
  • 第二个转移对于同一个 $i$，转移目标 $f_{i+1,i}$ 固定，可以换种写法：$f_{i+1,i}=\min\{f_{i,j}+d(i,j)\}$。

于是便有了下面两种方法（虽然第一种我写TLE了 QwQ）

- 线段树+非旋TREAP

用树套树来维护 $f_i$。

因为是曼哈顿距离，想到按一个点把平面分成 $4$ 块从而去掉绝对值。可以把 $f_{i,j}$ 的DP值附加在点 $(x_j,y_j)$ 上，然后就是要维护一个矩阵内 $(f+x+y,f+x-y,f-x+y,f-x-y)$ 这四种值的最小值了。

就可以横坐标离散化后用线段树，纵坐标直接作为 TREAP 的键值建立线段树套平衡树。

  1. 第一种转移，整棵线段树中的点的权值全部附加 $d(i,i+1)$；
  2. 新增一个点——枚举到 $i$ 的时候新增点为 $(f_{i+1,i},x_{i},y_{i})$，就把这个点插入树套树中；

查询就按 $(x_{i+1},y_{i+1})$ 把平面分成 $4$ 块求对应维护的最小值。另外比较特别的是 $f_{i,0}$ 这种状态，即有一只手还没用，特殊维护一下。

理论时间复杂度 $O(n\log^2 n)$，空间复杂度 $O(n\log n)$（不能是 $O(n\log^2 n)$ 会 MLE），不知道为什么跑得极慢。

- 归并树+线段树

仍然是把平面分成 $4$ 块，要维护一个矩阵内的信息。

先按横坐标排序然后按纵坐标建立归并树，这样归并树的每个节点中横坐标连续而纵坐标有序。既然纵坐标有序就可以对每个节点按纵坐标建立线段树，外层归并树因为横坐标连续，所以用法跟线段树基本上一样。

可以预先给每个点留个位置赋为 $+\infty$，这个点出现过后再改权值。

更新值就直接在归并树上向对应区间递归，每一层都要在对应的线段树上修改值。查询值比较特别，若询问点横坐标落在左区间，则计算右区间的点对它的贡献，然后递归左区间；落在右区间同理。

实现代码的时候要动态分配内存（线段树的节点个数为 $2n$），std 的指针+内存池分配内存运用得极好。

理论时间复杂度 $O(n\log^2n)$，空间复杂度 $O(n\log n)$，用了些STL的函数（inplace_merge 内置归并排序函数）跑得极快。

# 源代码

- 线段树+TREAP

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
/*Lucky_Glass*/
#include<cassert>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+10,M=1e9,SIZ=N*20;
typedef long long ll;
const ll INF=1ll<<60;
typedef pair<int,int> pii;
#define ci const int &
#define cl const ll &
#define fir first
#define sec second

struct FastIO {
    static const int S = 1e7;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar() {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) exit(0);
        return buf[pos++];
    }
    inline int xuint() {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c > 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x)
    {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos++] = x;
    }
    inline void wint(ll x)
    {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
        wchar('\n');
    }
    inline void wstring(const char *s)
    {
        while (*s) wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;

vector<int> unx;
int cas,n,nnod;
int pnt[N][2];

struct NODE{
    int nxt[2],fix,key,x,y;
    ll val[4],mn[4],add;
    inline int& operator [](ci i){return nxt[i];}
    void Update(ll cur){
        add+=cur;
        for(int i=0;i<4;i++) val[i]+=cur,mn[i]+=cur;
    }
}nod[N*20];
namespace TREAP{
    inline void PushUp(ci u){
        for(int i=0;i<4;i++){
            nod[u].mn[i]=nod[u].val[i];
            if(nod[u][0]) nod[u].mn[i]=min(nod[u].mn[i],nod[nod[u][0]].mn[i]);
            if(nod[u][1]) nod[u].mn[i]=min(nod[u].mn[i],nod[nod[u][1]].mn[i]);
        }
    }
    inline void PushDown(ci u){
        if(!nod[u].add) return;
        if(nod[u][0]) nod[nod[u][0]].Update(nod[u].add);
        if(nod[u][1]) nod[nod[u][1]].Update(nod[u].add);
        nod[u].add=0;
    }
    inline int NewNode(int x,int y,cl f){
        int p=++nnod;
        x=unx[x-1];
        nod[p].x=x,nod[p].y=y;
        nod[p].fix=rand(),nod[p].key=y;
        nod[p].add=0;
        nod[p][0]=nod[p][1]=0;
        nod[p].val[0]=nod[p].mn[0]=f+x+y;
        nod[p].val[1]=nod[p].mn[1]=f-x+y;
        nod[p].val[2]=nod[p].mn[2]=f+x-y;
        nod[p].val[3]=nod[p].mn[3]=f-x-y;
        return p;
    }
    inline pii SplitKey(ci u,ci key){
        if(!u) return make_pair(0,0);
        PushDown(u);
        if(nod[u].key<=key){
            pii res=SplitKey(nod[u][1],key);
            nod[u][1]=res.first,PushUp(u);
            res.first=u;
            return res;
        }
        else{
            pii res=SplitKey(nod[u][0],key);
            nod[u][0]=res.second,PushUp(u);
            res.second=u;
            return res;
        }
    }
    inline int Merge(ci u,ci v){
        if(!u || !v) return u|v;
        PushDown(u),PushDown(v);
        if(nod[u].fix>nod[v].fix){
            nod[u][1]=Merge(nod[u][1],v);
            PushUp(u);
            return u;
        }
        else{
            nod[v][0]=Merge(u,nod[v][0]);
            PushUp(v);
            return v;
        }
    }
    void Insert(int &rt,ci x,ci y,cl f){
        pii dv=SplitKey(rt,y);
        rt=Merge(dv.fir,Merge(NewNode(x,y,f),dv.sec));
    }
    ll Query(int &rt,ci i,ci le,ci ri){
        pii dv1=SplitKey(rt,ri),
            dv2=SplitKey(dv1.fir,le-1);
        ll res=dv2.sec? nod[dv2.sec].mn[i]:INF;
        rt=Merge(Merge(dv2.fir,dv2.sec),dv1.sec);
        return res;
    }
    ll Value(ci rt){
        if(!rt) return INF;
        PushDown(rt);
        ll res=(nod[rt].val[0]+nod[rt].val[3])/2;
        if(nod[rt][0]) res=min(res,Value(nod[rt][0]));
        if(nod[rt][1]) res=min(res,Value(nod[rt][1]));
        return res;
    }
}
struct SEGTREE{
    #define idx(l,r) (((l)+(r))|((l)!=(r)))
    int tr[N<<1];
    ll add[N<<1];
    void Update(ci le,ci ri,ll key){
        if(tr[idx(le,ri)]) nod[tr[idx(le,ri)]].Update(key);
        add[idx(le,ri)]+=key;
    }
    void PushDown(ci le,ci ri){
        int u=idx(le,ri),mi=(le+ri)>>1;
        if(!add[u]) return;
        Update(le,mi,add[u]),Update(mi+1,ri,add[u]);
        add[u]=0;
    }
    void Insert(ci le,ci ri,ci x,ci y,cl f){
        TREAP::Insert(tr[idx(le,ri)],x,y,f);
        if(le==ri) return;
        PushDown(le,ri);
        int mi=(le+ri)>>1;
        if(x<=mi) Insert(le,mi,x,y,f);
        else Insert(mi+1,ri,x,y,f);
    }
    ll Query(ci le,ci ri,ci xL,ci xR,ci kL,ci kR,ci i){
        if(xL>xR || kL>kR) return INF;
        if(xL<=le && ri<=xR) return TREAP::Query(tr[idx(le,ri)],i,kL,kR);
        PushDown(le,ri);
        int mi=(le+ri)>>1;
        if(xR<=mi) return Query(le,mi,xL,xR,kL,kR,i);
        if(mi<xL) return Query(mi+1,ri,xL,xR,kL,kR,i);
        return min(Query(le,mi,xL,xR,kL,kR,i),Query(mi+1,ri,xL,xR,kL,kR,i));
    }
    void Build(ci le,ci ri){
        tr[idx(le,ri)]=0;add[idx(le,ri)]=0;
        if(le==ri) return;
        int mi=(le+ri)>>1;
        Build(le,mi),Build(mi+1,ri);
    }
    ll Value(ci le,ci ri){return TREAP::Value(tr[idx(le,ri)]);}
    #undef idx
}Se;

int eABS(ci x){return x<0? -x:x;}
int Dist(ci a,ci b){return eABS(unx[pnt[a][0]-1]-unx[pnt[b][0]-1])+eABS(pnt[a][1]-pnt[b][1]);}
void Init(){
    unx.clear();
    nnod=n=0;
}
void Input(){
    n=io.xint();
    for(int i=1;i<=n;i++){
        pnt[i][0]=io.xint(),pnt[i][1]=io.xint();
        unx.push_back(pnt[i][0]);
    }
    sort(unx.begin(),unx.end());
    unx.erase(unique(unx.begin(),unx.end()),unx.end());
    for(int i=1;i<=n;i++)
        pnt[i][0]=lower_bound(unx.begin(),unx.end(),pnt[i][0])-unx.begin()+1;
}

int main(){
    //srand(time(NULL));
    cas=io.xint();
    while(cas--){
        Init();
        Input();
        int m=unx.size();
        Se.Build(1,m);
        ll fi0=0;
        for(int i=0;i<n;i++){
            ll res=min(
                min(
                    Se.Query(1,m,pnt[i+1][0],m,pnt[i+1][1],M,0)-unx[pnt[i+1][0]-1]-pnt[i+1][1],
                    Se.Query(1,m,1,pnt[i+1][0],pnt[i+1][1],M,1)+unx[pnt[i+1][0]-1]-pnt[i+1][1]
                ),min(
                    Se.Query(1,m,pnt[i+1][0],m,0,pnt[i+1][1],2)-unx[pnt[i+1][0]-1]+pnt[i+1][1],
                    Se.Query(1,m,1,pnt[i+1][0],0,pnt[i+1][1],3)+unx[pnt[i+1][0]-1]+pnt[i+1][1]
                )
            );
            //Se.Print(1,m);
            if(i){
                Se.Update(1,m,Dist(i,i+1));
                Se.Insert(1,m,pnt[i][0],pnt[i][1],min(fi0,res));
                fi0+=Dist(i,i+1);
            }
        }
        io.wint(min(Se.Value(1,m),fi0));
    }
    return 0;
}

- 归并树+线段树

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
/*Lucky_Glass*/
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;

#define ci const int &
typedef pair<int,int> pii;
typedef long long ll;
const int N=1e5+10;

namespace MEMORY{
    const int M=N*18,L=M*8;
    int pol[M],*npol;
    ll ifo[L],*nifo;
    inline void Reset(){npol=pol,nifo=ifo;}
    inline int* Ask32(int len){
        int *ret=npol;
        npol+=len;
        return ret;
    }
    inline ll* Ask64(int len){
        ll *ret=nifo;
        nifo+=len;
        return ret;
    }
}

int n,nuni;
ll dp[N];
pii seq[N],uni[N];

inline void UpdMin(ll &x,ll y){x>=y && (x=y);}
inline bool cmpY(ci u,ci v){return uni[u].second<uni[v].second;}

struct SEGMENT{
    int ytot,*yque;
    ll *ifo;
}seg[N<<1];

#define idx(l,r) (((l)+(r))|((l)!=(r)))

//初始化归并区间内线段树
void SegInitInner(SEGMENT &rt,ci le,ci ri){
    if(le==ri) return;
    int mi=(le+ri)>>1;
    SegInitInner(rt,le,mi),SegInitInner(rt,mi+1,ri);
    ll *cur=rt.ifo+(idx(le,ri)<<2);
    ll *lef=rt.ifo+(idx(le,mi)<<2);
    ll *rig=rt.ifo+(idx(mi+1,ri)<<2);
    //PushUp
    cur[0]=min(lef[0],rig[0]);
    cur[1]=min(lef[1],rig[1]);
    cur[2]=min(lef[2],rig[2]);
    cur[3]=min(lef[3],rig[3]);
}
void SegInitOuter(ci le,ci ri){
    static int ord[N];
    if(le<ri){
        int mi=(le+ri)>>1;
        SegInitOuter(le,mi),SegInitOuter(mi+1,ri);
        //归并区间[l,r]内所有点按纵坐标建归并树
        inplace_merge(ord+le,ord+mi+1,ord+ri+1,cmpY);
    }
    else ord[le]=le;
    SEGMENT &rt=seg[idx(le,ri)];
    //ytot：归并区间中不同的纵坐标的个数
    rt.ytot=1;
    for(int i=le+1;i<=ri;i++)
        rt.ytot+=cmpY(ord[i-1],ord[i]);
    //分配内存池，归并区间建线段树
    rt.yque=MEMORY::Ask32(rt.ytot);
    rt.ifo=MEMORY::Ask64(((rt.ytot-1)<<1|1)<<2); //(n-1)<<1|1 个节点，每个节点需要4个位置
    for(int i=le,j=0;i<=ri;j++){
        int u=ord[i++],y=uni[u].second,xL=uni[u].first,xR=xL;
        //取出纵坐标相同的一段点，求横坐标范围[xL,xR]
        for(int v;i<=ri && !cmpY(u,v=ord[i]);i++){
            int tmp=uni[v].first;
            if(tmp<xL) xL=tmp;
            else if(tmp>xR) xR=tmp;
        }
        rt.yque[j]=y;
        //单点初始化权
        ll *val=rt.ifo+(idx(j,j)<<2);
        val[0]=-xR-y; //左下
        val[1]=-xR+y; //左上
        val[2]=xL-y; //右下
        val[3]=xL+y; //右上
    }
    SegInitInner(rt,0,rt.ytot-1);
}
//查询点横坐标在左边
inline ll SegQueryRightInner(SEGMENT &rt,int x,int y){
    ll ret=LLONG_MAX;
    for(int L=0,R=rt.ytot-1;L<=R;){
        ll *cur=rt.ifo+(idx(L,R)<<2);
        //若递归出界
        if(y<=rt.yque[L]){
            UpdMin(ret,cur[3]-y);
            break;
        }
        else if(y>=rt.yque[R]){
            UpdMin(ret,cur[2]+y);
            break;
        }
        int M=(L+R)>>1;
        if(y<=rt.yque[M]){
            ll *rig=rt.ifo+(idx(M+1,R)<<2);
            UpdMin(ret,rig[3]-y);
            R=M;
        }
        else{
            ll *lef=rt.ifo+(idx(L,M)<<2);
            UpdMin(ret,lef[2]+y);
            L=M+1;
        }
    }
    if(ret!=LLONG_MAX) ret-=x;
    return ret;
}
//查询点横坐标在右边
inline ll SegQueryLeftInner(SEGMENT &rt,int x,int y){
    ll ret=LLONG_MAX;
    for(int L=0,R=rt.ytot-1;L<=R;){
        ll *cur=rt.ifo+(idx(L,R)<<2);
        if(y<=rt.yque[L]){
            UpdMin(ret,cur[1]-y);
            break;
        }
        else if(y>=rt.yque[R]){
            UpdMin(ret,cur[0]+y);
            break;
        }
        int M=(L+R)>>1;
        if(y<=rt.yque[M]){
            ll *rig=rt.ifo+(idx(M+1,R)<<2);
            UpdMin(ret,rig[1]-y);
            R=M;
        }
        else{
            ll *lef=rt.ifo+(idx(L,M)<<2);
            UpdMin(ret,lef[0]+y);
            L=M+1;
        }
    }
    if(ret!=LLONG_MAX) ret+=x;
    return ret;
}
inline ll SegQueryOuter(ci po){
    //查询点 (x,y)
    int x=uni[po].first,y=uni[po].second;
    ll ret=dp[po];
    for(int L=0,R=nuni-1;L<R;){
        int M=(L+R)>>1;
        if(po<=M){
            //向左边递归，计算右边的答案
            UpdMin(ret,SegQueryRightInner(seg[idx(M+1,R)],x,y));
            R=M;
        }
        else{
            //向右边递归……
            UpdMin(ret,SegQueryLeftInner(seg[idx(L,M)],x,y));
            L=M+1;
        }
    }
    return ret;
}
inline void SegUpdateInner(SEGMENT &rt,int y,ll val[]){
    for(int L=0,R=rt.ytot-1;L<=R;){
        ll *cur=rt.ifo+(idx(L,R)<<2);
        UpdMin(cur[0],val[0]);
        UpdMin(cur[1],val[1]);
        UpdMin(cur[2],val[2]);
        UpdMin(cur[3],val[3]);
        if(L==R) break;
        int M=(L+R)>>1;
        if(y<=rt.yque[M]) R=M;
        else L=M+1;
    }
}
inline void SegUpdateOuter(ci po){
    int x=uni[po].first,y=uni[po].second;
    ll v=dp[po],val[5]={v-x-y,v-x+y,v+x-y,v+x+y};
    for(int L=0,R=nuni-1;L<=R;){
        SegUpdateInner(seg[idx(L,R)],y,val);
        if(L==R) break;
        int M=(L+R)>>1;
        if(po<=M) R=M;
        else L=M+1;
    }
}

inline int ABS(ci x){return x<0? -x:x;}
void Solve(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&seq[i].first,&seq[i].second);
        uni[i]=seq[i];
        dp[i]=0;
    }
    sort(uni,uni+n);
    nuni=unique(uni,uni+n)-uni;
    MEMORY::Reset(); //内存池
    SegInitOuter(0,nuni-1); //线段树外层（归并树）
    ll ans=0,sum=0;
    int las=lower_bound(uni,uni+nuni,seq[0])-uni;
    for(int i=1;i<n;i++){
        ll dis=ABS(seq[i].first-seq[i-1].first)+ABS(seq[i].second-seq[i-1].second);
        int pos=lower_bound(uni,uni+nuni,seq[i])-uni;
        ll best=SegQueryOuter(pos)-dis;
        if(dp[las]>best){
            UpdMin(ans,dp[las]=best);
            SegUpdateOuter(las);
        }
        sum+=dis;
        las=pos;
    }
    printf("%lld\n",ans+sum);
}
int main(){
    int cas;scanf("%d",&cas);
    while(cas--) Solve();
    return 0;
}

THE END

Thanks for reading!

> Linked 零和Zero-Sum-Bilibili