洛谷P3246 [HNOI2016]序列(离线 差分 树状数组)

时间：2023-03-09 07:07:40
洛谷P3246 [HNOI2016]序列(离线 差分 树状数组)

题意

题目链接

Sol

好像搞出了一个和题解不一样的做法(然而我考场上没写出来还是爆零0)

一个很显然的思路是考虑每个最小值的贡献。

预处理出每个数左边第一个比他小的数，右边第一个比他大的数。

那么\([L_i + 1, i]\)对\([i, R_i]\)中的每个数都会有\(a[i]\)的贡献。

我们可以抽象成一个二维平面内的矩形加。

询问就是询问最下角为\((l, l)\)，右上角为\((r, r)\)的矩形内的权值

也就是我们需要解决这么一个问题：两个操作, 矩形加矩形求和，而且前者都在后者的前面执行

我们可以把所有矩形加操作全都向右上角差分，所有询问操作全都向左下角差分。这样我们就只需要考虑每个\((i, j)\)左下角的所有修改\((x, y)\)的影响，这部分的权值为\((i - x + 1) * (j - y + 1) * w\)

直接拆开，发现可以用树状数组维护(单点修改，查前缀和)。然后就做完了

复杂度\(O(nlogn)\)

/*

*/

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)

char buf[(1 << 22)], *p1 = buf, *p2 = buf;

char obuf[1<<24], *O = obuf;

void print(int x) {if(x > 9) print(x / 10); *O++ = x % 10 + '0';}

#define OS  *O++ = '\n';

#define fout fwrite(obuf, O-obuf, 1 , stdout);

using namespace std;

const int MAXN = 1e5 + 10, INF = 1e9 + 10;

template<typename A, typename B> inline bool chmax(A &x, B y) {return x < y ? x = y, 1 : 0;}

template<typename A, typename B> inline bool chmin(A &x, B y) {return x > y ? x = y, 1 : 0;}

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, M, Q, a[MAXN],  st[MAXN], L[MAXN], R[MAXN];

LL ans[MAXN];

struct Modify {

	int h;LL v;

};

vector<Modify> tag[MAXN];

struct Query {

	int h, id, opt;

};

vector<Query> q[MAXN];

void Add(int x1, int y1, int x2, int y2, int v) {

	tag[x1].push_back({y1, v});

	tag[x2 + 1].push_back({y1, -v});

	tag[x1].push_back({y2 + 1, -v});

	tag[x2 + 1].push_back({y2 + 1, v});

}

void Query(int x1, int y1, int x2, int y2, int id) {

	q[x2].push_back({y2, id, 1});

	q[x1 - 1].push_back({y2, id, -1});

	q[x2].push_back({y1 - 1, id, -1});

	q[x1 - 1].push_back({y1 - 1, id, 1});

}

#define lb(x) (x & (-x))

LL s1[MAXN], s2[MAXN], s3[MAXN], s4[MAXN];

void TreeAdd(int x, LL v1, LL v2, LL v3, LL v4) {

	while(x <= M)

		s1[x] += v1, s2[x] += v2, s3[x] += v3, s4[x] += v4, x += lb(x);

}

pair<pair<LL, LL>, pair<LL, LL> > TreeQuery(int x) {

	pair<pair<LL, LL>, pair<LL, LL> > ans;

	while(x)

		ans.fi.fi += s1[x], ans.fi.se += s2[x], ans.se.fi += s3[x], ans.se.se += s4[x], x -= lb(x);

	return ans;

}

#undef lb

void solve() {

	for(int i = 1; i <= M; i++) {

		for(auto y: tag[i]) {

			int v = y.v;

			TreeAdd(y.h, 1ll * v, 1ll * (y.h - 1) * v, 1ll * (i - 1) * v, 1ll * (y.h - 1) * (i - 1) * v);

		}

		for(auto x : q[i]) {

			LL sumv = 0, sumyv = 0, sumxv = 0, sumxyv = 0;

			pair<pair<LL, LL>, pair<LL, LL> > tmp = TreeQuery(x.h);

			sumv = tmp.fi.fi;

			sumyv = tmp.fi.se;

			sumxv = tmp.se.fi;

			sumxyv = tmp.se.se;

			int j = x.h;

			ans[x.id] += 1ll * x.opt * (1ll * i * j * sumv - 1ll * i * sumyv - 1ll * j * sumxv + sumxyv);

		}

	}

}

void Pre() {

	a[0] = -INF; a[N + 1] = -INF; int top = 0;

	for(int i = 1; i <= N + 1; i++) {

		while(top && a[i] < a[st[top]]) R[st[top--]] = i;

		L[i] = st[top];

		st[++top] = i;

	}

	for(int i = 1; i <= N; i++)

		if((i <= R[i] - 1) && (L[i] + 1 <= i))

			Add(i, L[i] + 1, R[i] - 1, i, a[i]);

}

signed main() {

	//freopen("a.in", "r", stdin); freopen("b.out", "w", stdout);

	N = read(); M = N + 1; Q = read();

	for(int i = 1; i <= N; i++) a[i] = read();

	Pre();

	for(int i = 1; i <= Q; i++) {

		int l = read(), r = read(), ans = 0;

		Query(l, l, r, r, i);

	}

	solve();

	for(int i = 1; i <= Q; i++) cout << ans[i] << '\n';

	return 0;

}

相关文章