Wannafly挑战赛18 E 极差（线段树、单调栈）

Wannafly挑战赛18 E 极差

题意

给出三个长度为n的正整数序列，一个区间[L,R]的价值定义为：三个序列中，这个区间的极差（最大值与最小值之差）的乘积。

求所有区间的价值之和。答案对\(2^{32}\)取模。

题解

如果只有一个区间，我们可以枚举区间右端点，当右端点向右移动，左端点在[x, r]的一些区间的值会发生改变，可以用单调栈和线段树维护。

至于三个区间，可以用八棵线段树维护选中的某几个区间想乘的值。

代码

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define rep(i, a, b) for(int i=(a); i<(b); i++)

#define sz(a) (int)a.size()

#define efi(a) a[sz(a)-1]

#define ese(a) a[sz(a)-2]

#define de(a) cout << #a << " = " << a << endl

#define dd(a) cout << #a << " = " << a << " "

#define all(a) a.begin(), a.end()

#define endl "\n"

typedef long long ll;

typedef unsigned int uint;

typedef pair<int, int> pii;

typedef vector<int> vi;

//---

const int N = 101010;

const ll P = 1ll<<32;

int n;

uint a[3][N];

struct Seg {

#define ls (rt<<1)

#define rs (ls|1)

	static const int N = ::N<<2;

	uint sum[8][N], la[3][N];

	void build(int l, int r, int rt) {

		sum[0][rt] = r-l+1;

		if(l==r) return ;

		int mid = l+r>>1;

		build(l, mid, ls);

		build(mid+1, r, rs);

	}

	inline void gao(int x, uint c, int rt) {

		int p = 1<<x;

		rep(i, 1, 8) if((i&p)==p) {

			sum[i][rt] += sum[i^p][rt] * c;

		}

		la[x][rt] += c;

	}

	inline void down(int rt) {

		rep(x, 0, 3) if(la[x][rt]) {

			gao(x, la[x][rt], ls);

			gao(x, la[x][rt], rs);

			la[x][rt] = 0;

		}

	}

	inline void up(int rt) {

		rep(i, 1, 8) sum[i][rt] = sum[i][ls] + sum[i][rs];

	}

	void upd(int L, int R, int p, uint c, int l, int r, int rt) {

		if(L<=l&&r<=R) {

			gao(p, c, rt);

			return ;

		}

		int mid = l+r>>1;

		down(rt);

		if(L<=mid) upd(L, R, p, c, l, mid, ls);

		if(R>=mid+1) upd(L, R, p, c, mid+1, r, rs);

		up(rt);

	}

	uint qry(int L, int R, int l, int r, int rt) {

		if(L<=l&&r<=R) return sum[7][rt];

		int mid = l+r>>1;

		down(rt);

		uint ans = 0;

		if(L<=mid) ans += qry(L, R, l, mid, ls);

		if(R>=mid+1) ans += qry(L, R, mid+1, r, rs);

		up(rt);

		return ans;

	}

}seg;

int pma[3], pmi[3];

int ma[3][N], mi[3][N];

int main() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	///

	cin >> n;

	///read

	rep(i, 0, 3) rep(j, 1, n+1) cin >> a[i][j];

	///solve

	seg.build(1, n, 1);

	uint ans = 0;

	rep(j, 1, n+1) {

		rep(i, 0, 3) {

			while(pmi[i] && a[i][mi[i][pmi[i]]] > a[i][j]) {

				seg.upd(mi[i][pmi[i]-1]+1, mi[i][pmi[i]], i, a[i][mi[i][pmi[i]]], 1, n, 1);

				--pmi[i];

			}

			mi[i][++pmi[i]] = j;

			seg.upd(mi[i][pmi[i]-1]+1, j, i, -a[i][j], 1, n, 1);

			while(pma[i] && a[i][ma[i][pma[i]]] < a[i][j]) {

				seg.upd(ma[i][pma[i]-1]+1, ma[i][pma[i]], i, -a[i][ma[i][pma[i]]], 1, n, 1);

				--pma[i];

			}

			ma[i][++pma[i]] = j;

			seg.upd(ma[i][pma[i]-1]+1, j, i, a[i][j], 1, n, 1);

		}

		ans += seg.sum[7][1];

	}

	cout << ans << endl;

	return 0;

}