Source Code
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long
#define ld long double
#define R return
//#define B break
#define C continue
#define sf scanf
#define pf printf
#define pb push_back
#define F first
#define S second

using namespace std;

const ll Mod=998244353;

ll poww(ll a,ll b,ll mod){
    ll res=1;if(b<0)b=(b%(mod-1)+mod-1)%(mod-1);
    for(;b;b>>=1,a=1ll*a*a%mod)
      if(b&1)res=1ll*res*a%mod;
    return res;
}

void Max(ll& x,ll y){
x=max(x,y);
}
void Min(ll& x,ll y){
x=min(x,y);
}

void OK(bool yes){
    cout<<(yes?"YES\n":"NO\n");
}

const ll N=300300,M=2010,LN=(1<<24),K=17,Mx=3e5,inf=3e18;
const ld pi=acos(-1),eps=1e-6;

struct constr{
ll l,r,p;
};

ll a[N],Pre[N],up[N],vis[N],st[N*4];
constr c[N];

bool cmp(constr x,constr y){
if(x.p==y.p){
    if(x.r==y.r)return x.l<y.l;
    else x.r<=y.r;
}
else{
    return x.p>y.p;
}
}



void build(int nd,int l,int r)
{
    if(l==r)
    {
        st[nd]=a[l];
        return;
    }

    int mid=(l+r)/2;
    int lf=2*nd;
    int rt=2*nd+1;
    build(lf,l,mid);
    build(rt,mid+1,r);
    st[nd]=(st[lf]+st[rt]);
}



void update(int nd,int l,int r,int from,int to,ll val){

    if( from>r || to<l )return;
    if( from<=l&&r<=to ){
        st[nd]+=val;
        return;
    }
    int mid=(l+r)/2;
    int lf=2*nd;
    int rt=2*nd+1;
    update(2*nd  ,  l  ,mid,from,to,val);
    update(2*nd+1,mid+1, r ,from,to,val);
    st[nd]=st[lf]+st[rt];
}


ll query(int nd,int l,int r,int from,int to){

    if( from<=l&&r<=to )return st[nd];
    if( r<from || l>to )return 0;

    int mid=(l+r)>>1;
    ll lf=query(2*nd  ,  l  ,mid,from,to);
    ll rt=query(2*nd+1,mid+1, r ,from,to);
    return (lf+rt);
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


    int T=1;
    cin>>T;
    while(T--){
        ll n,m,Ans=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i]&=1;
            Pre[i]=Pre[i-1]+a[i];
            up[i]=0;
        }
        for(int i=1;i<=m;i++){
            cin>>c[i].l>>c[i].r>>c[i].p;
        }
        sort(c+1,c+m+1,cmp);
        int j=1;
        for(j=1;j<=m;j++){
            if(c[j].p==1){
                up[c[j].l]++;
                up[c[j].r+1]--;
            }
            else break;
        }
        ll val=0;
        for(int i=1;i<=n;i++){
            val+=up[i];
            if(val){
                vis[i]=1;
                if(a[i]==0){
                    a[i]=1;
                    Ans++;
                }
            }
            Pre[i]+=Ans;
        }
        set<ll> s;
        s.insert(0);
        for(int i=1;i<=n;i++){
            if(!vis[i])s.insert(i);
        }
        s.insert(inf);
        bool ok=1;
        build(1,1,n);
        for(;j<=m;j++){
            ll x=query(1,1,n,c[j].l,c[j].r);
            //cout<<j<<' '<<c[j].l<<' '<<c[j].r<<' '<<x<<'\n';
            if(x==c[j].r-c[j].l+1){
                auto p=s.upper_bound(c[j].r);
                p--;
                ll pos=*p;
                //ll pos=c[j].l;
                //cout<<"P"<<pos<<'\n';
                if(pos<c[j].l){
                    ok=0;
                    break;
                }
                vis[pos]=1;
                a[pos]=0;
                Ans++;
                update(1,1,n,pos,pos,-1);
            }
        }
        if(ok)cout<<Ans;
        else cout<<-1;
        if(T)cout<<'\n';
        for(int i=0;i<=n+10;i++){
            a[i]=Pre[i]=up[i]=vis[i]=c[i].l=c[i].r=c[i].p=0;
        }
        for(int i=0;i<=4*n+10;i++){
            st[i]=0;
        }
        up[0]=up[n+1]=0;
        //OK(ok);
    }


    return 0;
}

/*

*/
Copy
Constraints Wise-ard
GNU G++17
196 ms
1.9 MB
Wrong Answer