4826: [Hnoi2017]影魔

题意：一个排列，点对\((i,j)\)，\(p=max(i+1,j-1)\)，若\(p<a_i,a_j\)贡献p1，若\(p\)在\(a_1,a_2\)之间贡献p2. 多组询问一个区间的贡献和。

感觉和去年的题挺像的...然后\(O(n\sqrt{n}logn)\)莫队被卡成暴力...那个log还是主席树log... 并且调试时间比正解还长，不能更弱了

一个点对只有唯一的最大值\(p\)

可以按照\(p\)来分类统计

单调栈预处理\(l_i, r_i\)第一个大于的位置

\((li,\ ri)\)这个点对贡献p1

\((l_i,\ i+1...r_i-1)\)贡献p2

\((l_i+1...i-1,\ r_i)\)也贡献p2

就是一个“单点加，线段加，矩形求和”的问题

可以分别对横坐标和纵坐标建两棵主席树，用区间加实现线段加

使用标记永久化比较简单

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = 2e5+5;

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, Q, p1, p2, a[N], st[N], l[N], r[N];

struct lis {

	struct meow{int l, r, val, ne;} e[N<<1];

	int cnt, h[N];

	inline void ins(int u, int l, int r, int v) {

		e[++cnt] = (meow){l, r, v, h[u]}; h[u] = cnt;

	}

} l1, l2;

#define rg(l, r, ql, qr) ( (r<qr ? r : qr) - (l>ql ? l : ql) + 1 )

struct ct {

	struct meow{int l, r; ll add, sum;} t[N*40];

	int sz, root[N];

	void add(int &x, int l, int r, int ql, int qr, ll v) {

		t[++sz] = t[x]; x = sz;

		if(ql<=l && r<=qr) t[x].add += v, t[x].sum += (r-l+1) * v;

		else {

			t[x].sum += rg(l, r, ql, qr) * v;

			int mid = (l+r)>>1;

			if(ql <= mid) add(t[x].l, l, mid, ql, qr, v);

			if(mid < qr)  add(t[x].r, mid+1, r, ql, qr, v);

		}

	}

	ll que(int x, int y, int l, int r, int ql, int qr) {

		if(ql<=l && r<=qr) return t[y].sum - t[x].sum;

		else {

			ll ans = rg(l, r, ql, qr) * (t[y].add - t[x].add);

			int mid = (l+r)>>1;

			if(ql <= mid) ans += que(t[x].l, t[y].l, l, mid, ql, qr);

			if(mid < qr)  ans += que(t[x].r, t[y].r, mid+1, r, ql, qr);

			return ans;

		}

	}

	ll que(int l, int r) {

		return que(root[l-1], root[r], 1, n, l, r);

	}

	void build(lis &li) {

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

			root[i] = root[i-1];

			for(int p = li.h[i]; p; p = li.e[p].ne) {

				int l = li.e[p].l, r = li.e[p].r, v = li.e[p].val;

				add(root[i], 1, n, l, r, v);

			}

		}

	}

} t1, t2;

void init() {

	int top = 0;

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

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

		l[i] = st[top];

		st[++top] = i;

	}

	while(top) r[st[top]] = n+1, top--;

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

		if(l[i] > 0 && r[i] <= n) l1.ins(l[i], r[i], r[i], p1);

		if(i+1 <= r[i]-1) l1.ins(l[i], i+1, r[i]-1, p2);

		if(l[i]+1 <= i-1) l2.ins(r[i], l[i]+1, i-1, p2);

	}

	t1.build(l1); t2.build(l2);

}

int main() {

	freopen("in", "r", stdin);

	n=read(); Q=read(); p1=read(); p2=read();

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

	init();

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

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

		ll ans = t1.que(l, r) + t2.que(l, r) + (ll) (r-l) * p1;

		printf("%lld\n", ans);

	}

}

下面是莫队

# pragma GCC optimize ("O2")

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = 2e5+5;

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, p1, p2, a[N], block, l[N], r[N], pos[N];

struct ct {

	struct meow{int l, r, sum;} t[N*40];

	int sz, root[N];

	void insert(int &x, int l, int r, int p) {

		t[++sz] = t[x]; x = sz;

		t[x].sum++;

		if(l == r) return;

		int mid = (l+r)>>1;

		if(p <= mid) insert(t[x].l, l, mid, p);

		else insert(t[x].r, mid+1, r, p);

	}

	void build(int *a) {

		for(int i=1; i<=n; i++) root[i] = root[i-1], insert(root[i], 1, n, a[i]);

	}

	int quer(int x, int y, int l, int r, int ql, int qr) {

		if(ql<=l && r<=qr) return t[y].sum - t[x].sum;

		else {

			int mid = (l+r)>>1, ans=0;

			if(ql <= mid) ans += quer(t[x].l, t[y].l, l, mid, ql, qr);

			if(mid < qr)  ans += quer(t[x].r, t[y].r, mid+1, r, ql, qr);

			return ans;

		}

	}

	int quer(int l, int r, int ql, int qr) {

		if(l > r || ql > qr) return 0;

		if(r < 1 || l > n) return 0;

		if(l < 1) l = 1; if(r > n) r = n;

		//printf("quer [%d, %d]   [%d, %d]\n", l, r, ql, qr);

		return quer(root[l-1], root[r], 1, n, ql, qr);

	}

} tl, tr;

int st[N], top;

void init() {

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

		while(top && a[ st[top] ] < a[i]) r[ st[top] ] = i-1, top--;

		l[i] = st[top] + 1;

		st[++top] = i;

	}

	while(top) r[ st[top--] ] = n;

	tl.build(l); tr.build(r);

	//for(int i=1; i<=n; i++) printf("%d  [%d, %d]\n", i, l[i], r[i]);

}

struct meow {

	int l, r, id;

	bool operator <(const meow &a) const {return pos[l] == pos[a.l] ? r < a.r : pos[l] < pos[a.l];}

} q[N];

ll now, ans[N];

int ql, qr;

inline void addr(int x) { //printf("\naddr %d\n", x);

	int L = max(ql, l[x]-1);

	now += tr.quer(L, qr, qr, n) * p1; //printf("__p1 %d\n", a);

	now += tr.quer(L, qr, 1, qr-1) * p2;

	now += tr.quer(ql, l[x]-2, qr, n) * p2; //printf("__p2 %d\n", b);

	//printf("now %d\n", now);

}

inline void delr(int x) {

	int L = max(ql, l[x]-1);

	now -= tr.quer(L, qr, qr, n) * p1;

	now -= tr.quer(L, qr, 1, qr-1) * p2;

	now -= tr.quer(ql, l[x]-2, qr, n) * p2;

}

inline void addl(int x) {

	int R = min(r[x]+1, qr);

	now += tl.quer(ql, R, 1, ql) * p1;

	now += tl.quer(ql, R, ql+1, n) * p2;

	now += tl.quer(r[x]+2, qr, 1, ql) * p2;

}

inline void dell(int x) { //printf("\n---dell %d\n", x);

	int R = min(r[x]+1, qr);

	now -= tl.quer(ql, R, 1, ql) * p1; //printf("__a %d\n", a);

	now -= tl.quer(ql, R, ql+1, n) * p2; //printf("__b %d\n", b);

	now -= tl.quer(r[x]+2, qr, 1, ql) * p2; //printf("__c %d\n", c);

}

void modui() {

	ql=1; qr=0;

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

		while(qr < q[i].r) addr(qr+1), qr++;

		while(qr > q[i].r) qr--, delr(qr+1);

		while(ql < q[i].l) ql++, dell(ql-1);

		while(ql > q[i].l) addl(ql-1), ql--;

		ans[ q[i].id ] = now;

	}

}

int main() {

	freopen("in", "r", stdin);

	n=read(); m=read(); p1=read(); p2=read();

	block = sqrt(n);

	for(int i=1; i<=n; i++) a[i]=read(), pos[i] = (i-1)/block+1;

	for(int i=1; i<=m; i++) q[i].l = read(), q[i].r = read(), q[i].id = i;

	sort(q+1, q+1+m);

	init();

	modui();

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

}

巴特西

bzoj 4826: [Hnoi2017]影魔 [主席树单调栈]

4826: [Hnoi2017]影魔

最新文章

热门文章

巴特西

bzoj 4826: [Hnoi2017]影魔 [主席树 单调栈]

4826: [Hnoi2017]影魔

最新文章

热门文章

bzoj 4826: [Hnoi2017]影魔 [主席树单调栈]