自动搬运

查看原文

来自洛谷，原作者为

	gyh20 orz Feecle6418

搬运于2025-08-24 22:39:37，当前版本为作者最后更新于2022-08-30 09:34:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解将按照 A,B,C 一步步的深入。

这里称最终的数列为 $a$，限制为 $L_i,R_i,V_i$，下面视 $n,m$ 同阶。

先说两个所有部分都要用的性质：

$1.$ 存在一种最优情况，使得最终数列中的所有数都为输入的 $L_i,R_i,V_i$ 其中一个的 $V_i$。如果不是，将这个区间的数全体调整即可。

$2.$ 若存在 $i<j,a_i>a_j$，且交换 $a_i,a_j$ 后合法，则交换后一定更优。证明显然。

先考虑 A：

此时的限制有两种：区间全为 $1$，称其为 $1$ 类限制，和区间不全为 $1$，称其为 $2$ 类限制。

根据性质 $2$，若存在相邻的 $10$ 且可以交换一定更优，所以对于每一个 $0$ 的连续极长区间，都有其的第一个位置是某个 $2$ 类限制的 $L$，或其前一个位置是一个 $1$ 类限制的 $R$。

将所有的 $1$ 类限制求一个区间覆盖。

将所有的 $2$ 类限制按照 $L$ 从大到小排序。在这样的顺序下，我们可以贪心，若区间内没有已经钦定为 $0$ 的位置，则把区间内第一个没有被 $1$ 类区间覆盖的位置强制钦定为 $0$，因为若该位置不为 $0$ 且后面有 $0$，可以直接交换。

做了这样的操作之后，每一个限制都已经合法了，于是现在的情况就是一些位置强制为 0/1，剩下位置没有限制，根据性质 $2$，那么剩下的位置必定是一个前缀为 $0$，枚举一下分界线，中途涉及到的操作做到 $O(n\log n)$ 是容易的。

B:

相当于有一些单点的限制，无解的情况可以轻易判掉。

然后发现一个神奇的性质，局部最优解构成了全局最优解，即，对于每个没有限制的位置单独考虑，其位置越靠后，最终选的值会越大。即，对于每个点，只考虑其于已经被限制的点的贡献来选出一个最优解，那么这些位置的上的值内部不存在逆序对。用线段树容易 $O(n\log n)$。证明很容易理解，实在不行把维护单点最优解的线段树操作拿出来很容易理解。

C:

首先根据性质 $2$，区间最小值一定在区间的第一个。

然后可以近似看作 B，在 B 的基础上，多了一些 $a_i\geq k_i$ 的限制。

这里先说做法，和 B 做一模一样的操作，从前往后，找局部最优解即线段树上 $\geq k_i$ 的位置上的最小值，若有多个选最靠前的。

为什么这样是正确的呢？首先选更大的位置显然是不优的，因为是从前往后的，选的越小对后面的位置影响越小，如果当前选的为 $x$，假设存在某个更优的位置是 $y$，那么直接将最终序列当前位置之后的所有值在 $[y,x]$ 之间的数变为 $x$ 即可，这样显然是合法并且不劣的。

正解：

还是尝试将问题转化为限制某些位置的值 $=V_i$，某些位置的值 $\geq V_i$，后者即为被覆盖的位置取一个 $\max$。

若两个区间相交且 $V$ 不同，那么可以缩短 $V$ 小的一个区间，看成不相交，若 $V$ 相同，可以直接用 A 性质来搞出对单点的限制。

于是最终的流程即为，从大到小枚举 $x$，对所有的 $V_i=x$ 的位置用 A 中的做法进行标记，然后将区间内的所有位置删掉，之后不能被标记，若任意时刻找不到合法的标记输出 $-1$，这部分可以用并查集。

然后对于已经限制的点内部用一个树状数组统计逆序对，剩下的用一个线段树动态维护。总复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
int t,n,m,a[1000002],A,B,L[1000002],R[1000002],V[1000002],W[1000002],mn[4000002],mnp[4000002],tg[4000002],fa[1000002],V1[1000002],V2[1000002],c[1000002],ans1,ans2;
char s[1000002];
inline void add(re int x){for(;x;x^=x&(-x))++c[x];}
inline int ask(re int x,re int s=0){for(;x<=m;x+=x&(-x))s+=c[x];return s;} 
inline void build(re int p,re int l,re int r){
	tg[p]=mn[p]=0,mnp[p]=l;
	if(l==r)return;
	re int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r); 
}
inline void pu(re int p){
	mn[p]=min(mn[p<<1],mn[p<<1|1]);
	if(mn[p]==mn[p<<1])mnp[p]=mnp[p<<1];
	else mnp[p]=mnp[p<<1|1];
}
inline void Add(re int x,re int y){mn[x]+=y,tg[x]+=y;}
inline void pd(re int p){
	if(tg[p])Add(p<<1,tg[p]),Add(p<<1|1,tg[p]),tg[p]=0;
}
inline void add(re int p,re int l,re int r,re int x,re int y,re int z){
	if(l>=x&&r<=y)return Add(p,z);
	pd(p);
	re int mid=l+r>>1;
	if(x<=mid)add(p<<1,l,mid,x,y,z);
	if(y>mid)add(p<<1|1,mid+1,r,x,y,z);
	pu(p);
}
inline void ask(re int p,re int l,re int r,re int x,re int y){
	if(l>=x&&r<=y){
		if(mn[p]<ans2)ans2=mn[p],ans1=mnp[p];
		return;
	}pd(p);
	re int mid=l+r>>1;
	if(x<=mid)ask(p<<1,l,mid,x,y);
	if(y>mid)ask(p<<1|1,mid+1,r,x,y);
}
struct node{int x,y;bool operator <(const node A)const{return x<A.x;};};
inline int root(re int x){return x==fa[x]?x:fa[x]=root(fa[x]);}
vector<node>G[1000002];
int main(){
	t=read();
	while(t--){
		n=read(),m=read();
		for(re int i=1;i<=m;++i)L[i]=read(),R[i]=read(),V[i]=W[i]=read(),G[i].clear();
		for(re int i=1;i<=n;++i)V1[i]=V2[i]=0; 
		sort(W+1,W+m+1);
		for(re int i=1;i<=m;++i)V[i]=lower_bound(W+1,W+m+1,V[i])-W,G[V[i]].push_back((node){L[i],R[i]});
		for(re int i=1;i<=n+1;++i)fa[i]=i;re bool ia=1;
		for(re int i=m;i&&ia;--i)if(G[i].size()){
			sort(G[i].begin(),G[i].end());
			re int lst=n+1; 
			for(re int j=G[i].size()-1;~j&&ia;--j)
				if(G[i][j].y<lst){
					re int pos=root(G[i][j].x);
					V1[pos]=i,ia&=pos<=G[i][j].y,lst=pos;
				}
			for(auto z:G[i])
			for(re int j=root(z.x);j<=z.y;j=root(j))V2[j]=i,fa[j]=j+1;
		}if(!ia){puts("-1");continue;}build(1,0,m+1);long long ans=0;
		for(re int i=1;i<=m;++i)c[i]=0;
		for(re int i=1;i<=n;++i)if(V1[i])ans+=ask(V1[i]+1),add(V1[i]),add(1,0,m+1,V1[i]+1,m+1,1);
		for(re int i=1;i<=n;++i)
			if(V1[i])add(1,0,m+1,V1[i]+1,m+1,-1),add(1,0,m+1,0,V1[i]-1,1);
			else{
				ans2=1e9,ask(1,0,m+1,V2[i],m+1);
				ans+=ans2;
				if(ans1)add(1,0,m+1,0,ans1-1,1);
			}
		printf("%lld\n",ans);
	}
}