9.21校内T2
EternalEpic · · 个人记录
链接：https://www.qizhishu.com/upload/file/20200919/20200919100811_96172.pdf
维护两个单调栈和线段树，可以发现直接算贡献会超时，考虑在
// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>
#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")
using namespace std;
namespace Base {
inline char gc(void)
{
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
#define gc() getchar()
template <class T> inline void read(T &x)
{
T flag = (T) 1; x = 0; static char ch = gc();
for (; ch > '9' || ch < '0'; ch = gc())
flag = ch == '-' ? -1 : 1;
for (; ch >= '0' && ch <= '9'; ch = gc())
x = (x << 1) + (x << 3) + (ch & 15);
x *= flag; return;
}
inline void readstr(string&x) {
x = ""; static char ch;
while (isspace(ch = gc()));
while (x += ch, !isspace(ch = gc()));
}
inline void readstr(char *s) {
do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
*s = 0; return;
}
inline void printstr(string x, int num = 0, char ch = '\n') {
for (int i = num; i < x.size(); ++i)
putchar(x[i]); putchar(ch);
}
inline void readch(char&x) { while (isspace(x = gc())); }
char pf[100000], *o1 = pf, *o2 = pf + 100000;
#define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
template <class T>
inline void println(T x, char c = '\n') {
if (x < 0) ot(45), x = -x;
static char s[15], *b; b = s;
if (!x) *b ++= 48;
for (; x; * b ++= x % 10 + 48, x /= 10);
for (; b-- != s; ot(*b)); ot(c);
}
template <class T> inline void write(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0'); return;
}
template <class T> inline void writeln(T x) { write(x); puts(""); }
template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }
template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
template <class T> inline T max(const T&x, const T&y, const T&z) {
return x > y ? (x > z ? x : z) : (y > z ? y : z);
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define Ms(arr, opt) memset(arr, opt, sizeof(arr))
#define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
#define Mp(x, y) make_pair(x, y)
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
struct Vector {
double x, y;
Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}
inline Vector Vary(void) { return Vector(x, -y); }
inline bool operator < (const Vector&rhs)
const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
inline Vector operator - (const Vector&rhs)
const { return Vector(x - rhs.x, y - rhs.y); }
inline Vector operator + (const Vector&rhs)
const { return Vector(x + rhs.x, y + rhs.y); }
inline Vector operator * (const double&rhs)
const { return Vector(x * rhs, y * rhs); }
inline Vector operator / (const double&rhs)
const { return Vector(x / rhs, y / rhs); }
inline Vector operator * (const Vector&rhs)
const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
}; typedef Vector Complex;
}
using namespace Base;
const int mod = 1e9 + 7, Maxn = 5e5 + 5;
inline void inc(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline void dec(int &x, int y) { x = x - y < 0 ? x - y + mod : x - y; }
int n, a[Maxn], sta1[Maxn], sta2[Maxn], cnta, cntb;
struct SegmentTree {
int t[Maxn << 2], tag[Maxn << 2]; SegmentTree(void) { Ms(tag, -1); }
inline void pushup(int pos) { t[pos] = (t[pos << 1] + t[pos << 1 | 1]) % mod; }
inline void addtag(int pos, int l, int r, int val) { t[pos] = 1ll * (r - l + 1) * val % mod; tag[pos] = val; }
inline void pushdown(int pos, int l, int r) {
if (tag[pos] != -1) {
int mid = l + r >> 1;
addtag(pos << 1, l, mid, tag[pos]),
addtag(pos << 1 | 1, mid + 1, r, tag[pos]);
tag[pos] = -1;
}
}
inline void build(int pos, int l, int r) {
if (l == r) { t[pos] = a[l]; return; }
int mid = l + r >> 1;
build(pos << 1, l, mid),
build(pos << 1 | 1, mid + 1, r);
pushup(pos);
}
inline void modify(int pos, int l, int r, int L, int R, int val) {
if (L <= l && R >= r) return addtag(pos, l, r, val);
int mid = l + r >> 1; pushdown(pos, l, r);
if (L <= mid) modify(pos << 1, l, mid, L, R, val);
if (R > mid) modify(pos << 1 | 1, mid + 1, r, L, R, val);
pushup(pos);
}
inline int query(int pos, int l, int r, int L, int R) {
if (L <= l && R >= r) return t[pos];
int mid = l + r >> 1, ret = 0; pushdown(pos, l, r);
if (L <= mid) ret = query(pos << 1, l, mid, L, R);
if (R > mid) inc(ret, query(pos << 1 | 1, mid + 1, r, L, R));
return ret;
}
inline void modify(int l, int r, int val) { if (l > r) return; modify(1, 1, n, l, r, val); }
inline int query(int l, int r) { if (l > r) return 0; return query(1, 1, n, l, r); }
} Tmx, Tmn;
signed main(void) {
// file("");
read(n); int ans = 0, ret = 0;
for (int i = 1; i <= n; i++) read(a[i]);
Tmx.build(1, 1, n), Tmn.build(1, 1, n);
for (int i = 1; i <= n; i++) {
inc(ret, 1ll * a[i] * a[i] % mod);
while (cnta && a[i] > a[sta1[cnta]]) {
inc(ret, 1ll * Tmn.query(sta1[cnta - 1] + 1, sta1[cnta]) * (a[i] - a[sta1[cnta]]) % mod);
Tmx.modify(sta1[cnta - 1] + 1, sta1[cnta], a[i]); --cnta;
} sta1[++cnta] = i;
while (cntb && a[i] < a[sta2[cntb]]) {
inc(ret, 1ll * Tmx.query(sta2[cntb - 1] + 1, sta2[cntb]) * (a[i] - a[sta2[cntb]]) % mod);
Tmn.modify(sta2[cntb - 1] + 1, sta2[cntb], a[i]); --cntb;
ret = ret < 0 ? ret + mod : ret;
} sta2[++cntb] = i;
inc(ans, ret);
} writeln(ans);
// fwrite(pf, 1, o1 - pf, stdout);
return 0;
}
/**/