题面

题解

在网上看到有些做法，有什么平衡树、启发式合并等等总之复杂度O(Tnlog^2(n))的不优做法，这里我就用一个O(Tnlogn)的做法好了

其实大体上推导的思路都是一样的。

我们很容易发现，如果全选没水的条件，一定是一组满足条件的解。关键是我们要如何选择有水的条件。

容易发现，对于一个有水条件，它一定会使包含它的一段连续区间内高度小于它的地方都有水。而在其区间内，没有它高的有水条件，当它满足时，一定也能被满足，而没有它高的无水条件，当它满足时，一定不能被满足。

我们先考虑如何求出这一段区间。这一段区间内一定不包含比当前水位置高的墙……

之后对于这个区间，我们考虑如何维护在这个区间内灌水满足的条件……而选择这个条件可以带来的贡献，是其导致成立的有水条件减去导致不成立的无水条件。

我们求出了每个有水条件对应的区间与贡献后，可以通过dp来求出最大的满足条件值。

摘自 https://blog.csdn.net/tan_tan_tann/article/details/109788508 (有删改 )

我简单解释概括一下，

我们从结果方向考虑，最后灌完水了，肯定会是很多段连续的小水潭，彼此分隔开，而且其贡献就是每段水潭水下覆盖的“有水条件”数 + 水潭水面上方的“无水条件”数 + “岸上”的无水条件数。

而每段水潭的高度肯定恰好与某个有水条件的高度+1相等，因为若稍微高一些（不触碰到下一个有水条件）肯定不会更优，

因此，我们再从有水条件反过来想，容易发现对于每个有水条件，令其满足的“最低”水潭的覆盖区间是一定的，即上面摘录的“这一段区间内一定不包含比当前水位置高的墙”，事实上，由于水潭高度不会是整数，所以潭内的墙一定比水面低，潭两边的墙一定更高。那么我们把墙和有水条件按高度从大到小排序，把墙从高到矮往水箱中加（加进一个线段树中），同时，在大于某个有水条件高度的墙全部加进去后，把这个条件的左右区间确定了（即在线段树上查询原位置(i)左边最近的墙和右边最近的墙）。

把每个有水条件的区间确定后，我们再分别解决水面下和水面上的贡献。

水面下的贡献即为高度比水面矮、且原位置 i 在此区间内的有水条件数。类似地，我们把有水条件按高度从小到大排序，然后从头一个一个加进线段树内（原位置 i 的地方加 1），再查询此条件对应区间内的条件数量（这里可能有人会疑惑，高度相等的也要算，万一在他后面没算到怎么办？不用担心，做就是了，因为高度相等、区间重合的有水条件是等价的，在算最后一个这样等价的条件时会把所有贡献都计算进去）。

水面上的贡献即为无水条件的贡献嘛，类比一下，也这么处理就是了。

最后一步，我们设dp[i]为从左到右处理到 i 位置时最大的贡献（此dp默认没有影响到 i 后面的位置），把每个有水条件按照右端点挂到序列上，把每个位置的无水条件数处理出来，

dp[i] = max{dp[i-1] + (i 位置无水条件数) ，dp[L[j] - 1] + ans[j] (j 为 R[j] == i 的有水条件)}

总Answer = 最大的dp[i]

复杂度 O(Tnlogn)

CODE

#include<map>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define LL long long

#define ULL unsigned long long

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) ((-x) & (x))

#pragma GCC optimize(2)

LL read() {

	LL f = 1,x = 0;char s = getchar();

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

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f * x;

}

const int MOD = 1000000007;

int n,m,i,j,s,o,k;

int a[MAXN],b[MAXN];

int sm[MAXN],w[MAXN];

int dp[MAXN];

vector<int> col[MAXN];

struct qu{

	int i,j,l,r;

}ex[MAXN],no[MAXN];

inline bool cm1(qu a,qu b) {return a.j > b.j;}

int cte,ctn;

struct it{

	int id,h;

}hi[MAXN];

inline bool cmp(it a,it b) {return a.h > b.h;}

//------------------------------------------ZKW

int rr[MAXN<<2],ll[MAXN<<2],M;

void maketree(int n) {

	M=1;while(M < n+2)M <<= 1;

	for(int i=(M<<1|1);i>0;i--)rr[i]=n;

	memset(ll,0,sizeof(ll));

}

void addr(int l,int r,int ad) {

	int s = M + l - 1,t = M + r + 1;

	while(s || t) {

		if((s>>1) != (t>>1)) {

			if(!(s & 1)) rr[s^1] = min(rr[s^1],ad);

			if(t & 1) rr[t^1] = min(rr[t^1],ad);

		}else break;

		s >>= 1;t >>= 1;

	}return ;

}

void addl(int l,int r,int ad) {

	int s = M + l - 1,t = M + r + 1;

	while(s || t) {

		if((s>>1) != (t>>1)) {

			if(!(s & 1)) ll[s^1] = max(ll[s^1],ad);

			if(t & 1) ll[t^1] = max(ll[t^1],ad);

		}else break;

		s >>= 1;t >>= 1;

	}return ;

}

void query(int x,int &l,int &r) {

	int s = M + x;l = 0;r = 0x7f7f7f7f;

	while(s) {l = max(l,ll[s]);r = min(r,rr[s]);s>>=1;}

	return ;

}

//-----------------------------------ZKW_End

int c[MAXN];

void addtree(int x,int y) {while(x<=n)c[x] += y,x += lowbit(x);}

inline int sum(int x) {int as=0;while(x>0)as += c[x],x -= lowbit(x);return as;}

int main() {

//	freopen("tank.in","r",stdin);

//	freopen("tank.out","w",stdout);

	int T = read();

	while(T --) {

		n = read();m = read();

		b[0] = b[n] = 0x7f7f7f7f;

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

			b[i] = read();

			hi[i].id = i;hi[i].h = b[i];

		}

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

			sm[i] = 0; col[i].clear();

		}

		bool flag = 1;

		maketree(n);

		cte = ctn = 0;

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

			s = read();o = read();k = read();

			if(k == 1) {

				ex[++ cte].i = s;

				ex[cte].j = o;

			}

			else no[++ ctn].i = s,no[ctn].j = o,sm[s] ++;

		}

		sort(ex + 1,ex + 1 + cte,cm1);

		sort(no + 1,no + 1 + ctn,cm1);

		sort(hi + 1,hi + n,cmp);

		int j = 1;

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

			while(j <= cte && ex[j].j >= hi[i].h) {

				query(ex[j].i,ex[j].l,ex[j].r);

				ex[j].l ++;j ++;

			}

			addr(1,hi[i].id,hi[i].id);

			addl(hi[i].id+1,n,hi[i].id);

		}

		while(j <= cte) {query(ex[j].i,ex[j].l,ex[j].r);ex[j].l ++;j ++;}

		j = 1;

		memset(c,0,sizeof(c));

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

			while(j <= ctn && no[j].j > ex[i].j)

				addtree(no[j].i,1),j ++;

			w[i] = sum(ex[i].r) - sum(ex[i].l-1);

		}

		memset(c,0,sizeof(c));

		for(int i = cte;i > 0;i --) {

			addtree(ex[i].i,1);

			col[ex[i].r].push_back(i);

			w[i] += sum(ex[i].r) - sum(ex[i].l-1);

		}

		memset(dp,0,sizeof(dp));

		int ans = 0;

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

			dp[i] = dp[i-1] + sm[i];

			for(int j = 0;j < (int)col[i].size();j ++) {

				int l = ex[col[i][j]].l;

				int wi = w[col[i][j]];

				dp[i] = max(dp[i],dp[l-1] + wi);

			}

			ans = max(ans,dp[i]);

		}

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

	}

	return 0;

}

巴特西

「雅礼集训 2017 Day2」水箱（数据结构+dp ，一个log）

题面

题解

CODE

最新文章

热门文章

巴特西

「雅礼集训 2017 Day2」水箱 （数据结构+dp ，一个log）

题面

题解

CODE

最新文章

热门文章

「雅礼集训 2017 Day2」水箱（数据结构+dp ，一个log）