[TIOJ] 2039. AI-666 賺多少

題目連結:https://tioj.infor.org/problems/2039
注意!以下是努力壓常數後過的$O(N \log N)$作法(雖然好像大家也都是$O(N \log C)$的aliens優化解)。
這裡講一下我的作法好了,首先我們將題目視成不斷將k變大並詢問當前最大是多少。若是只有一個k的時候,我們顯然是要找一組左低右高的區間$[a_l, a_r]$,那變成兩個的時候,我們發現其實有幾種可能,一種是在$l$左邊繼續找一組左低右高的區間,或是在$r$右邊找一組左低右高的區間,或是在$(l, r)$中找一組左高右低的區間,把他們的差加進答案即可。
所以我們可以用線段樹維護我們想知道某個區間內左高右低或左低右高的最大值,這樣我們就是每次從heap拿出一個最大的區間加進答案後,把它左右中三個區間同時再塞到heap裡,繼續做到直到沒有東東可以拿,或達到k就好。
不過一般的線段樹實作會TLE,所以我寫了個zkw再加上輸入優化後就可以AC了XD
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int,int>;
#define FF first
#define SS second
const int N = 2000000;

struct Data{
	int v, p1, p2;
	Data():v(0),p1(-1),p2(-1){}
	Data(int a, int b, int c):v(a),p1(b),p2(c){}
	bool operator<(const Data& a) const {
		return v < a.v;
	}
	bool operator>(const Data& a) const {
		return v > a.v;
	}
} LR[N<<2], RL[N<<2];
PII mx[N<<2], mi[N<<2];
int m;
// zkw
inline Data queryLR(int l, int r){
	// (l, r)
	int b=-1,c=-1; Data ret;
	for(l+=m,r+=m;l^r^1;l>>=1,r>>=1){
		if(~l&1) {
			ret = max(ret, LR[l^1]);
			if(b != -1)
				ret = max(ret, Data(mx[l^1].FF-mi[b].FF, mi[b].SS, mx[l^1].SS));
			b = (b==-1 or mi[l^1]<mi[b])?(l^1):b;
		}
		if( r&1) {
			ret = max(ret, LR[r^1]);
			if(c != -1)
				ret = max(ret, Data(mx[c].FF-mi[r^1].FF, mi[r^1].SS, mx[c].SS));
			c = (c == -1 or mx[r^1]>mx[c])?(r^1):c;
		}
		if(b != -1 and c != -1)
			ret = max(ret, Data(mx[c].FF-mi[b].FF, mi[b].SS, mx[c].SS));
	}
	return ret;
}
inline Data queryRL(int l, int r){
	// (l, r)
	int a=-1,d=-1; Data ret;
	for(l+=m,r+=m;l^r^1;l>>=1,r>>=1){
		if(~l&1) {
			ret = max(ret, RL[l^1]);
			if(a != -1)
				ret = max(ret, Data(mx[a].FF-mi[l^1].FF, mx[a].SS, mi[l^1].SS));
			a = (a==-1 or mx[l^1]>mx[a])?(l^1):a;
		}
		if( r&1) {
			ret = max(ret, RL[r^1]);
			if(d != -1)
				ret = max(ret, Data(mx[r^1].FF-mi[d].FF, mx[r^1].SS, mi[d].SS));
			d = (d == -1 or mi[r^1]<mi[d])?(r^1):d;
		}
		if(a != -1 and d != -1)
			ret = max(ret, Data(mx[a].FF-mi[d].FF, mx[a].SS, mi[d].SS));
	}
	return ret;
}

struct Seg{
	int v, l, r, ll, rr;
	Seg():v(0),l(-1),r(-1),ll(-1),rr(-1){}
	Seg(Data a, int b, int c):v(a.v),l(a.p1),r(a.p2),ll(b),rr(c){}
	Seg(int a, int b, int c, int d, int e):v(a),l(b),r(c),ll(d),rr(e){}
	bool operator<(const Seg& a) const {
		return v < a.v;
	}
	bool operator>(const Seg& a) const {
		return v > a.v;
	}
};

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k; cin>>n>>k;
	for(m=1;m<n;m<<=1);
	for(int i=m+1;i<=m+n;i++){
		cin>>mx[i].FF;
		mx[i].SS = i-m;
		mi[i] = mx[i];
	}
	for(int i=m-1;i;i--){
		LR[i] = max(LR[i<<1], LR[i<<1|1]);
		LR[i] = max(LR[i], Data(mx[i<<1|1].FF-mi[i<<1].FF, mi[i<<1].SS, mx[i<<1|1].SS));
		RL[i] = max(RL[i<<1], RL[i<<1|1]);
		RL[i] = max(RL[i], Data(mx[i<<1].FF-mi[i<<1|1].FF, mx[i<<1].SS, mi[i<<1|1].SS));
		mx[i] = max(mx[i<<1], mx[i<<1|1]);
		mi[i] = min(mi[i<<1], mi[i<<1|1]);
	}
	int ans = 0, tot = 0;
	priority_queue<Seg> pq;
	auto x = queryLR(0, n+1);
	if(x.p1 != -1 and x.p2 != -1)
		pq.push(Seg(queryLR(0, n+1), 0, n+1));
	while(!pq.empty() and tot<k) {
		auto cur = pq.top(); pq.pop();
		ans += cur.v; tot += 1;
		if(mx[cur.l+m] < mx[cur.r+m]) {
			// LR
			if(cur.l-cur.ll>2){
				auto x = queryLR(cur.ll, cur.l);
				if(x.p1 != -1 and x.p2 != -1)
					pq.push(Seg(x, cur.ll, cur.l));
			}
			if(cur.rr-cur.r>2){
				auto x = queryLR(cur.r, cur.rr);
				if(x.p1 != -1 and x.p2 != -1)
					pq.push(Seg(x, cur.r, cur.rr));
			}
			if(cur.r-cur.l >2){
				auto x = queryRL(cur.l, cur.r);
				if(x.p1 != -1 and x.p2 != -1)
					pq.push(Seg(x, cur.l, cur.r));
			}
		} else {
			// RL
			if(cur.l-cur.ll>2){
				auto x = queryRL(cur.ll, cur.l);
				if(x.p1 != -1 and x.p2 != -1)
					pq.push(Seg(x, cur.ll, cur.l));
			}
			if(cur.rr-cur.r>2){
				auto x = queryRL(cur.r, cur.rr);
				if(x.p1 != -1 and x.p2 != -1)
					pq.push(Seg(x, cur.r, cur.rr));
			}
			if(cur.r-cur.l >2){
				auto x = queryLR(cur.l, cur.r);
				if(x.p1 != -1 and x.p2 != -1)
					pq.push(Seg(x, cur.l, cur.r));
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology