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

题面

题解

在网上看到有些做法，有什么平衡树、启发式合并等等总之复杂度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;
}