NOI2022 D2T2 题解 有证明。
gyh20
·
·
题解
题解将按照 A,B,C 一步步的深入。
这里称最终的数列为 a，限制为 L_i,R_i,V_i，下面视 n,m 同阶。
先说两个所有部分都要用的性质：
$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)$。
```cpp
#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);
}
}
```