自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:07:56，当前版本为作者最后更新于2025-01-03 18:52:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

Purslane 花了半个小时想这道题，已经到了弱智的境界……

设最后每个位置数是 $a_i$，那么限制 $(l,r,d)$ 将得到一个必要条件——$\forall l \le i \le r$，$a_i \ge d$。因此可以计算出每个数的下界 $u_i$。

显然 $i$ 只能放在 $u_j \le i$ 的 $j$ 上。

如果 $i$ 有一些限制，设这些限制的交是 $[L,R]$，则 $j \in [L,R]$。则显然如果 $u_j \le i$，则 $u_j=i$——所以这些 $j$ 都是能放的。

如果没有限制，看有多少个当前还能放数的点即可。

复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10,MOD=1e9+7;
int n,q,rnk[MAXN],ans=1;
vector<pair<int,int>> lim[MAXN];
vector<int> occ[MAXN];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	ffor(i,1,q) {
		int a,b,x;
		cin>>a>>b>>x,lim[x].push_back({a,b});	
	}
	set<int> pos;
	ffor(i,1,n) pos.insert(i);
	roff(i,n,1) {
		for(auto pr:lim[i]) {
			int l=pr.first,r=pr.second;
			while(1) {
				auto it=pos.lower_bound(l);
				if(it==pos.end()||*it>r) break ;
				rnk[*it]=i,pos.erase(it);	
			}
		}
	}
	ffor(i,1,n) rnk[i]=max(rnk[i],1ll),occ[rnk[i]].push_back(i);
	int cnt=0;
	ffor(i,1,n) {
		if(lim[i].size()) {
			int L=0,R=n+1,mul=0;
			for(auto pr:lim[i]) L=max(L,pr.first),R=min(R,pr.second);
			for(auto id:occ[i]) if(L<=id&&id<=R) mul++;
			ans=ans*mul%MOD;
			cnt+=occ[i].size(),cnt--;
		}
		else cnt+=occ[i].size(),ans=ans*cnt%MOD,cnt--;
	}
	cout<<ans;
	return 0;
}