年轻人的第一个 *3500。抄题解的。
考虑选出一个字段 \([l, r]\) 然后计算可以产生贡献的地方。那么就是 \(\underset{i \in [l, r]} \max pre_i + 1\) 和 \(\underset{i \in [l, r]} \min suf_i - 1\) ，称其为 \(f_{l, r}\) 和 \(g_{l, r}\)。这些就是左端点和右端点的边界。对于每一个左端点维护最大可行产生贡献的区间 \([i, p]\)，再使用单调栈维护 \(\max\) 和 \(\min\) 这写东西然后产生的贡献是：
\[\sum^p_{k = i} (i - f_{i, k})(g_{i, k} - k) \]这个东西，然后我们经典拆柿子有：
\[\sum_{k = i}^p ig_{i, k} + kf_{i, k} - ik - f_{i, k}g_{i, k} \]使用线段树维护区间推平，区间和、区间 \(ia_i\) 和区间点积即可，时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define lc x << 1
#define rc x << 1 | 1
using namespace std;
typedef long long ll;
const int _ = 1e5 + 5, mod = 1e9 + 7;
int power (int x, int y) {
int ret = 1;
for ( ; y; y >>= 1, x = 1ll * x * x % mod)
if (y & 1) ret = 1ll * ret * x % mod;
return ret;
}
void add (int & x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
int mul (int x, int y) { return 1ll * x * y % mod; }
ll Su (int l, int r) { return 1ll * (r - l + 1) * (l + r) / 2; }
int tag[_ << 2][2];
struct Info { ll s[4]; } tr[_ << 2];
Info I;
Info operator + (Info x, Info y) {
Info z;
rep(i, 0, 3) z.s[i] = x.s[i] + y.s[i];
return z;
}
void apply (int x, int l, int r, int k, int op) {
tr[x].s[op] = 1ll * (r - l + 1) * k;
if (op == 0) tr[x].s[2] = 1ll * k * Su(l, r);
tr[x].s[3] = tr[x].s[op ^ 1] * k;
tag[x][op] = k;
return ;
}
void pushdown (int x, int l, int mid, int r) {
rep(i, 0, 1) if (tag[x][i])
apply(lc, l, mid, tag[x][i], i),
apply(rc, mid + 1, r, tag[x][i], i), tag[x][i] = 0;
}
void modify (int x, int l, int r, int ql, int qr, int k, int op) {
if (ql <= l && r <= qr) return apply(x, l, r, k, op);
int mid = (l + r) >> 1; pushdown(x, l, mid, r);
if (ql <= mid) modify(lc, l, mid, ql, qr, k, op);
if (qr > mid) modify(rc, mid + 1, r, ql, qr, k, op);
tr[x] = tr[lc] + tr[rc];
}
Info query (int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tr[x];
int mid = (l + r) >> 1; Info ret = I; pushdown(x, l, mid, r);
if (ql <= mid) ret = ret + query(lc, l, mid, ql, qr);
if (qr > mid) ret = ret + query(rc, mid + 1, r, ql, qr);
return ret;
}
int n, tot, a[_], tmp[_];
int lst[_], pre[_], suf[_];
int top, stk[_];
int suc[_], prv[_];
ll ans;
map <int, int> buc;
int main() {
/*
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
黛拉可玛莉·岗德森布莱德，一亿年一遇美少女。
*/
rep(i, 0, 3) I.s[i] = 0;
cin >> n;
rep(i, 1, n) {
scanf("%d", & a[i]);
if (!buc[a[i]]) buc[a[i]] = ++ tot;
a[i] = buc[a[i]];
}
rep(i, 1, n) pre[i] = lst[a[i]] + 1, lst[a[i]] = i;
rep(i, 1, tot) lst[i] = n + 1;
per(i, n, 1) suf[i] = lst[a[i]] - 1, lst[a[i]] = i;
per(i, n, 1) {
while (top && pre[stk[top]] < pre[i]) top --;
prv[i] = top ? stk[top] - 1 : n, stk[++ top] = i;
}
top = 0;
per(i, n, 1) {
while (top && suf[stk[top]] > suf[i]) top --;
suc[i] = top ? stk[top] - 1 : n, stk[++ top] = i;
}
int j = n;
per(i, n, 1) {
// cout << prv[i] << " " << suc[i] << " " << pre[i] << " " << suf[i] << endl;
modify(1, 1, n, i, prv[i], pre[i], 0),
modify(1, 1, n, i, suc[i], suf[i], 1);
tmp[a[i]] ++;
while (tmp[a[i]] > 1) tmp[a[j]] --, j --;
Info info = query(1, 1, n, i, j);
(ans += 1ll * i * info.s[1] - Su(i, j) * i - info.s[3] + info.s[2]) %= mod;
}
cout << ans << endl;
return 0;
}
闲话，究竟是写线性对数好看还是写 \(O(n \log n)\) 好看？？
标签：int,top,ret,stk,lst,CF1083D,mod From： https://www.cnblogs.com/Custlo/p/17813798.html