首先考虑A性质的点。区间最小值为 \(1\) 的限制等价于要求区间所有值为 \(1\) 。另外一种限制等价于区间不全为 \(1\) 。
把一定是 \(1\) 的做一个区间覆盖。其他部分暂且设为 \(0\) 。设当前暂时的序列为 \(a_i\) ， \(s_i\) 为 \(a_i\) 的前缀和，那么若 \(a_i=0\) ，若把 \(a_i\) 变成 \(1\) 的话，逆序对数的改变量为 \(-s_i+(n-i-(s_n-s_i))=n-i-s_n\) 。惊奇的发现他只和整个序列 \(1\) 的数量有关。那么初始状态下， \(i>n-s_n\) 的位置改成 \(1\) 的话，逆序对数一定减少。这个过程中 \(s_n\) 也在增大，所以使逆序对减小的 \(i\) 的下界也在减少。那么就只需要倒序依次考虑每一个位置是否要变为 \(1\) 即可。
接下来考虑如何满足一个区间不全为 \(1\) 的限制。这个是一种常见的考虑dp的方法。和 noi2020d1t2 类似，当前已经逆序决策到了 \(i\) 下标。那么我们时刻维护“当前还没满足条件的限制的左端点的最大值\(rm\)”，则在 \([rm,i]\) 内必须要有一个 \(0\) 。对于一个变成 \(1\) 会更优的位置，我们只需要考虑若这次把他变成 \(1\) 了，那 \([rm,i-1]\) 还有没有机会出现 \(0\) 即可，这样我们可以知道每个位置是否必须取到 \(0\) 。其中 \(rm\) 和上一个 \(0\) 的位置都可以循环时直接维护，时间复杂度 \(O(n)\) 。
性质 B
首先此题有一个很显然的结论，就是最优序列一定可以是每个位置都填出现过的 \(V_i\) 。否则调整后一定不劣。考虑某一个非确定位置的位置 \(i\) ，它对逆序对数的贡献是 \(\sum\limits_{j<i}[a_j>a_i]+\sum\limits_{j>i}[a_j<a_i]=\sum\limits_{j<i}[a_j>a_i]+n-i-\sum\limits_{j>i}[a_j\geq a_i]\) 。那么这个东西如果每一个空位单独考虑的话，很容易用线段树维护出来。而且发现（因为A我思维定式了，其实正着做也行）逆序依次决定的话，这棵以取值为下标，维护贡献的线段树的修改都是前缀减 \(1\) ，查询都是全局最小。也就是说，他的最小值点永远在减小。只需要考虑任意两个位置之间大小关系很容易看出来。在序列上也就是空位内部一定没有逆序对。所以每个位置贡献独立，用线段树维护即可，时间复杂度 \(O(n\log m)\) 。
我到这时候我才反应过来这个本该更早意识到的结论：空位内部没有逆序对，否则调整一定更优。
C 性质和B 性质其实没啥大差别。很显然如果区间之间无影响的话，最小值点一定取在区间左端点。区间 \([l+1,r]\) 的点要求 \(a_i\geq v\) 。那么有类似的结论：若位置 \(i\) 处取了 \(a_i\) ，则 \(j<i\) 和 \(i\) 形成逆序对当且仅当 \(j\) 处要求的下界大于 \(a_i\) 。其余部分依然一定没有逆序对，否则交换一定更优。所以就把 \(j<i,mn_j>a_i\) 的贡献同样考虑在线段树上即可，和B性质一样做法，代码甚至都没差太多。至此已经有足足80分
正解
对于一般情况，考虑如何判无解。这是个经典问题，印象中好像是个奶牛题。对于两个限制，若两个限制相交，则限制区间最小值较小的那个限制比较大的限制更松。也就是说他们的交集只需考虑限制最小值较大的那个限制即可。那么就可以考虑从大到小考虑所有限制。如果某个限制的区间已经被之前的较大限制覆盖过了，那么是不合法的。这个过程用类似并查集，其实就是记一个后继的思路可以做到 \(O(n)\) ，同时求出来每个位置取值的下界 \(mn_i\) 。
所以现在这些限制可以转化为，每个位置的 \(a_i\geq mn_i\) ，且每个区间必须有个位置取到最小值。显然这个取到最小值的位置一定是越靠左越好。那么对于每个值 \(v\) ，把 \(V_i=v\) 的限制和他限制的区间中 \(mn_x=v\) 的位置拿出来，对他们做类似性质 A 做法的贪心，倒着做，考虑“还没满足的限制里最靠右的左端点”即可求出一些必须要强制取到 \(v\) 的位置。而其他位置只需满足大于 \(v\) 即可满足条件。
这样就完全转化为了 C 性质最终要维护的问题：一部分点固定，一部分点有下界，倒着扫一遍维护线段树即可。时间复杂度 \(O(n\log m)\) 。
ABC 性质不算很困难，最后用经典奶牛题的做法，再结合起来A和C做法这一步还是差在这了。其实要是很熟悉那个题的话，这一步也算是自然。
我代码写的有点放飞自我，但是要是写的收敛一些的话我这个做法的常数还是比较小的，对A性质的处理比较简单。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define N 1101200
inline void rd(int &x)
{x=0;register char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
}
struct node{int l,r,mn;}b[N];
bool cmp(node n1,node n2){return n1.mn>n2.mn;}
int T,n,m,s[N],a[N],rm[N],pre[N],mn[N<<2],mnp[N<<2],rt,laz[N<<2];
int lsh[N],tot,dn[N],nxt[N];
vector<int>v[N];
inline void gv(int ind,int x){mn[ind]+=x;laz[ind]+=x;}
void pushdown(int ind){gv(ind<<1,laz[ind]);gv(ind<<1|1,laz[ind]);laz[ind]=0;}
void pushup(int ind)
{
if(mn[ind<<1]<mn[ind<<1|1])mn[ind]=mn[ind<<1],mnp[ind]=mnp[ind<<1];
else mn[ind]=mn[ind<<1|1],mnp[ind]=mnp[ind<<1|1];
}
void bt(int ind,int l,int r)
{mn[ind]=laz[ind]=0;
if(l==r){mnp[ind]=l;return;}
int mid=(l+r)>>1;
bt(ind<<1,l,mid);bt(ind<<1|1,mid+1,r);
pushup(ind);
}
void chng(int ind,int l,int r,int al,int ar,int x)
{if(al>ar)return;
if(al<=l&&r<=ar){gv(ind,x);return;}
int mid=(l+r)>>1;pushdown(ind);
if(al<=mid)chng(ind<<1,l,mid,al,ar,x);
if(ar>mid)chng(ind<<1|1,mid+1,r,al,ar,x);
pushup(ind);
}
pair<int,int> ask(int ind,int l,int r,int al,int ar)
{
if(al<=l&&r<=ar)return make_pair(mn[ind],mnp[ind]);
int mid=(l+r)>>1,rmn=1e9,rmnp;pushdown(ind);
if(al<=mid)
{
pair<int,int> ret=ask(ind<<1,l,mid,al,ar);
if(ret.first<rmn)rmn=ret.first,rmnp=ret.second;
}
if(ar>mid)
{
pair<int,int> ret=ask(ind<<1|1,mid+1,r,al,ar);
if(ret.first<=rmn)rmn=ret.first,rmnp=ret.second;
}
return make_pair(rmn,rmnp);
}
inline int getpos(int co,int x)
{
int l=0,r=v[co].size()-1,mid,ret;
while(l<=r)
{
mid=(l+r)>>1;
if(x>=v[co][mid])ret=mid,l=mid+1;
else r=mid-1;
}return ret;
}
int main()
{
rd(T);
while(T--)
{
rd(n),rd(m);
for(int i=1;i<=m;i++)
{
rd(b[i].l),rd(b[i].r),rd(b[i].mn);
}
for(int i=1;i<=n;i++)a[i]=dn[i]=0;
tot=0;for(int i=1;i<=m;i++)lsh[++tot]=b[i].mn;
sort(lsh+1,lsh+1+tot);tot=unique(lsh+1,lsh+1+tot)-lsh-1;
for(int i=1;i<=m;i++)b[i].mn=lower_bound(lsh+1,lsh+1+tot,b[i].mn)-lsh;
sort(b+1,b+1+m,cmp);
bool flag=true;
for(int i=1;i<=n;i++)nxt[i]=i+1;
for(int i=1;i<=m;i++)
{
bool tf=false;
for(int j=b[i].l;j<=b[i].r;j=nxt[j])
{
if(dn[j]<=b[i].mn)dn[j]=b[i].mn,tf=true;
}
if(!tf){flag=false;break;}
for(int j=b[i].l;j<=b[i].r;)
{
int nx=nxt[j];
if(dn[j]==b[i].mn)nxt[j]=nxt[b[i].r];
j=nx;
}
}
if(!flag)
{
puts("-1");
continue;}
for(int i=1;i<=tot;i++)v[i].clear();
//for(int i=1;i<=n;i++)printf("%d ",dn[i]);puts("dn");
for(int i=1;i<=n;i++)if(dn[i])v[dn[i]].push_back(i);
for(int i=1;i<=m;i++)
{
int j=i;while(j<=m&&b[i].mn==b[j].mn)j++;j--;
int co=b[i].mn;
int len=v[co].size();
if(!len){i=j;continue;}
for(int ii=0;ii<len;ii++)rm[v[co][ii]]=0;
for(int ii=i;ii<=j;ii++)
{
int tx=getpos(co,b[ii].r);
rm[v[co][tx]]=max(rm[v[co][tx]],b[ii].l);
}
int trm=0;
for(int ii=len-1;ii>=0;ii--)
{
int tx=v[co][ii];
trm=max(trm,rm[tx]);
if(trm&&(ii==0||v[co][ii-1]<trm))a[tx]=co,trm=0;
else a[tx]=-co;
}
i=j;
}
//for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("aa");
bt(1,1,tot);
for(int i=1;i<=n;i++)
{
if(a[i]>0)
{
chng(1,1,tot,1,a[i]-1,1);
}
}
for(int i=1;i<=n;i++)if(a[i]<0)
{
chng(1,1,tot,1,-a[i]-1,1);
}
//printf("%lld\n",ans);
for(int i=n;i;i--)
{
if(a[i]==0)
{
int tp=mnp[1];
a[i]=tp;
chng(1,1,tot,1,tp,-1);
}
else if(a[i]<0)
{
chng(1,1,tot,1,-a[i]-1,-1);
pair<int,int>pr=ask(1,1,tot,-a[i],tot);
a[i]=pr.second;
chng(1,1,tot,1,pr.second,-1);
}
else
{
chng(1,1,tot,1,a[i]-1,-1);
chng(1,1,tot,1,a[i],-1);
}
}
ll ans=0;
bt(1,1,tot);
for(int i=1;i<=n;i++)
{
pair<int,int>pr=ask(1,1,tot,a[i],a[i]);
ans+=pr.first;
chng(1,1,tot,1,a[i]-1,1);
}
printf("%lld\n",ans);
}
}