(22) two permutation (DP), package delivery (greedy)

Two Permutations

The question
Given length is n The whole arrangement $a[],b[]$, The length is 2n Sequence of numbers $c[]$.
Now use 2n This operation constructs a length of 2n Sequence of numbers , Each operation is arranged from full $a[]$ or $b[]$ Take a number at the front of , Delete it from the sequence , Then add it to the end of the construction sequence .
ask , The constructed sequence eventually becomes a sequence $c[]$ How many construction schemes are there ？

$1\le n\le 300000,\; Number\; of\; schemes\mathrm{mod}998244353$

Ideas
consider dp.
Defining the f1[i, j] Express , Construct a sequence of numbers $c[]$ Before i A place , The last position is full arrangement $a[]$ Of $j$ Location Number of alternatives ;
f2[i, j] Express , Construct a sequence of numbers $c[]$ Before i A place , The last position is full arrangement $b[]$ Of $j$ Location Number of alternatives .

State shift ：
Traverse from front to back c The sequence Each position i, For the current value, find it in a The sequence Where in pos, The number of schemes in this location is transferred from the number of schemes in the previous location , Add the number of schemes at the previous location .
The first i-1 The location may be a The sequence Of pos-1 Location , If so f1[i, pos] Just add f1[i-1, pos-1];
It could also be in the b The sequence Of i-pos Location , If so f1[i, pos] add f2[i-1, i-pos].

Handle in the same way b The sequence Where in .

Preprocessing ：
Preprocess the first position f1[1,1], f2[1, 1], After traversal, transfer from the second position .

So the transfer equation is ：

int t = i-pos1;
if(a[pos1-1] == c[i-1]) f1[i][pos1] += f1[i-1][pos1-1];
if(b[t] == c[i-1]) f1[i][pos1] += f2[i-1][t];

t = i-pos2;
if(b[pos2 - 1] == c[i-1]) f2[i][pos2] += f2[i-1][pos2-1];
if(a[t] == c[i-1]) f2[i][pos2] += f1[i-1][t];

be aware n Size , If you open two dimensions , Two dimensional arrays cannot be saved , Only use map, Time complexity is high .
And observe the state transition , Move from the previous position every time , So you can optimize with a rolling array , Two dimensional compression to one dimension .

int w = 0;
if(a[pos1-1] == c[i-1]) w += f1[pos1-1];
if(b[t] == c[i-1]) w += f2[t];
f1[pos1] = w % mod;

int w = 0;
if(b[pos2 - 1] == c[i-1]) w += f2[pos2-1];
if(a[t] == c[i-1]) w += f1[t];
f2[pos2] = w % mod;

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 300010, mod =  998244353;
int T, n, m;
int a[N], b[N], c[N*2];
int p1[N], p2[N];
map<int, int> f1[2*N], f2[2*N];

signed main(){
    
	Ios;
	cin >> T;
	while(T--)
	{
    
		cin >> n;
		for(int i=1;i<=n;i++) cin >> a[i], p1[a[i]] = i;
		for(int i=1;i<=n;i++) cin >> b[i], p2[b[i]] = i;
		
		for(int i=1;i<=2*n;i++) cin >> c[i];
		
		for(int i=1;i<=2*n;i++) f1[i].clear(), f2[i].clear();
		
		if(a[1] == c[1]) f1[1][1] = 1;
		if(b[1] == c[1]) f2[1][1] = 1;
		
		for(int i=2;i<=2*n;i++)
		{
    
			int pos1 = p1[c[i]], t = i-pos1;
			if(pos1 <= i && t <= n)
			{
    
				if(a[pos1-1] == c[i-1]) f1[i][pos1] += f1[i-1][pos1-1];
				if(b[t] == c[i-1]) f1[i][pos1] += f2[i-1][t];
				f1[i][pos1] %= mod;
			}
			int pos2 = p2[c[i]]; t = i-pos2;
			if(pos2 <= i && t <= n)
			{
    
				int w = 0;
				if(b[pos2 - 1] == c[i-1]) f2[i][pos2] += f2[i-1][pos2-1];
				if(a[t] == c[i-1]) f2[i][pos2] += f1[i-1][t];
				f2[i][pos2] %= mod;
			}
		}
		
		int ans = 0;
		if(a[n] == c[2*n]) ans += f1[2*n][n];
		if(b[n] == c[2*n]) ans += f2[2*n][n];
		cout << ans % mod << endl;	
	}
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 300010, mod =  998244353;
int T, n, m;
int a[N], b[N], c[N*2];
int p1[N], p2[N];
int f1[N], f2[N];

signed main(){
    
	Ios;
	cin >> T;
	while(T--)
	{
    
		cin >> n;
		for(int i=1;i<=n;i++) cin >> a[i], p1[a[i]] = i;
		for(int i=1;i<=n;i++) cin >> b[i], p2[b[i]] = i;
		
		for(int i=1;i<=2*n;i++) cin >> c[i];
		
		for(int i=1;i<=n;i++) f1[i] = f2[i] = 0;
		
		if(a[1] == c[1]) f1[1] = 1;
		if(b[1] == c[1]) f2[1] = 1;
		
		for(int i=2;i<=2*n;i++)
		{
    
			int pos1 = p1[c[i]], t = i-pos1;
			if(pos1 <= i && t <= n)
			{
    
				int w = 0;
				if(a[pos1-1] == c[i-1]) w += f1[pos1-1];
				if(b[t] == c[i-1]) w += f2[t];
				f1[pos1] = w % mod;
			}
			int pos2 = p2[c[i]]; t = i-pos2;
			if(pos2 <= i && t <= n)
			{
    
				int w = 0;
				if(b[pos2 - 1] == c[i-1]) w += f2[pos2-1];
				if(a[t] == c[i-1]) w += f1[t];
				f2[pos2] = w % mod;
			}
		}
		
		int ans = 0;
		if(a[n] == c[2*n]) ans += f1[n];
		if(b[n] == c[2*n]) ans += f2[n];
		cout << ans % mod << endl;
	}
	
	return 0;
}

Experience
The number of schemes ending in the current position from The number of schemes at the end of the above position To transfer , There may be many situations in the previous location , Adding the number of schemes in these cases is the number of schemes in the current position .

---

Package Delivery

The question
Given n Intervals , Each interval has a range $[l_i,r_i]$.
One position can be selected for each operation , Then eliminate the most including this position m Intervals .
ask , At least how many operations can eliminate all intervals ？
$1\le m\le n\le 100000,1\le l_i\le r_i\le 10^9$

Ideas
It is obviously a matter of greed , Consider how greedy .

Only operate at the last position of the interval each time , When operating in the current interval , Take as many sections as possible . This will minimize the number of operations .

Consider simplicity ：
First, sort by the right endpoint , Traverse all intervals from front to back .
If the current range is not eliminated , You need to use an operation to eliminate the current interval , In order to take as many sections as possible , Put this operation position at the right end of the current interval , The rear left end point can be taken away from all the sections in front of this position .

• If the number of intervals that can be taken away is not more than m individual , Because the interval of the current enumeration must be eliminated , So be sure to operate once , Take these sections away .
• But if the number of intervals that can be taken away exceeds m A the , Do you want to take them away ？
  I thought so at first , In order not to waste the number of operations , Take it away every time m A multiple of , The rest of the interval is not taken away . What intervals are left , The left end point is on the right , That is, the one behind the current position .
  It's better to think like this than to take it all away , But it's not the best .
  If the current position can be taken away 2m individual , But there is m individual Can take away m-1 An interval of , If the current position is taken away with two operations , Back m Separate use 1 operations . And if the current position is operated once , Take the rest m Give each to hinder m Intervals , It's like this m The two are still used separately 1 operations , This saves one operation .
  therefore , Each operation can take away at most m Intervals .
  In this case , Just look back m-1 An interval whose left end point is less than or equal to the right end point of the current interval , Take it away with you .

That is to say , Traverse every unmarked interval , After each mark m-1 The left end point does not exceed the interval of the right end point of the current interval .

however , Cannot be in O(nlogn) Realize the above operation within the complexity of .

Just thinking about it is from the front to the back , The top of each package meets m individual . But it is hard to realize .
Then you might as well do the opposite , Every time you look at the current interval, which one is covered by the previous one .

Use a set set To store the interval in which the operation is performed .
Sort by right endpoint , Traverse all intervals from front to back ：

• Find the first interval in the set where the right end of the interval is greater than or equal to the left end of the current interval , That interval is the interval of the current interval of the package . Judge whether the interval has been covered m It's an interval , If it is , Delete it from the set .
• If not , It means that there is no section in front of you that can cover you , Then you need to perform operations in the current interval , Operating frequency ++, Put the current interval into the set , Set the number of packages to 1.

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'
map<int,int> cnt;

const int N = 200010, mod = 1e9+7;
int T, n, m;
PII a[N];
int f[N];

bool cmp(PII a, PII b){
    
	if(a.se != b.se) return a.se < b.se;
	return a.fi < b.fi;
}

set<int> st;

signed main(){
    
	Ios;
	cin >> T;
	while(T--)
	{
    
		cin >> n >> m;
		for(int i=1;i<=n;i++) cin >> a[i].fi >> a[i].se;
		
		sort(a+1, a+n+1, cmp);
		
		st.clear(), cnt.clear();
		
		int ans = 0;
		for(int i=1;i<=n;i++)
		{
    
			auto it = st.lower_bound(a[i].fi);
			if(it == st.end())
			{
    
				ans ++;
				cnt[a[i].se] ++;
				st.insert(a[i].se);
				
				if(cnt[a[i].se] == m) cnt[a[i].se] = 0, st.erase(a[i].se); //m May be 1 
			}
			else
			{
    
				int x = *it;
				cnt[x]++;
				if(cnt[x] == m) cnt[x] = 0, st.erase(x);
			}
		}
		cout << ans << endl;
	}
	return 0;
}