题意
先将所所有条件按照高度从小到大排序,其中我们将隔板也看成条件。
现在我们将\(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;
}