Walls 防壁 - 题目 - 黑暗爆炸OJ

一下子想不到什么数据结构来维护一车东西，因为考虑对于每个线段对于每一个点都是需要考虑贡献的，所以状态数就已经是 $O(n ^ 2)$ 了，所以要考虑减少状态。

考虑对于一个点 $x$，在区间 $[l, r]$ 是合法的当且仅当 $l \le x \le r$，发现没有什么特别的性质。考虑点 $r = l + len$，那么发现对于上述式子可以变成 $x - len \le l \le x$，诶，线段和点相互转换了。

我们考虑当前用点去匹配线段的情况，我们尝试缩减状态，很明显三条同向的线段是可以变成开头和结尾两条的，那么我们的线段就变成了左右横跳的情况。

但是我们 $\tt len$ 是会变的，我们考虑对于一个点 $l$ 在其左边的线段肯定是横跳到原来的 $x$，对于右边的线段就是 $x - len$，当长度变得足够大的时候我们会发现两条线段有重合部分了，对于这种情况我们其实只要跳到上线段右端点就已经是最优的。

所以我们考虑可以对于距离最近的线段进行删除，因为上述就已经不是反复横跳的情况了。

我们不妨将两条连续线段的编号记成下面线段的编号，为了快速删除我们使用链表维护所有线段，考虑位置 $x, y = pre(x)$ 的情况。

  • 如果 $y$ 是开始线段，为了保留交线，所以我们删除 $y$。

  • 如果 $x$ 是最后的线段，我们直接删除 $x$ 就可以了。

  • 如果 $x, y$ 是中间的线段，考虑保留交线之后 $pre_y \to y \to x \to suf_x$ 是同向的，我们需要删除 $x, y$。

最后计算答案的时候我们发现需要分类讨论第一条线段在左边还是右边，但是只要我们触碰到了一条左边的线段，那么就可以进行反复横跳，我们直接暴力遍历前两条线段就可以了。

最后的贡献就是线段的总长减去线段条数减去当前的 $\tt len$，我们对于这个 $\tt len$ 离线一下就可以了。

其实代码没有很难写，也不是很长，但是听 $\tt macesuted$ 讲感觉挺恐怖的。

事实上能删除就不需要打标记了，毕竟有能直接支持快速删除的数据结构链表了。

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
#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
	namespace Read {
//		#define Fread
		#ifdef Fread
		const int Siz = (1 << 21) + 5;
		char *iS, *iT, buf[Siz];
		#define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
		#define getchar gc
		#endif
		template <typename T>
		void r1(T &x) {
		    x = 0;
			char c(getchar());
			int f(1);
			for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
			for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
			x *= f;
		}
		template <typename T, typename...Args>
		void r1(T &x, Args&...arg) {
			r1(x), r1(arg...);
		}
		#undef getchar
	}

using namespace Read;

const int maxn = 2e5 + 5;
int n, m;
struct Node {
    int l, r, id;
    int operator < (const Node &z) const {
        return r - l < z.r - z.l;
    }
}a[maxn];
int pre[maxn], suf[maxn], Q;
int ln[maxn], st;
int vis[maxn];
typedef pair<int, int> pr;
typedef long long int64;
priority_queue<pr, vector<pr>, greater<pr>> q;
int ts(0);

int64 rs[maxn], ans;

int64 Ask(int l,int r) {
    int64 res = ans, tln = ts;
    for(int _ = 0, now = st; _ < 2 && now; now = suf[now], ++ _) {
        if(pre[now]) -- tln, res -= abs(ln[pre[now]] - ln[now]);
        if(r < ln[now]) {
            int64 tmp = ln[now] - r;
            l += tmp, r += tmp;
            res += tmp;
        }
        else if(l > ln[now]) {
            int64 tmp = l - ln[now];
            l -= tmp, r -= tmp;
            res += tmp;
        }
    }
    return res - tln * (r - l);
}

void Getdel(int lim) {
    while(!q.empty() && ts >= 2) {
        auto tmp = q.top();
        if(tmp.first > lim) return ;
        q.pop();
        int x = tmp.second;
        if(vis[x] || x == st) continue;
        int y = pre[x];
        if(y == st) {
            vis[y] = 1;
            pre[x] = 0, st = x;
            -- ts;
            ans -= abs(ln[x] - ln[y]);
            continue;
        }
        if(suf[x] == 0) {
            vis[x] = 1;
            suf[y] = 0;
            -- ts;
            ans -= abs(ln[x] - ln[y]);
            continue;
        }
        int pr = pre[y], sf = suf[x];
        ans -= abs(ln[x] - ln[y]);
        ans -= abs(ln[pr] - ln[y]);
        ans -= abs(ln[x] - ln[sf]);
        ans += abs(ln[pr] - ln[sf]);
        suf[pr] = sf, pre[sf] = pr;
        vis[y] = vis[x] = 1;
        q.push({abs(ln[pr] - ln[sf]), sf});
    }
}

signed main() {
	int i, j;
	r1(n, Q);
	for(i = 1; i <= n; ++ i) r1(a[i].l, a[i].r), a[i].id = i;
    sort(a + 1, a + n + 1);
    while(Q --) {
        int x; r1(x);
        if(!m) { ln[++ m] = x; continue; }
        if(x == ln[m]) continue;
        if(m > 1 && (ln[m - 1] < ln[m]) == (ln[m] < x)) ln[m] = x;
        else ln[++ m] = x;
    }
    st = 1;
    for(i = 1; i <= m; ++ i) {
        if(i > 1) pre[i] = i - 1;
        if(i < m) suf[i] = i + 1;
        if(i > 1) {
            ++ ts;
            q.push({abs(ln[i] - ln[i - 1]), i});
            ans += abs(ln[i] - ln[i - 1]);
        }
    }
    for(i = 1; i <= n; ++ i) Getdel(a[i].r - a[i].l), rs[a[i].id] = Ask(a[i].l, a[i].r);
    for(i = 1; i <= n; ++ i) printf("%lld\n", rs[i]);
	return 0;
}

}


signed main() { return Legendgod::main(), 0; }//