一个1到n的排列a. 每个点对(l, r) (l<r) 有代价. 定义空集的 max = -inf. 如果 max{ a[k] | l<k<r } ≤ min{ a[l], a[r] }, 代价为p1; 如果 min{ a[l], a[r] } < max{ a[k] | l < k < r } < max{ a[l], a[r] }, 代价为p2. m个询问, 求某区间内所有点对(l,r) (l<r) 的代价之和. (1≤n,m≤2*10^5, 1≤p1,p2≤10^4) 去年省选考过几乎一样的题: [bzoj 4540] [Hnoi2016]序列. 求某区间所有子区间的最小值之和.
以前写的题解, 现在感觉没有点重要害......数形结合啊......
那道题的一个做法是离线线段树, 本题也可以效仿.
把一个点对(l,r)看成平面上的一个点, 则查询的是一个矩形内的点权之和.
考虑以a[i]为最大值的所有开区间(L,R) (即点对). 用单调栈求出i的左边, 右边离i最近且大于a[i]的第一个位置l[i], r[i], 则L∈[L,i), R∈(i,R]即为所求.
当L∈(l[i],i), R∈(i,r[i]), 由于a[i]>a[L], a[i]>a[R], a[i]对这些点对的代价没有贡献.
当L=l[i], R∈(i,r[i]), a[R]<a[i]<a[L], a[i]对这些点对贡献p2.
当L∈(l[i],i), R=r[i], a[L]<a[i]<a[R], a[i]对这些点对贡献p2.
当L=l[i], R=r[i], a[i]<a[L], a[i]<a[R], a[i]对这个点对贡献p1.
这些(L,R)或是平面上的一点, 或是平面上的线段. 按R升序将它们加入线段树或从线段树中删除, 维护历史版本和. 对于每个询问, 查询两个前缀和, 作差即得答案.
如果强制在线, 可以用可持久化线段树代替普通线段树.
一开始用vector, 结果RE了 (bad alloc). 换成了手写的链表. 然后变成了WA. 线段树查询时将两个子区间的答案加起来, 临时变量没开成long long.
让我表达一下对一位神犇的无限景仰 QAQ
#define ALL 1, 1, n
using namespace std;
const int N = 2e5;
typedef long long ll;
struct Event {
int l, r, d, nxt;
} E[N*6 + 1];
struct Query {
int l, r, d, k, nxt;
} Q[N*2 + 1];
int e[N+2], q[N+1], e_ptr = 1, q_ptr = 1;
template<typename T>
inline void add(T pool[], int head[], int i, int& ptr, const T& v)
{
pool[ptr] = v;
pool[ptr].nxt = head[i];
head[i] = ptr++;
}
ll ans[N];
struct Fun {
ll a, b, c;
Fun(ll a=0, ll b=0, ll c=0): a(a), b(b), c(c) {}
Fun operator*(const Fun& o) const
{
return Fun(a + o.a, b + o.b, b*o.a + c + o.c);
}
void operator()(ll& s, ll& ss, int len) const
{
ss += a*s + c*len;
s += b*len;
}
};
struct Seg {
ll s[N*4], ss[N*4];
bool b[N*4];
Fun f[N*4];
void down(int o, int len, const Fun& g)
{
b[o] = true;
g(s[o], ss[o], len);
f[o] = f[o] * g;
}
void down(int o, int l, int m, int r)
{
if (!b[o]) return;
down(o*2, m-l+1, f[o]);
down(o*2+1, r-m, f[o]);
f[o] = Fun();
b[o] = false;
}
void up(int o)
{
s[o] = s[o*2] + s[o*2+1];
ss[o] = ss[o*2] + ss[o*2+1];
}
void modify(const Fun& g, int L, int R, int o, int l, int r)
{
if (L <= l && r <= R) return down(o, r-l+1, g), void();
int m = (l+r)/2;
down(o, l, m, r);
if (L <= m) modify(g, L, R, o*2, l, m);
if (R > m) modify(g, L, R, o*2+1, m+1, r);
up(o);
}
ll query(int L, int R, int o, int l, int r)
{
if (L <= l && r <= R) return ss[o];
int m = (l+r)/2;
ll a = 0;
down(o, l, m, r);
if (L <= m) a = query(L, R, o*2, l, m);
if (R > m) a += query(L, R, o*2+1, m+1, r);
return a;
}
} T;
int a[N+1], l[N+1], r[N+1];
stack<int> S;
int main()
{
int n, m, p1, p2;
scanf("%d%d%d%d", &n, &m, &p1, &p2);
rep (i, 1, n+1) scanf("%d", a+i);
rep (i, 1, n+1) {
int t;
while (!S.empty() && a[t = S.top()] < a[i]) {
r[t] = i;
S.pop();
}
S.push(i);
}
while (!S.empty()) {
r[S.top()] = n+1;
S.pop();
}
per (i, n, 1) {
int t;
while (!S.empty() && a[t = S.top()] < a[i]) {
l[t] = i;
S.pop();
}
S.push(i);
}
rep (i, 1, n+1) {
if (l[i] && r[i] <= n) {
add(E, e, r[i], e_ptr, (Event){l[i], l[i], p1});
add(E, e, r[i]+1, e_ptr, (Event){l[i], l[i], -p1});
}
if (l[i] && i < r[i]-1) {
add(E, e, i+1, e_ptr, (Event){l[i], l[i], p2});
add(E, e, r[i], e_ptr, (Event){l[i], l[i], -p2});
}
if (i > l[i]+1) {
add(E, e, r[i], e_ptr, (Event){l[i]+1, i-1, p2});
add(E, e, r[i]+1, e_ptr, (Event){l[i]+1, i-1, -p2});
}
}
rep (i, 0, m) {
int L, R;
scanf("%d%d", &L, &R);
add(Q, q, L-1, q_ptr, (Query){L, R, -1, i});
add(Q, q, R, q_ptr, (Query){L, R, 1, i});
ans[i] = p1 * (R-L);
}
rep (i, 1, n+1) {
for (int j = e[i]; j; j = E[j].nxt) {
const Event& t = E[j];
T.modify(Fun(0, t.d, 0), t.l, t.r, ALL);
}
T.modify(Fun(1, 0, 0), 1, n, ALL);
for (int j = q[i]; j; j = Q[j].nxt) {
const Query& t = Q[j];
ans[t.k] += t.d * T.query(t.l, t.r, ALL);
}
}
rep (i, 0, m)
printf("%lld\n", ans[i]);
return 0;
}