歡迎訪(fǎng)問(wèn) My Luogu Space。

---

【題目大意】

有 \(n\) 個(gè)身高為 \([1,\ n]\) 的且各不相同的人排成一個(gè)序列。

有兩種操作：

讓位置 \(x,\ y\) 的人交換位置。

給定一個(gè)范圍\([l,\ r]\)，詢(xún)問(wèn)身高在該范圍內(nèi)的所有人是否排成了一個(gè)連續(xù)的序列。

輸出操作二的詢(xún)問(wèn)。

---

【題解】

線(xiàn)段樹(shù)。

操作一很簡(jiǎn)單。

對(duì)于操作二：

我們發(fā)現(xiàn)身高在 \([l,\ r]\) 的人一共有 \(k=(r-l+1)\) 個(gè)。

我們只需要找到身高在這個(gè)范圍內(nèi)，且站在最左端和最右端的人的坐標(biāo)。

\((\)右坐標(biāo)\(-\)左坐標(biāo) \(+1)\) 的值如果等于 \(k\)，那么這 \(k\) 個(gè)人就剛好排成了一個(gè)連續(xù)的序列。

如果大于就是這 \(k\) 個(gè)人當(dāng)中被插入了一些其他人，不可能有小于的情況出現(xiàn)。

因此我們需要支持查詢(xún)坐標(biāo)的最大和最小值。

建一棵以身高為下標(biāo)的線(xiàn)段樹(shù)，值為身高對(duì)應(yīng)的坐標(biāo)，區(qū)間查詢(xún)坐標(biāo)的最大和最小值。

---

【代碼】

// output format !! // long long !! #include <bits/stdc++.h> #define ls (x<<1) #define rs (x<<1|1) const int MAXN = 200000+10; using std::max; using std::min; using std::swap; struct TREE{int Max, Min;}t[MAXN*4];int n, m, h[MAXN], loc[MAXN], L, R;void build(int x, int l, int r){if(l == r) return t[x].Max = t[x].Min = loc[l], void();int mid = (l+r)>>1;build(ls, l, mid), build(rs, mid+1, r);t[x].Max = max(t[ls].Max, t[rs].Max);t[x].Min = min(t[ls].Min, t[rs].Min); } void query(int x, int l, int r, int ql, int qr){if(ql<=l && r<=qr){L = min(L, t[x].Min);R = max(R, t[x].Max);return;}int mid = (l+r)>>1;if(ql <= mid) query(ls, l, mid, ql, qr);if(qr > mid) query(rs, mid+1, r, ql, qr); } void modify(int x, int l, int r, int p, int v){if(l == r) return t[x].Max = t[x].Min = v, void();int mid = (l+r)>>1;if(p <= mid) modify(ls, l, mid, p, v);else modify(rs, mid+1, r, p, v);t[x].Max = max(t[ls].Max, t[rs].Max);t[x].Min = min(t[ls].Min, t[rs].Min); } int main(){scanf("%d%d", &n, &m);for(int i=1; i<=n; ++i) scanf("%d", h+i), loc[h[i]] = i;build(1, 1, n);while(m--){int op, x, y;scanf("%d%d%d", &op, &x, &y);if(op == 1){modify(1, 1, n, h[y], x);modify(1, 1, n, h[x], y);swap(h[x], h[y]), swap(loc[h[x]], loc[h[y]]);}else{L = 1e9, R = 0;query(1, 1, n, x, y);if(R-L+1 == y-x+1) puts("YES");else puts("NO");}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/bosswnx/p/10988258.html

總結(jié)

以上是生活随笔為你收集整理的题解 DTOJ #1438. 矮人排队（lineup）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。