目录
@description@
『新的风暴已经出现，怎么能够停滞不前』——你决定去攻击小怪兽的巢⽳。
怪兽有⼀⾏ n 个巢⽳，从 1 到 n 编号，第 i 个巢⽳的防御⼒为 Ri。 ⼀开始你在降⽣在第 x 个巢⽳（此时巢⽳ x 已被破坏），攻击⼒为 Rx。每次你有三种操作：
- 攻击你左边的第⼀个没有被摧毁的巢⽳，要求你的攻击⼒要⼤于等于它的防御⼒。
- 攻击你右边的第⼀个没有被摧毁的巢⽳，要求你的攻击⼒要⼤于等于它的防御⼒。
- 增加你的攻击⼒，这会占用你 K 次操作，你的攻击⼒会变成两边第⼀个没有被摧毁的巢⽳防御⼒的较小值（不存在算作 inf）。
令 Ex 等于你出⽣在 x 的时候，捣毁所有巢⽳需要的最少次数。
现在有 Q 个询问，每次有两种操作：
- 交换巢⽳ x 和 x + 1。
- 给出两个数字 x 和 y，求 \(\sum^{y}_{i=x} E_i\) 的值。
input
第⼀⾏两个整数 n 和 k。 第⼆⾏ n 个整数，表示 Ri。 之后若⼲⾏（q ⾏），开始⼀个数 op 表示操作类型，如果 op = 1，接下来⼀个数 x。 否则 op = 2，接下来两个数字 x 和 y。output
每⾏⼀个整数表示答案。sample input
5 3 2 3 1 4 1 2 2 2 2 1 5 1 2 2 2 2 2 1 5sample output 7 38 13 41100% 的分数满⾜ n ≤ 10^5, k ≤ 10^6, Ri ≤ 10^9, q ≤ 2 ∗ 10^5, x < n。
@solution@
考虑对于一个给定的 x，怎么求解 Ex。设改变了 c 次攻击力，则显然 Ex = c*k + (n-1)。
于是问题转变为对于给定的 x，改变了多少次攻击力。一种想法是通过递推转移。令 f[x] 表示从 x 开始改变的攻击力次数。
找到 x 左边第一个比 Rx 大的数的位置 lm，右边第一个比它 Rx 大的数的位置 rm，则设 p 为 lm 与 rm 之中对应着较小的数的位置。 于是有着 f[x] = f[p] + 1。另一种想法是考虑一个数对另一个数的贡献。考虑 x，找到 x 右边第一个大于或等于它的数 y。
则对于 x 与 y 之间的数，它们肯定要在 x 这个地方改变一次攻击力。所以 x 对于 x 与 y 之间的数产生贡献。 但是注意假如 Rx = Ry 的时候，按照上述计算方法是会在 Rx 算了一次，Ry 又重复算了一次。但其实 Rx 与 Ry 是在同一次改变攻击力。所以要特判。考虑修改时怎么维护。假如交换 x 与 x+1，不妨令 R[x] > R[x+1]（反过来同理）。
可以发现对于 x 基本什么不会都不会变。对于 x+1，我们先通过递推找到它新的 Ex。然后通过线段树对它所影响到的区间进行修改。 同时我们也可以通过线段树上二分 O(log^2) 求出 x 之前/之后最靠近 x 的比 Rx 大的数。 具体操作怎么实现的可以参考代码。一个小细节：假如完全按照上面实现，你需要在线段树上既实现找最靠近 x 大于 Rx 又要实现找最靠近 x 大于等于 Rx。
对于等于的情况，我们不妨维护一个链表，将 x 前/后最靠近的等于 Rx 的连接起来，在交换的时候简单维护一下即可。@accepted code@
#include#include using namespace std;typedef long long ll;const int MAXN = 100000;int R[MAXN + 5];struct segtree { struct node{ int mx, le, ri; int tag; ll sum; }t[4*MAXN + 5]; void pushup(int x) { t[x].mx = (R[t[x<<1].mx] > R[t[x<<1|1].mx]) ? t[x<<1].mx : t[x<<1|1].mx; t[x].sum = t[x<<1].sum + t[x<<1|1].sum; } void build(int x, int l, int r) { t[x].le = l, t[x].ri = r, t[x].tag = t[x].sum = 0; if( l == r ) { t[x].mx = l; return ; } int mid = (l + r) >> 1; build(x<<1, l, mid); build(x<<1|1, mid+1, r); pushup(x); } void pushdown(int x) { if( t[x].tag ) { t[x<<1].tag += t[x].tag, t[x<<1].sum += t[x].tag*(t[x<<1].ri-t[x<<1].le+1); t[x<<1|1].tag += t[x].tag, t[x<<1|1].sum += t[x].tag*(t[x<<1|1].ri-t[x<<1|1].le+1); t[x].tag = 0; } } void add(int x, int l, int r, int d) { if( l > t[x].ri || r < t[x].le ) return ; if( l <= t[x].le && t[x].ri <= r ) { t[x].tag += d; t[x].sum += d*(t[x].ri-t[x].le+1); return ; } pushdown(x); add(x<<1, l, r, d), add(x<<1|1, l, r, d); pushup(x); } void update(int x, int p) { if( p > t[x].ri || p < t[x].le ) return ; if( t[x].le == t[x].ri ) return ; pushdown(x); update(x<<1, p), update(x<<1|1, p); pushup(x); } int query_mx(int x, int p, int type) { if( t[x].le == t[x].ri ) return (R[t[x].le] > R[p]) ? t[x].le : -1; pushdown(x); if( type ) { if( p >= t[x<<1].ri ) return query_mx(x<<1|1, p, type); else if( p < t[x<<1].le ) { if( R[t[x].mx] <= R[p] ) return -1; else return (R[t[x<<1].mx] > R[p]) ? query_mx(x<<1, p, type) : query_mx(x<<1|1, p, type); } else { int q = query_mx(x<<1, p, type); if( q == -1 ) return query_mx(x<<1|1, p, type); else return q; } } else { if( p <= t[x<<1|1].le ) return query_mx(x<<1, p, type); else if( p > t[x<<1|1].ri ) { if( R[t[x].mx] <= R[p] ) return -1; else return (R[t[x<<1|1].mx] > R[p]) ? query_mx(x<<1|1, p, type) : query_mx(x<<1, p, type); } else { int q = query_mx(x<<1|1, p, type); if( q == -1 ) return query_mx(x<<1, p, type); else return q; } } } int query_sum(int x, int l, int r) { if( l > t[x].ri || r < t[x].le ) return 0; if( l <= t[x].le && t[x].ri <= r ) return t[x].sum; pushdown(x); return query_sum(x<<1, l, r) + query_sum(x<<1|1, l, r); }}T;int d[MAXN + 5], lst[MAXN + 5], nxt[MAXN + 5], adj[MAXN + 5];int main() { freopen("attack.in", "r", stdin); freopen("attack.out", "w", stdout); int n, k; scanf("%d%d", &n, &k); for(int i=1;i<=n;i++) scanf("%d", &R[i]), d[i] = R[i]; sort(d + 1, d + n + 1); int dsiz = unique(d + 1, d + n + 1) - d - 1; for(int i=1;i<=n;i++) R[i] = lower_bound(d + 1, d + dsiz + 1, R[i]) - d; R[0] = R[n+1] = dsiz + 1; for(int i=1;i<=dsiz;i++) adj[i] = n + 1; for(int i=n;i>=1;i--) { nxt[i] = adj[R[i]]; lst[adj[R[i]]] = i; adj[R[i]] = i; } for(int i=1;i<=dsiz;i++) lst[adj[i]] = 0; T.build(1, 0, n+1); for(int i=1;i<=n;i++) { int x = T.query_mx(1, i, 0), y = T.query_mx(1, i, 1); if( x >= lst[i] ) T.add(1, x + 1, i - 1, 1); if( y <= nxt[i] ) T.add(1, i + 1, y - 1, 1); else T.add(1, i + 1, nxt[i] - 1, 1); } int op; while( scanf("%d", &op) == 1 ) { if( op == 2 ) { int l, r; scanf("%d%d", &l, &r); printf("%lld\n", 1LL*k*T.query_sum(1, l, r) + 1LL*(n-1)*(r-l+1)); } else { int x, y; scanf("%d", &x); y = x + 1; if( R[x] == R[y] ) continue; if( R[x] > R[y] ) { int p = T.query_mx(1, y, 1); if( p <= nxt[y] ) T.add(1, y + 1, p - 1, -1); int xs = T.query_sum(1, x, x), ys = T.query_sum(1, y, y); T.add(1, x, x, -xs), T.add(1, y, y, xs-ys); swap(R[x], R[y]), T.update(1, x), T.update(1, y); swap(nxt[x], nxt[y]), swap(lst[x], lst[y]); lst[nxt[x]] = nxt[lst[x]] = x; lst[nxt[y]] = nxt[lst[y]] = y; int q = T.query_mx(1, x, 0); T.add(1, x, x, R[q] > R[y] ? T.query_sum(1, y, y) + 1 : T.query_sum(1, q, q) + 1); if( q >= lst[x] ) T.add(1, q + 1, x - 1, 1); } else { int p = T.query_mx(1, x, 0); if( p >= lst[x] ) T.add(1, p + 1, x - 1, -1); int xs = T.query_sum(1, x, x), ys = T.query_sum(1, y, y); T.add(1, x, x, ys-xs), T.add(1, y, y, -ys); swap(R[x], R[y]), T.update(1, x), T.update(1, y); swap(nxt[x], nxt[y]), swap(lst[x], lst[y]); lst[nxt[x]] = nxt[lst[x]] = x; lst[nxt[y]] = nxt[lst[y]] = y; int q = T.query_mx(1, y, 1); T.add(1, y, y, R[q] > R[x] ? T.query_sum(1, x, x) + 1 : T.query_sum(1, q, q) + 1); if( q <= nxt[y] ) T.add(1, y + 1, q - 1, 1); } } }}
@details@
一道思维量适中，应用线段树的，算是比较典型的题吧。
只是对于大于小于、等于等情况讨论有些令人头疼。