luogu P8500 [NOI2022] 冒泡排序

题面传送门

这个部分分提示得太妙了。

首先这个冒泡排序的壳已经被套烂了，就是对逆序对计数。

首先观察一下，发现第一个样例解释中在等于某个限制对应的最小值的时候取到逆序对最小值，因此可以猜测一定值域在这些里面。然后发现显然是对的，因为将一个数靠到最近的限制的值之后不会增加原有的逆序对，而可能会减少因此一定不会更劣。

考虑特殊限制B，相当于现在的序列中剩下的是一堆确定的值和一堆任意的值，考虑证明这样一个结论：任意的值不降，因为如果任意的值存在逆序对那么将这两个逆序对互换一定不会使对确定值得逆序对变大，而会使任意值得逆序对变小。所以任意值之间不会产生逆序对，每个任意值的取值只和两边的确定的值有关，可以用一个线段树维护出答案。

显然，对于任意情况下这个单调性依然存在，即：若(x,y)任选，(a_y>a_x,x>y)且交换后满足最小值的限制，则交换后一定不劣。

之后考虑特殊性质C。这里有一个套路拆最小值恰好为(x)的方法：至少有一个位置等于(x)，且全部数都要大于等于(x)，那么我们现在的问题就在于确定最小值的位置，然后剩下就可以套用B的方法。注意到每个区间是相对独立的，因此如果这个区间内的数固定，两个数交换是不会影响到这个区间和两边区间的逆序对个数的，而只会影响其自身。因此把最小值放在区间开头一定最优。

那么对于区间有交的情况呢？这里就存在区间共用一个最小值的情况，但是可以发现，将最小值限制相同的区间按照左端点降序排序后，第一个区间可以看成相对独立的，因此可以放在开头，而这也是共用区间最容易的。因此策略就是：排序后如果一个区间内部有最小值那就不额外标记，否则标记在最开头。

别忘记计算这些已经确定的值之间的逆序对。

然后你发现这个东西显然可以过特殊性质A。

然后你发现这个东西其实已经正确了，是(O(n^2))的。看你实现能得(72)到(76)分。

然后你发现你用个并查集做一下每个最小值定在哪里，用个树状数组数一下确定的值之间的逆序对，用个线段树维护一下选数的过程即可。可以做到(O(nlog n))。

我不会告诉你我暴力忘记删然后以为自己被卡常卡了一年

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=1e6+5,M=N*4+5,K=1e5+5,mod=1e9+7,Mod=mod-1,INF=1e9+7;const db eps=1e-5;mt19937 rnd(time(0));
int n,m,k,x,y,z,Nh,vis[N],W[N],f1[N],f2[N],Ts,YZX;ll Ans;
struct Node{int l,r;};vector<Node> S[N];bool cmp(Node x,Node y){return x.l>y.l;}
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='n'||x=='r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
namespace Init{
	int L[N],R[N],V[N],Ns[N],fa[N];int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;}
	void Solve(){
		int i,j;fin>>n>>m;Nh=0;for(i=1;i<=m;i++) fin>>L[i]>>R[i]>>V[i],Ns[++Nh]=V[i];
		sort(Ns+1,Ns+Nh+1);Nh=unique(Ns+1,Ns+Nh+1)-Ns-1;for(i=1;i<=m;i++) V[i]=LB(Ns+1,Ns+Nh+1,V[i])-Ns;
		for(i=1;i<=n+1;i++) W[i]=-1e9,vis[i]=0,fa[i]=i;for(i=1;i<=Nh;i++) S[i].clear();for(i=1;i<=m;i++) S[V[i]].PB((Node){L[i],R[i]});
		for(i=Nh;i;i--) {
			sort(S[i].begin(),S[i].end(),cmp);int Mx=1e9;for(Node j:S[i]){
				int Fl=0,x=GF(j.l);if(Mx<=j.r) Fl=1;
				if(!Fl&&x<=j.r) vis[x]=i,Fl=1,Mx=x;
				if(!Fl){puts("-1");YZX=1;return;}
			}for(Node j:S[i]){int x=GF(j.l);while(x<=j.r) W[x]=i,fa[x]=GF(x+1),x=GF(x);}
		}
	} 
}
namespace BIT{int f[N];void Cl(){for(int i=1;i<=Nh;i++) f[i]=0;}void Ins(int x){while(x<=Nh) f[x]++,x+=x&-x;}int Qry(int x){int Ans=0;while(x) Ans+=f[x],x-=x&-x;return Ans;}}
namespace SGT{
	#define ls v<<1
	#define rs v<<1|1
	struct Node{int w,Id;Node operator +(const Node &B)const{return w<B.w?(Node){w,Id}:B;};}Cl=(Node){INF,INF},Pl;
	Node f[M];int g[M];void Up(int v){f[v]=f[ls]+f[rs];f[v].w+=g[v];}
	void BD(int l=0,int r=Nh+1,int v=1){f[v]=Pl;g[v]=0;if(l==r){f[v].Id=l;return;}int m=l+r>>1;BD(l,m,ls);BD(m+1,r,rs);Up(v);}
	void Ins(int x,int y,int z,int l=0,int r=Nh+1,int v=1){if(x<=l&&r<=y) {g[v]+=z;f[v].w+=z;return;}int m=l+r>>1;x<=m&&(Ins(x,y,z,l,m,ls),0);y>m&&(Ins(x,y,z,m+1,r,rs),0);Up(v);}
	Node Qry(int x,int y,int l=0,int r=Nh+1,int v=1){if(x<=l&&r<=y) return f[v];int m=l+r>>1;Node p=(x<=m?Qry(x,y,l,m,ls):Cl)+(y>m?Qry(x,y,m+1,r,rs):Cl);p.w+=g[v];return p;}
	#undef ls
	#undef rs
}
void Solve(){
	int i,j,h;YZX=0;Init::Solve();if(YZX) return;
	Ans=0;for(i=n;i;i--) vis[i]&&(BIT::Ins(vis[i]),Ans+=BIT::Qry(vis[i]-1));BIT::Cl();
	SGT::BD();for(i=1;i<=n;i++) vis[i]&&(SGT::Ins(vis[i]+1,Nh+1,1),0);
	for(i=1;i<=n;i++)if(!vis[i]){
		//Ts=max(W[i],1);for(j=max(W[i],1)+1;j<=Nh;j++) f1[Ts+1]+f2[Ts-1]>f1[j+1]+f2[j-1]&&(Ts=j);
		SGT::Node p=SGT::Qry(max(W[i],1),Nh);
		vis[i]=p.Id;Ans+=p.w;SGT::Ins(0,vis[i]-1,1);
	}else SGT::Ins(vis[i]+1,Nh+1,-1),SGT::Ins(0,vis[i]-1,1);printf("%lldn",Ans);
}
int main(){
	freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	int t;fin>>t;while(t--) Solve(); 
}