T1

30 分

暴力枚举即可。

60 分

注意到选定一个 $x$ 后，每次 $p$ 一定是选一个质数，所以最大得分就是 $x$ 的质因子数目，枚举 $x$ 即可。

正解

注意到有一个条件 $2l\le r$，猜测答案就是最大的 $2^t\le r$，实际上这是显然的。

发现至少有 $t$ 个质因子的数是 $2^t$，因为 $\log_2 l+1\le \log_2r$，所以这个 $2^t\ge l$ 肯定成立。

#include<bits/stdc++.h>
using namespace std;
inline void solve(){
	int l,r,x;
	cin>>l>>r;
	x=1;int res=0;
	while(x*2<=r){
		res++;
		x*=2;
	}
	cout<<res<<endl;
}
signed main(){
	solve();
	return 0;
}
/*
l=1怎么处理
[1,r] 以内的质因数最多的个数
 2*2*2*2*2*2
l=1:2^k 
2l<=r
2^k
*/

T2

30 分

暴力即可。

60 分

对每一位滚一个前缀和就好，查询就对每一位查能否为 $1$。

正解

二进制问题就按位做，考虑 $l\sim r$ 中是否存在一个数满足二进制第 $i$ 位为 $1$。

考虑贪心的构造尽量一个大的满足 $\le r$ 的数，那么肯定是找到 $r$ 中第 $j(j>i)$ 位为 $1$ 的位置，把这一位变成 $0$，更高的位不动，第 $j$ 位后面的全部变成 $1$，那么这是一个合法的 $\le r$ 且最大的数，检查其是否 $\ge l$ 即可。

时间复杂度 $\mathcal{O}(T\log_2 r)$。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int T; cin>>T;
	while(T--){
		long long l,r,ans=0;
		scanf("%lld%lld",&l,&r);
		for(int i=0;i<=30;i++){
			//二进制下第i位 
			long long y;
			if(l&(1ll<<i)) y=l;//l的第i位二进制为1 
			//if((l>>i)&1)
			else{//l的第i位二进制为0 
				y=(l|(1ll<<i));
				for(int j=0;j<i;j++)
					if(y&(1ll<<j)) y^=(1ll<<j);
			}
			if(y<=r) ans|=(1<<i);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
/*
位运算
拆位角度 
每一位分别去进行考虑
第0位为1的数在[l,r]内有没有出现过 
第1位为1的数在[l,r]内有没有出现过 
第2位为1的数在[l,r]内有没有出现过 

[l,r]有没有一个数，它的二进制下第x位为1
找到大于等于l的第一个二进制下第x位为1的数 y
y<=r说明存在，否则不存在 
1.l的第x位为1，那么y=l
2.l的第x位不为1,那么y=? 
把l的第x位改成1,0到x-1位都改成0,这个数就是y

位运算->每一位是独立的
每一位都拆开来就从2^30可能变成2种可能 
 
 


*/

T3

20 分

暴力搜索并比较字典序即可。

40 分

显然最长的子序列的长度就是数字种类数。

有一个非常显然的暴力，看选择了一个数后能否取到答案的最大值，如果能取到说明这个数可以选，否则不行，每次在能选的数里面选最大/最小的那一个，暴力实现的话是 $\mathcal{O}(n^3)$。

80 分

考虑优化上述暴力，注意到 check 一个数能不能选就是看一个后缀的数字种类数，这个是容易维护的，可以做到 $\mathcal{O}(n^2)$。

正解

注意到取到答案的最大值的位置组成了一个前缀。

设 $ed_x$ 表示 $x$ 出现的最后一个位置，那么 $1\sim \min_{x\in S}ed_x$ 这个前缀都能取到最大值，这是显然的。

那么就好做了，用 $set$ 维护 $ed_x$ 组成的集合，每次取出最小的一个，每次会询问一个区间 $[l,r]$ 的最小或最大值，因为左右端点右移，可以利用单调队列优化。

#include <bits/stdc++.h>

using namespace std;

int main() {
    freopen("subsequence.in", "r", stdin);
    freopen("subsequence.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int tt = 1;
    while (tt--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            a[i]--;
        }
        vector<int> l(n + 1, INT_MAX);
        for (int i = 0; i < n; i++) l[a[i]] = i;
        priority_queue<int, vector<int>, greater<int>> q(l.begin(), l.end());
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> q1, q2;
        vector<bool> vis(n + 1, false);
        for (int i = 0; i <= q.top(); i++) {
            q1.push({ -a[i], i });
            q2.push({ a[i], i });
        }
        vector<int> ans;
        int i = 0;
        while (!q2.empty()) {
            auto t = (ans.size() % 2 == 0 ? q1.top() : q2.top());
            int x = t[0], pos = t[1];
            if (ans.size() % 2 == 0) {
                q1.pop();
                x *= -1;
            } else {
                q2.pop();
            }
            ans.emplace_back(x);
            i = pos + 1, vis[x] = true;
            while ((q.top() != INT_MAX) && vis[a[q.top()]]) {
                int j = q.top();
                q.pop();
                for (int k = j + 1; k <= min(q.top(), n - 1); k++) {
                    q1.push({ -a[k], k });
                    q2.push({ a[k], k });
                }
            }
            while (!q1.empty() && (vis[-q1.top()[0]] || q1.top()[1] < i)) q1.pop();
            while (!q2.empty() && (vis[q2.top()[0]] || q2.top()[1] < i)) q2.pop();
        }
        cout << ans.size() << '\n';
        for (auto x : ans) cout << x + 1 << ' ';
        cout << '\n';
    }
    return 0;
}
/*
序列长度为不同元素的个数
字典序->最小化 
一定是逐位确定,贪心的角度确定 
第一位填入最大的数
n,________ 我们去尝试找一找是否存在一个好的序列 
n-1,________
n-2,________
n-2,1,________
n-2,2,________
n-2,3,________
n-2,3,n,________
n-2,3,n-1,______
填出一个前缀，找一找是否有一个序列它的前缀刚好是这样
n-2,3,n-1,______
找到整个序列中第一个大小为n-2的位置假设是i
然后我们在i开始继续找第一个大小为3的位置假设是j
然后我们在j开始继续找第一个大小为n-1的位置假设是k
这个序列一定是每个元素互不相同的
[k+1,n] 判定一下这个区间是否有剩下的我没有选的元素 

每一位我都要从1枚举到n或者从n枚举到1逐位确定
每一位都要枚举O(n)次，然后一共有O(n)个位
一共要判定O(n^2) O(n)   ->O(n^3)


O(n^2)
STL
一开始把所有元素出现的最后一个位置插入到 priority_queue
有没有出现过的数的最后一个位置最开头的那一个
取所有位置的最小值 
我们每次找到priority_queue 里最小的一个元素x这个位置 
判定一下a[x]是否已经在序列里出现过了
如果出现过了说明a[x]已经出现了，x从优先队列里删除，继续找下一个x
x就是最靠前的那一个 

加入元素
找到整个集合内的最大值/最小值
删掉最大值/最小值 

每次都问一个区间[l,r]中的最小值/最大值
l端点一直在右移，r端点也一直在右移
优先队列/单调队列O(n) STL O(nlogn)

我们假设把所有没有出现过的数的最后一个位置
插入到一个priority_queue
这个队列只会删除，不会增加元素，并且我们只关心最靠前的那一个
每次找优先队列的开头的一个元素x
如果x的数值已经出现过了，我们就把x弹出继续找优先里的元素
说明x是所有没有出现过的数的最后一个位置
*/

T4

20 分

暴力搜索即可。

40 分

需要挖掘一些性质，注意到可以把 $a$ 分成若干极长子段，每段的元素都相同。

容易知道，每段的元素是什么并不重要，只要知道划分方式就能推出唯一的 $b$。

比较特殊的情况是除了开头的段与结尾的段，如果有长度为 $2$ 的段，其等价于两个长度为 $1$ 的段，对应的 $b$ 都是 1 1，于是直接钦定除了开头和结尾不能出现长度为 $2$ 的段。

考虑直接 dp，$dp_{i,j}$ 表示到了 $i$ 划分出了 $j$ 段，这样是 $\mathcal{O}(n^3)$。

60 分

注意到划分出 $>k$ 段的方案是等价的，因为只要求 $1\sim k$ 在 $a$ 中都至少出现了一次。

所以第二位只需要 dp 到 $k+1$，这样是 $\mathcal{O}(n^2 k)$。

正解

注意到转移是标准的求一个区间的和，前缀和优化即可。时间复杂度 $\mathcal{O}(nk)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7,K=15,p=998244353;
int n,k,f[N][K],g[N][K];
int add(int a,int b){
	if(a+b>=p) return a+b-p; return a+b;
}
int dec(int a,int b){
	if(a-b<0) return a-b+p; return a-b;
}
inline void solve(){
	cin>>n>>k;
	f[0][0]=g[0][0]=1;
	for(int i=1;i<=n;i++){
		g[i][0]=1;
		for(int j=1;j<=k;j++){
			f[i][j]=g[i-1][j-1];
			if(i>2&&i!=n)f[i][j]=dec(f[i][j],f[i-2][j-1]);
			g[i][j]=add(g[i-1][j],f[i][j]);
		}
		f[i][k+1]=add(g[i-1][k],g[i-1][k+1]);
		if(i>2&&i!=n)f[i][k+1]=dec(f[i][k+1],add(f[i-2][k],f[i-2][k+1]));
		g[i][k+1]=add(g[i-1][k+1],f[i][k+1]); 
	}
	cout<<add(f[n][k],f[n][k+1])<<endl;
} 
signed main(){
	solve();
	return 0;
}
/*
DP
找充要条件 
给你一个序列b，怎么判定它是否是一个合法的序列 
a=[1,1,1,1,2,3]
b=[4,3,2,1,1,1]
最靠近左侧有x个一模一样的数
b=[x,x-1,x-2,x-3,...,1, 
最靠近右侧有x个一模一样的数
b=             1,...,x-2,x-1,x]
在中间有x个一模一样的数
a=[1,2,2,2,2,3]
b=[1,1,2,2,1,1]
2,2,2 在中间[1,2,1]
2,2  [1,1] [1][1]
2  [1]
2,2,2,2  [1,2,2,1]
2,2,2,2,2  [1,2,3,2,1]
2,2,2,2,2,2 [1,2,3,3,2,1]

a=[3,3,3,2,2,2,2,2,1,1,1]
b=[3,2,1,1,2,3,2,1,1,2,3]
所有的区间划分成三种，第一种是最左侧，第二种是最右侧，第三种是中间
甚至可以唯一划分
[|3,2,1|1,2,3,2,1|1,2,2,1|1,2,3]
 [1,1]  不知道是两个一样的数，还是两个不同的数 
给你一个序列b
除去连续好几个[1]这种情况以外，我们可以知道这个序列的唯一划分 
一共有7段
[3,2,1|1,2,2,1|1,2,3,2,1|1,2,2,1|1,2,3,2,1|1,2,2,1|1,2,3]
最终的段数一定是大于等于k的
每段肯定是相同的数， 
从这个角度，段数肯定越多越好
[1,1,1,1,1,] 肯定是划分成[1][1][1][1][1][1]是最好的 

k=5,一共有7段
1,2,3,4,5,1,2 
贪心的角度，因为长度为2的区间和2个1没有办法区分，其他都可以区分
dp[i][j]表示前i个数划分成了j个区间的方案数
开头的x个数是可以区分的
开头是1个数[1]
开头是2个数[2,1]
开头是3个数[3,2,1]
初始化dp[i][1]=1 

dp[i][j]->dp[i+1][j+1] //放了一个长度为1的区间
dp[i][j]->dp[i+3][j+1] //放了一个长度为3的区间
最后一段的时候
dp[i][j] -> dp[n][j+1]
最终答案就是所有j>=k的所有dp[i][j]之和
k=10,j=12 可以和11取个min
j:0,1,2,...,k+1 
->前缀和优化 

dp[i][j]<-S[i-1][j-1],dp[i-1][j-1]+dp[i-2][j-1]dp[i-3][j-1],dp[i-4][j-1],dp[i-5][j-1]
-dp[i-2][j-1]
 
 b的形态
 [1][1]
 [1,1] 

*/