[雅礼集训 2017 Day2]水箱

本文主要是介绍[雅礼集训 2017 Day2]水箱，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

水箱

题解

~~其实还是蛮水的一道题。~~

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

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

我们先考虑如何求出这一段区间。这一段区间内一定不包含比当前水位置高的墙，我们可以用一棵线段树，在其前后位置的线段树上二分找出左右第一堵比它高的墙。时间复杂度为 $O(log\, n)$ 。

之后对于这个区间，我们考虑如何维护在这个区间内的条件。我们可以开一棵vector的线段树，每个节点存储有多少个条件在当前节点对应的区间内。对于当前的有水操作求出其对应的不超过 $log\, n$ 的区间中有水条件比它矮的，我们可以根据二分来求出。而选择这个条件可以带来的贡献，是其导致成立的有水条件减去导致不成立的无水条件。

我们求出了每个有水条件对应的区间与贡献后，可以通过dp来求出最大的满足条件值。
总的时间复杂度为 $O(tnlogn^2)$ 。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef long long LL;
const int INF=1e8+10;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
int t,n,m,a[MAXN],maxx[MAXN<<2],ans[MAXN],answ,tot,dp[MAXN];
struct limite{int i,j,k;}q[MAXN];
struct tann{int fl,fr,ak;}s[MAXN];
struct ming{vector<int>lim,lzy;}tr[MAXN<<2];
bool cmp(int x,int y){return q[x].j<q[y].j;}
bool cmp1(tann x,tann y){return x.fr<y.fr;}
void build(int rt,int l,int r){tr[rt].lim.clear();tr[rt].lzy.clear();if(l==r)return (void)(maxx[rt]=a[l]);int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
}
int queryL(int rt,int l,int r,int al,int ar,int aw){if(l>r||al>ar||r<al)return 0;if(al<=l&&r<=ar){if(maxx[rt]<=aw)return 0;if(l==r)return l;int mid=l+r>>1;if(maxx[rt<<1|1]<=aw)return queryL(rt<<1,l,mid,al,ar,aw);return queryL(rt<<1|1,mid+1,r,al,ar,aw);}int mid=l+r>>1,res=0;if(al<=mid)res=max(queryL(rt<<1,l,mid,al,ar,aw),res);if(ar>mid)res=max(queryL(rt<<1|1,mid+1,r,al,ar,aw),res);return res;
}
int queryR(int rt,int l,int r,int al,int ar,int aw){if(l>r||al>ar||r<al)return n;if(al<=l&&r<=ar){if(maxx[rt]<=aw)return n;if(l==r)return l;int mid=l+r>>1;if(maxx[rt<<1]<=aw)return queryR(rt<<1|1,mid+1,r,al,ar,aw);return queryR(rt<<1,l,mid,al,ar,aw);}int mid=l+r>>1,res=n;if(al<=mid)res=min(queryR(rt<<1,l,mid,al,ar,aw),res);if(ar>mid)res=min(queryR(rt<<1|1,mid+1,r,al,ar,aw),res);return res;
}
void Insert(int rt,int l,int r,int ai,int aw){if(l>ai||r<ai||l>r)return ;int mid=l+r>>1;if(q[aw].k==0)tr[rt].lim.push_back(aw);if(q[aw].k==1)tr[rt].lzy.push_back(aw);//printf("%d Insert in %d %d\n",aw,l,r);if(l==r)return ;if(ai<=mid)Insert(rt<<1,l,mid,ai,aw);if(mid<ai)Insert(rt<<1|1,mid+1,r,ai,aw);
}
void Sorted(int rt,int l,int r){sort(tr[rt].lzy.begin(),tr[rt].lzy.end(),cmp);sort(tr[rt].lim.begin(),tr[rt].lim.end(),cmp);if(l==r)return ;int mid=l+r>>1;Sorted(rt<<1,l,mid);Sorted(rt<<1|1,mid+1,r);
}
void Modify(int rt,int l,int r,int al,int ar,int ai){if(l>r||al>r||ar<l)return ;if(al<=l&&r<=ar){int L=0,R=tr[rt].lim.size()-1,num=-1;while(L<=R){int mid=L+R>>1;if(q[tr[rt].lim[mid]].j<=q[ai].j)L=mid+1,num=mid;else R=mid-1;}ans[ai]+=num+1;//printf("%d %d %d:%d ",ai,l,r,num+1);L=0;R=tr[rt].lzy.size()-1;num=-1;while(L<=R){int mid=L+R>>1;if(q[tr[rt].lzy[mid]].j<=q[ai].j)L=mid+1,num=mid;else R=mid-1;}ans[ai]-=num+1;//printf("%d %d\n",num+1,tr[rt].lzy.size());return ;}int mid=l+r>>1;if(al<=mid)Modify(rt<<1,l,mid,al,ar,ai);if(ar>mid)Modify(rt<<1|1,mid+1,r,al,ar,ai);
}
signed main(){freopen("tank.in","r",stdin);freopen("tank.out","w",stdout);read(t);while(t--){read(n);read(m);for(int i=1;i<n;i++)read(a[i]);build(1,1,n);answ=0;tot=0;for(int i=1;i<=m;i++){read(q[i].i);read(q[i].j);read(q[i].k);Insert(1,1,n,q[i].i,i);if(!q[i].k)answ++;}Sorted(1,1,n);for(int i=1;i<=m;i++)if(q[i].k==1){int al=queryL(1,1,n,1,q[i].i-1,q[i].j)+1;int ar=queryR(1,1,n,q[i].i,n,q[i].j);ans[i]=0;Modify(1,1,n,al,ar,i);s[++tot]=(tann){al,ar,ans[i]};//printf("%d %d:%d\n",al,ar,ans[i]);}sort(s+1,s+tot+1,cmp1);int k=0;dp[0]=answ;for(int i=1;i<=n;i++){dp[i]=dp[i-1];while(k<tot&&s[k+1].fr==i)k++,dp[i]=max(dp[i],dp[s[k].fl-1]-s[k].ak);//printf("DP%d:%d\n",i,dp[i]);}printf("%d\n",dp[n]);for(int i=0;i<=n;i++)dp[i]=0;}return 0;
}