[jzoj5073 GDOI2017第二轮模拟] 影魔

Description

影魔，奈文摩尔，据说有着一个诗人的灵魂。事实上，他吞噬的诗人灵魂早已成千上万。千百年来，他收集了各式各样的灵魂，包括诗人、牧师、帝王、乞丐、奴隶、罪人，当然，还有英雄。
每一个灵魂，都有着自己的战斗力，而影魔，靠这些战斗力提升自己的攻击。
奈文摩尔有n个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号1到n。第i个灵魂的战斗力为k[i]，灵魂们以点对的形式为影魔提供攻击力，对于灵魂对i，j(i<j)来说，若不存在k[s](i<s<j)大于k[i]或者k[j]，则会为影魔提供p1的攻击力（可理解为：当j=i+1时，因为不存在满足i<s<j的s，从而k[s]不存在，这时提供p1的攻击力；当j>i+1时，若max{k[s]|i<s<j}<=min{k[i],k[j]}，则提供p1的攻击力）；另一种情况，令c为k[i+1],k[i+2],k[i+3]……k[j-1]的最大值，若c满足：k[i]<c<k[j],或者k[j]<c<k[i]，则会为影魔提供p2的攻击力，当这样的c不存在时，自然不会提供这p2的攻击力；其他情况的点对，均不会为影魔提供攻击力。
影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了，他想知道，对于任意一段区间[a,b]，1<=a<b<=n，位于这些区间中的灵魂对会为影魔提供多少攻击力，即考虑所有满足a<=i<j<=b的灵魂对i,j提供的攻击力之和。
顺带一提，灵魂的战斗力组成一个1到n的排列：k[1],k[2],…,k[n]。

Input

输入文件名为sf.in。
第一行n,m,p1,p2
第二行n个数：k[1],k[2],…,k[n]
接下来m行，每行两个数a,b，表示询问区间[a,b]中的灵魂对会为影魔提供多少攻击力。

Output

输出文件名为sf.out
共输出m行，每行一个答案，依次对应m个询问。

Sample Input

Sample Output

Data Constraint

30%：1<= n,m <= 500。
另30%: p1=2*p2。
100%:1 <= n,m <= 200000；1 <= p1,p2 <= 1000。

Solution

把所有询问离线

用单调栈分别做两次，求出对于排列数组的单个元素从自己开始到左边和到右边的最远的端点

为了处理贡献对应询问的区间建出一颗线段树

按左端点排序询问，枚举区间内的元素，设当前元素为最大值，那么，从它到区间端点（端点作为最大值）的这个区间的都可以打上p2贡献的标记

设当前元素为次小值，那么，对区间端点打上p1-p2-p2的标记（作为次小有两次重复）

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define _L long long

#define _RG register int

#define lson s, mid, k << 1

#define rson mid + 1, t, k << 1 | 1

const int N = 200010;

int n, m, p1, p2, a[N], l[N], r[N], steck[N], sec, nex[N], tim;

_L tag[N << 2], sum[N << 2], ans[N];

struct Q

	{

	int l, r, id;

	}que[N];

inline void downt(_RG s, _RG t, _RG k)

	{

	sum[k] += tag[k] * (_L)(t - s + 1);

	if(s ^ t) tag[k << 1] += tag[k], tag[k << 1 | 1] += tag[k];

	tag[k] = 0;

	}

void updat(_RG s, _RG t, _RG k, _RG x, _RG y, _RG z)

	{

	_RG mid = s + t >> 1;

	downt(s, t, k);

	if(s ^ t) downt(s, mid, k << 1), downt(mid + 1, t, k << 1 | 1);

	if(s == x && t == y)

		{

		tag[k] += z;

		downt(s, t, k);

		return;

		}

	if(y <= mid) updat(lson, x, y, z);

	else if(x > mid) updat(rson, x, y, z);

	else updat(lson, x, mid, z), updat(rson, mid + 1, y, z);

	sum[k] = sum[k << 1] + sum[k << 1 | 1];

	}

_L query(_RG s, _RG t, _RG k, _RG x, _RG y)

	{

	_RG mid = s + t >> 1;

	downt(s, t, k);

	if(s ^ t) downt(s, mid, k << 1), downt(mid + 1, t, k << 1 | 1);

	if(s == x && t == y) return sum[k];

	if(y <= mid) return query(lson, x, y);

	if(x > mid) return query(rson, x, y);

	return query(lson, x, mid) + query(rson, mid + 1, y);

	}

void solve()

	{

	for(_RG i = 1; i <= m; ++i) que[i] = (Q) {l[i], r[i], i};

	std::sort(que + 1, que + 1 + m, [](const Q &u, const Q &v) {return u.l > v.l;});

	steck[sec = 1] = n + 1;

	a[n + 1] = 1e9;

	for(_RG i = n; i; --i)

		{

		while(sec && a[steck[sec]] < a[i]) --sec;

		nex[i] = steck[sec];

		steck[++sec] = i;

		}

	tim = 1;

	for(_RG i = n; i; --i)

		{

		updat(1, n + 1, 1, i + 1, nex[i], p2);

		updat(1, n + 1, 1, nex[i], nex[i], p1 - p2 - p2);

		while(tim <= m && que[tim].l == i)

			{

			ans[que[tim].id] += query(1, n + 1, 1, i, que[tim].r);

			++tim;

			}

		if(tim > m) break;

		}

	}

int main()

	{

	scanf("%d%d%d%d", &n, &m, &p1, &p2);

	for(_RG i = 1; i <= n; ++i) scanf("%d", a + i);

	for(_RG i = 1; i <= m; ++i) scanf("%d%d", l + i, r + i);

	solve();

	memset(sum, 0LL, sizeof sum), memset(tag, 0LL, sizeof tag);

	for(_RG i = 1; i <= n / 2; ++i) std::swap(a[i], a[n - i + 1]);

	for(_RG i = 1; i <= m; ++i) l[i] = n - l[i] + 1, r[i] = n - r[i] + 1, std::swap(l[i], r[i]);

	solve();

	for(_RG i = 1; i <= m; ++i) printf("%lld\n", ans[i]);

	return 0;

	}

枚举当前数为次小值，则可以直接为区间加上贡献，用线段树覆盖，

巴特西