题意

先将所所有条件按照高度从小到大排序,其中我们将隔板也看成条件。

现在我们将\(n\)个格子看成\(n\)个连通块,之后从\(1\)开始扫描,并维护每个联通块如下信息:
\(nowans\)表示当前连通块最多能满足几个条件。
\(sum\)表示该连通块如果涨到当前水位,这个联通块的答案是多少。

对于每种条件\((x,h)\)\(x\)是位置,\(h\)是高度):
1.是隔板:
\(x\)\(x+1\)所在联通块合并,\(nowans\)\(sum\)相加即可。
2.没有水的条件:
直接\(nowans++\),因为涨到当前水位,这个点会被淹没,\(sum\)是不会变的。
3.有水的条件:
\(sum++\),并与\(nowans\)\(\max\)

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int T,n,m,ans;
int fa[maxn],sum[maxn],nowans[maxn];
struct Query{int x,k,op;}qr[maxn<<1];
inline int read()
{
    char c=getchar();int res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
inline bool cmp(Query a,Query b){return a.k==b.k?a.op<b.op:a.k<b.k;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void solve()
{
    memset(sum,0,sizeof(sum));
    memset(nowans,0,sizeof(nowans));
    ans=0;
    n=read(),m=read();
    for(int i=1;i<n;i++)qr[i].x=i,qr[i].k=read(),qr[i].op=-1;
    for(int i=1;i<=m;i++)qr[i+n-1].x=read(),qr[i+n-1].k=read(),qr[i+n-1].op=read();
    sort(qr+1,qr+n+m,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<n+m;i++)
    {
        if(qr[i].op==-1)
        {
            int x=find(qr[i].x),y=find(qr[i].x+1);
            if(x==y)continue;
            fa[x]=y;nowans[y]+=nowans[x];sum[y]+=sum[x];
            nowans[y]=max(nowans[y],sum[y]);
            ans=max(ans,nowans[y]);
        }
        if(!qr[i].op)
        {
            int x=find(qr[i].x);nowans[x]++;
            ans=max(ans,nowans[x]);
        }
        if(qr[i].op==1)
        {
            int x=find(qr[i].x);sum[x]++;
            nowans[x]=max(nowans[x],sum[x]);
            ans=max(ans,nowans[x]);
        }
    }
    printf("%d\n",ans);
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    T=read();
    while(T--)solve();
    return 0;
}
12-16 19:32