Let's focus on the number of occurrences of each element: let $$$c_i$$$ be the number of time that element $$$i$$$ occurs in the array. To keep a subsequence is to decrease each $$$c_i$$$ by a non-negative integer. We need to make all the non-zero elements in $$$c$$$ the same while maximizing the sum of $$$c$$$.

For each integer $$$x$$$: suppose the value of all non-zero elements in $$$c$$$ is $$$x$$$, what is the length of the longest subsequence?

By Caylex.

def solve():
    n = int(input())
    ls = list(map(int, input().split()))
    a = [0] * n
    for x in ls:
        a[x - 1] += 1
    a = sorted(a)
    s = sum(a)
    ans = s
    for i in range(n):
        ans = min(ans, s - (n - i) * a[i])
    print(n - ans)
    return
 
 
t = int(input())
for _ in range(t):
    solve()

How to check if there is at least one way to choose the sets?

How to greedily find two more solutions to choose the sets?

By Caylex.

def solve():
    n, m = map(int, input().split())
    cnt = [0] * m
    t = 0
    v = []
    for i in range(n):
        v.append([])
        inp = list(map(int, input().split()))
        l = inp[0]
        for j in range(1, l + 1):
            x = inp[j]
            x -= 1
            t += not cnt[x]
            cnt[x] += 1
            v[i].append(x)
    ans = t == m
    for i in range(n):
        for x in v[i]:
            cnt[x] -= 1
            t -= not cnt[x]
        ans += t == m
        for x in v[i]:
            t += not cnt[x]
            cnt[x] += 1
    print("YES" if ans >= 3 else "NO")
    return


t = int(input())
for _ in range(t):
    solve()

How to check if an element $$$x$$$ is stable? For an element $$$p_i$$$, we only care about whether $$$p_i \lt x$$$, $$$p_i=x$$$ or $$$p_i \gt x$$$.

If an element is not stable, we can choose $$$m$$$ correctly in the first step to exclude $$$x$$$ from interval $$$[l,r]$$$.

By Caylex.

def solve():
    n = int(input())
    s = str(input())
    l = 0
    p = []
    for i in range(n):
        p.append(i + 1)
    while l < n:
        if s[l] == "1":
            l += 1
            continue
        r = l
        while r + 1 < n and s[r + 1] == "0":
            r += 1
        if r - l + 1 == 1:
            print("NO")
            return
        ok = 1
        for i in range(l, r):
            p[i] = i + 2
        p[r] = l + 1
        l = r + 1
    print("YES")
    for i in range(n):
        print(p[i], end=" ")
    print()
    return


t = int(input())
for _ in range(t):
    solve()

Try a few cases by hand or guess by the samples, what's the maximized answer for $$$l=0,r=n$$$?

We need to make the bitwise AND of $$$a_i$$$ and $$$b_i$$$ all equal to $$$0$$$. Let's remind you that the bitwise AND of $$$x$$$ and $$$2^k-1-x$$$ is $$$0$$$ for $$$0\le x \lt 2^k$$$. We can try to pair integers $$$x$$$ and $$$y$$$ by letting $$$a_x=y,a_y=x$$$.

Construct from the back.

By Caylex.

def solve():
    l, r = map(int, input().split())
    pw = 1
    ans = 0
    while pw < r:
        pw = pw << 1 | 1
    s = set()
    for i in range(l, r + 1):
        s.add(i)
    a = [0] * (r + 1)
    for i in range(r, l - 1, -1):
        while pw - i not in s:
            pw >>= 1
        a[i] = pw - i
        ans += i | a[i]
        s.remove(pw - i)
    print(ans)
    print(*a[l : r + 1])
    return


t = int(input())
for _ in range(t):
    solve()

Let's consider from the highest bits to the lowest bits. If the highest bits of $$$l$$$ and $$$r$$$ are the same, we can just ignore this bit and go on to a lower bit. We can still try to pair integers $$$x$$$ and $$$y$$$ by letting $$$a_x=y,a_y=x$$$.

Consider the highest bit that $$$l$$$ and $$$r$$$ differs. There exist an integer $$$t$$$ that this bit of $$$l\ldots t-1$$$ are $$$0$$$ and this bit of $$$t\ldots r$$$ are $$$1$$$. We need to pair a $$$0$$$ with a $$$1$$$ as more as possible while keeping the bitwise AND of lower bits small. Can we turn it into a smaller subproblem?

In D1, it is optimal to pair $$$x$$$ with $$$2^k-1-x$$$. Here, for interval $$$[l,r]$$$ and integer $$$t$$$ defined in Hint2, it is optimal to pair $$$x$$$ with $$$2t-1-x$$$.

By Caylex.

def g(x, j):
    return x >> j & 1


def solve():
    L, R = map(int, input().split())
    a = [0] * (R - L + 1)

    def solve(l, r, j):
        if l > r:
            return
        if l == r:
            a[l - L] = r
            return
        mid = l
        while mid + 1 <= r and g(mid + 1, j) == g(l, j):
            mid += 1
        if mid == r:
            solve(l, r, j - 1)
            return
        tl = mid + 1
        tr = mid
        while tl - 1 >= l and tr + 1 <= r:
            tl -= 1
            tr += 1
            a[tl - L] = tr
            a[tr - L] = tl
        solve(l, tl - 1, j - 1)
        solve(tr + 1, r, j - 1)
        return

    solve(L, R, 29)
    ans = 0
    for i in range(L, R + 1):
        ans += a[i - L] | i
    print(ans)
    print(*a)
    return


t = int(input())
for _ in range(t):
    solve()

It turns out that we can solve it greedily from the lowest bit to the highest bit. For each element in $$$[l,r]$$$, let's reverse its binary representation and insert it into a 01-trie. Then for each index $$$i$$$, we can do dfs on the trie while trying to keep every bit different with $$$i$$$. Formally, each step we try to go to the opposite side of each bit of $$$i$$$, and go on the other side if that subtree is empty.

We can prove that this gives the same construction with the other method constructing from the higher bits. You can read the implementation for better understanding.

#include<bits/stdc++.h>
using namespace std;
#define int         long long
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
int l,r;
int tot;
int son[6000005][2],cnt[6000005];
void Main() {
	cin>>l>>r;
	tot=1;
	son[0][0]=son[0][1]=-1;
	REP(i,l,r+1){
		int x=0;
		REP(j,0,30){
			int &p=son[x][(i>>j)&1];
			if(p==-1)p=tot++,cnt[p]=0,son[p][0]=son[p][1]=-1;
			x=p;++cnt[x];
		}
	}
	int ans=0;
	vector<int>res;
	REP(i,l,r+1){
		int x=0,t=0;
		REP(j,0,30){
			int o=!((i>>j)&1);
			if(son[x][o]==-1||!cnt[son[x][o]])o=!o;
			t|=o<<j;
			x=son[x][o];--cnt[x];
		}
		res.pb(t);ans+=i|t;
	}
	cout<<ans<<'\n';
	for(auto i:res)cout<<i<<' ';
	cout<<'\n';
}
void TC() {
    int tc=1;
    cin>>tc;
	while(tc--){
		Main();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */

For an array $$$b$$$ and an integer $$$x$$$ that does not appear in $$$b$$$, let $$$g(b,x)$$$ be the number of elements in $$$b$$$ that is greater than $$$x$$$. Then the weight of $$$b$$$ equals to $$$g(b,\rm{mex}(b))$$$. However, when $$$x\neq \rm{mex}(b)$$$, what will happen to $$$g(b,x)$$$?

For a fixed right endpoint $$$r$$$, let's enumerate over all the $$$x$$$ and maximize $$$g(a[l\dots r],x)$$$ while keeping $$$x$$$ no occurred in $$$a[l\dots r]$$$. It's clear that the value is maximized for $$$x$$$ if $$$l$$$ equals the last occurrence of $$$x$$$ plus $$$1$$$.

Use a segment tree to maintain the answer for each $$$x$$$.

By LMydd0225.

#include<bits/stdc++.h>
using namespace std;
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
int n;
int a[300005];
struct ds{
	int seg[1200005],tag[1200005];
	void build(int l,int r,int p){
		seg[p]=tag[p]=0;
		if(l==r)return;
		int m=(l+r)>>1;
		build(l,m,p*2+1);build(m+1,r,p*2+2);
	}
	void update(int l,int r,int s,int t,int p){
		if(l<=s&&t<=r){
			++seg[p];++tag[p];
			return;
		}
		int m=(s+t)>>1;
		if(m>=l)update(l,r,s,m,p*2+1);
		if(m<r)update(l,r,m+1,t,p*2+2);
		seg[p]=max(seg[p*2+1],seg[p*2+2])+tag[p];
	}
	void point(int pos,int l,int r,int p,int val=0){
		if(l==r)return seg[p]=-val,void();
		int m=(l+r)>>1;
		val+=tag[p];
		if(m>=pos)point(pos,l,m,p*2+1,val);
		else point(pos,m+1,r,p*2+2,val);
		seg[p]=max(seg[p*2+1],seg[p*2+2])+tag[p];
	}
}seg;
void Main() {
	cin>>n;
	REP(i,0,n)cin>>a[i];
	seg.build(0,n,0);
	REP(i,0,n){
		seg.update(0,a[i],0,n,0);
		seg.point(a[i],0,n,0);
		cout<<seg.seg[0]<<' ';
	}
	cout<<'\n';
}
void TC() {
    int tc=1;
    cin>>tc;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */

There's a harder version of the problem. Can you solve it?

There're $$$q$$$ queries: $$$x,y$$$. Find $$$\max_{x\le l\le r\le y}w(l,r)$$$. $$$n,q\le 3\cdot 10^5$$$.

Let's focus on bubble sort first. For an element $$$p_x$$$, how many rounds does it take to make all the numbers before the position small than $$$p_x$$$?

Try to count something else instead of permutations $$$p$$$. Can you come up with an $$$O(n^2)$$$ dynamic programming method?

The number of restrictions is small ($$$m\le 1000$$$). Can we decrease the number of states from $$$O(n^2)$$$ to $$$O(nm)$$$ and $$$O(m^2)$$$? How to calculate the coefficients then?

By LMydd0225.

#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define speMOD      2933256077ll
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define rf(v)       shuffle(all(v),sd);
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
int qpow(int a,int b,int m=MOD,int res=1){
	a%=m;
	while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1;
	return res;
}
int fac[2000005],inv[2000005];
void init(int n){
	fac[0]=inv[0]=1;
	REP(i,1,n+1)fac[i]=fac[i-1]*i%MOD;
	inv[n]=qpow(fac[n],MOD-2);
	for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%MOD;
}
int binom(int x,int y){
	return x<y||y<0? 0:fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
struct restr{
	int l,r,k;
};
int n,m;
int r1[1000005],r2[1000005];
int dp[10005],sum[10005];
int qry1(int l,int r,int k){
	if(k<l)return qpow(k+1,r-l+1);
	if(k>r)return fac[r+1]*inv[l]%MOD;
	return fac[k+1]*inv[l]%MOD*qpow(k+1,r-k)%MOD;
}
int qry2(int l,int r,int k,int x){
	return (qry1(l,r,k)+MOD-qry1(l,r,x))%MOD;
}
void Main() {
	cin>>n>>m;
	vector<int>v;vector<restr>a;
	vector<int>t;
	REP(i,0,m){
		int k,l,r;
		cin>>k>>l>>r;
		--l;
		if(l>=0)v.pb(l);
		if(r<n)v.pb(r);
		t.pb(k);
		a.pb({l,r,k});
	}
	v.pb(n-1);t.pb(-1);t.pb(n-1);
	deal(v);deal(t);
	for(auto i:v)r1[i]=t.size()-1,r2[i]=0;
	for(auto i:a){
		if(i.k==n-1&&i.r<n-1)over(0)
		if(i.l>=0)r1[i.l]=min(r1[i.l],lbound(t,i.k));
		if(i.r<n)r2[i.r]=max(r2[i.r],lbound(t,i.k));
	}
	int lst=0,m=t.size();dp[1]=1;REP(i,2,m+1)dp[i]=0;
	for(auto i:v){
		REP(j,1,m)sum[j]=dp[j];
		REP(j,2,m)(sum[j]+=sum[j-1])%=MOD;
		REP(j,1,m)if(j>r2[i]&&j<=r1[i]){
			dp[j]=(dp[j]*qry1(lst,i,t[j])+sum[j-1]*qry2(lst,i,t[j],t[j-1]))%MOD;
		}else dp[j]=0;
		lst=i+1;
	}
	int res=0;
	REP(j,1,m+1)(res+=dp[j])%=MOD;
	cout<<res<<endl;
}
void TC() {
	init(1000000);
    int tc=1;
    cin>>tc;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */