思维：找最小值和次小值
void solve(){
int n = 0;
cin>>n;
vector<int>arr(n+1);
int mn1 = 1e9+8,mn2 = 1e9+8,num1 = 0,num2 = 0;
//统计最小和次小。
for(int i = 1;i<=n;i++){
cin>>arr[i];
if(arr[i]<=mn1){
if(arr[i]<mn1){
mn2 = mn1;
num2 = num1;
mn1 = arr[i];
num1 = 1;
}else {
num1++;
}
}else if(arr[i]<=mn2){
if(arr[i]<mn2){
mn2 = arr[i];
num2 = 1;
}else{
num2++;
}
}
}
//分类
if(num1==1&&num2==1){
cout<<n-1<<"\n";
}else if(num1>=2){
cout<<n-num1<<"\n";
}else if(num1==1&&num2>1){
int dex = 0;
for(int i = 1;i<=n;i++){
if(arr[i]==mn1){
dex = i;
break;
}
}
int numl = 0,numr = 0;
for(int i = 1;i<=dex;i++){
if(arr[i]==mn2){
numl++;
}
}
for(int i = dex;i<=n;i++){
if(arr[i]==mn2){
numr++;
}
}
cout<<n-1-min(numl,numr)<<"\n";
}
}
//贡献计算法：
考虑到区间左右对称，那么我们可以先只处理一边，比如
先处理所有右区间的贡献，那么先预处理pre（min），考虑从一个开始，
当但前a【i】>pre[i-1]时候，放进队列。此时队列的区间的贡献就是队列的长度
但是当a【i】<=pre[i-1]的时候就不放入；因为左边具有相对最大值
当pre【i-1】>=pq.top()的时候，就要pop更新
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int pre[N], sur[N];
int lg[N], rg[N];
priority_queue<int, vector<int>, greater<int>> lq, rq;
int a[N];
int n;
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
pre[1] = a[1];
for (int i = 2; i <= n; i++) pre[i] = min(pre[i-1], a[i]);
sur[n] = a[n];
for (int i = n-1; i >= 1; i--) sur[i] = min(sur[i+1], a[i]);
for (int i = 1; i < n; i++) {
if (a[i] > sur[i+1]) {
lq.push(a[i]);
}
while (!lq.empty() && lq.top() <= sur[i+1]) {
lq.pop();
}
lg[i] = lq.size();
}
for (int i = n; i > 1; i--) {
if (a[i] > pre[i-1]) {
rq.push(a[i]);
}
while (!rq.empty() && rq.top() <= pre[i-1]) {
rq.pop();
}
rg[i] = rq.size();
}
int mmax = 0;
for (int i = 1; i < n; i++) {
mmax = max(mmax, lg[i] + rg[i+1]);
}
cout << mmax << endl;
return 0;
}
//简单的背包状态dp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e3+10;
int a[N];
int n,k;
bool dp[N][N];
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0][0]=true;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
if(j+a[i]+a[i]<=k) dp[i][j+a[i]*2]|=dp[i][j];
if(j+a[i]<=k) dp[i][j+a[i]]|=dp[i-1][j];
}
}
if(dp[n][k]){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
// int t=6;
// while(t--){
// int n;
// cin >> n;
// string s;
//
// for (int i = 1; i <= n; i++) {
// s += char(i + '0');
// }
//
// int ans = 0;
//
// do {
// for (int i = 0; i < n - 3; i++) {
// for (int j = i + 1; j < n - 1; j++) {
//
// int a, b, c;
// a = stoi(s.substr(0, i + 1));
// b = stoi(s.substr(i + 1, j - i));
// c = stoi(s.substr(j+1));
// // cout<<a<<" "<<b<<" "<<c<<"\n";
// if (2025 ==((a + b) * c)) {ans++;}
// if (2025==((a - b) * c)) {ans++;}
// if (2025==((a + b) - c)) {ans++;}
// if (2025==((a * b) - c)) {ans++;}
// if (2025==((a * b) + c)) ans++;
// if (2025==((a * b) * c)) ans++;
// if (2025==((a + b) + c)) ans++;
// if (2025==((a - b) - c)) ans++;
// if (2025==((a - b) + c)) ans++;
//
// }
// }
// } while (next_permutation(s.begin(), s.end()));
//
// cout << ans << "\n";
//
//
// }
int n;
cin>>n;
if(n==4||n==5){
cout<<0;
}else if(n==6||n==7){
cout<<9;
}else if(n==8){
cout<<581;
}else{
cout<<4067;
}
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int pre[N], sur[N];
int lg[N], rg[N];
priority_queue<int, vector<int>, greater<int>> lq, rq;
int a[N];
int n;
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
pre[1] = a[1];
for (int i = 2; i <= n; i++) pre[i] = min(pre[i-1], a[i]);
sur[n] = a[n];
for (int i = n-1; i >= 1; i--) sur[i] = min(sur[i+1], a[i]);
for (int i = 1; i < n; i++) {
if (a[i] > sur[i+1]) {
lq.push(a[i]);
}
while (!lq.empty() && lq.top() <= sur[i+1]) {
lq.pop();
}
lg[i] = lq.size();
}
for (int i = n; i > 1; i--) {
if (a[i] > pre[i-1]) {
rq.push(a[i]);
}
while (!rq.empty() && rq.top() <= pre[i-1]) {
rq.pop();
}
rg[i] = rq.size();
}
int mmax = 0;
for (int i = 1; i < n; i++) {
mmax = max(mmax, lg[i] + rg[i+1]);
}
cout << mmax << endl;
return 0;
}
//其实就是利用前缀数组+统计
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
string s;
int n;
int pre;
int ans;
map<int,int> mp;
signed main(){
cin>>n>>s;
for(auto c:s){
if(c=='0') pre--;
else pre++;
mp[pre]++;
if(pre)
ans+=(mp[pre]-1);
else
ans+=(mp[pre]);
}
cout<<ans;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
string s;
cin >> s;
int ret = 0;
int index = 0;
while((index = s.find("2025", index)) != -1){
ret += (index + 1) * (n - index - 3);
index += 1;
}
cout << ret << "\n";
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, k;
string s;
int vis[100001];
vector<int> vc[100001];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
cin >> s;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
vc[u].emplace_back(v);
vc[v].emplace_back(u);
}
int cnt = 1;
queue<int> que;
vector<int> beibao;
int onon = 0;
for(int i = 1; i <= n; i++){
if(vis[i]) continue;
que.push(i);
int of = 0;
if(s[i-1] == '1') {
onon++;
}
else {
of++;
}
while(!que.empty()){
int pos = que.front();
que.pop();
vis[pos] = cnt;
for(auto v: vc[pos]){
if(vis[v]) continue;
vis[v] = cnt;
que.push(v);
if(s[v-1] == '1') {
onon++;
}
else {
of++;
}
}
}
beibao.push_back(of);
cnt++;
}
sort(beibao.begin(), beibao.end(), greater<int>());
int total = onon;
for(int i = 0; i < k && i < (int)beibao.size(); i++){
total += beibao[i];
}
if(k >= (int)beibao.size()){
total = n;
}
cout << total << "\n";
}
//并查集版本
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int p[N],s[N],n,m,k,cnt;
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
void unite(int x,int y){
x=find(x),y=find(y);
if(x!=y) p[x]=y,s[y]+=s[x];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>k;
iota(p,p+n+1,0); // 初始化父节点
fill(s,s+n+1,1); // 初始化大小
string ss;
cin>>ss;
for(int i=0;i<n;i++)
if(ss[i]=='1') s[i+1]=0,cnt++;
while(m--){
int u,v; cin>>u>>v;
unite(u,v);
}
vector<int> vec;
for(int i=1;i<=n;i++)
if(p[i]==i) vec.push_back(s[i]);
sort(vec.rbegin(),vec.rend());
int add=0;
for(int i=0;i<k && i<vec.size();i++)
add += vec[i];
cout<<min(cnt+add,n)<<'\n';
}
1根据adj【i】.size()求出度数，度数1是根或者叶
2利用bfs的松弛操作求每个点到叶子节点的距离
3利用大到小前缀计算来求出贡献
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int n;
vector<int> adj[N];
int de[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
int u, v;
for(int i = 1; i < n; i++){
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
memset(de, 0x3f, sizeof de);
int cnt=0;
queue<int> que;
for(int i = 1; i <= n; i++){
if(adj[i].size() == 1){
de[i] = 1;
cnt++;
que.push(i);
}
}
while(!que.empty()){
int p = que.front();
que.pop();
for(auto son : adj[p]){
if(de[son] > de[p] + 1){
de[son] = de[p] + 1;
que.push(son);
}
}
}
map<int,int> mp;
for(int i = 1; i <= n; i++){
mp[de[i]]++;
}
int sum = 0;
int ans = 0;
for(auto it = mp.rbegin(); it != mp.rend(); it++){
sum += it->second;
ans += sum*it->second;
}
cout << ans-cnt*cnt;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
// 线段树节点结构体 (简化版，移除了 tag)
struct Node {
int l, r; // 管理区间
int sum; // 区间内元素总个数
} tr[N * 4]; // 线段树数组
vector<int> all_values; // 离散化数值集合
map<int, int> val2idx; // 数值到索引的映射
// 辅助函数：获取左右子节点索引
int ls(int u) { return u << 1; } // u*2
int rs(int u) { return u << 1 | 1; } // u*2+1
// 合并子树信息（仅需合并 sum）
void pushup(int u) {
tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;
}
// 构建线段树（无需初始化 tag）
void build(int u, int l, int r) {
tr[u] = {l, r, 0}; // sum 初始化为 0
if (l == r) return;
int mid = (l + r) >> 1;
build(ls(u), l, mid);
build(rs(u), mid + 1, r);
}
// 单点更新函数（无需处理 tag 和区间）
void update(int u, int pos) {
if (tr[u].l == tr[u].r) { // 找到目标位置
tr[u].sum += 1; // 计数 +1
return;
}
// 递归查找目标位置
int mid = (tr[u].l + tr[u].r) >> 1;
if (pos <= mid) update(ls(u), pos);
else update(rs(u), pos);
pushup(u); // 更新父节点 sum
}
// 区间查询函数（无需 pushdown）
int query(int u, int l, int r) {
if (l > r) return 0;
if (l <= tr[u].l && tr[u].r <= r)
return tr[u].sum;
int mid = (tr[u].l + tr[u].r) >> 1;
int res = 0;
if (l <= mid) res += query(ls(u), l, r);
if (r > mid) res += query(rs(u), l, r);
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
// 输入处理
int n, q;
cin >> n >> q;
vector<int> a(n), queries(q);
for (int& x : a) cin >> x;
for (int& x : queries) cin >> x;
// 离散化处理
all_values = a;
all_values.insert(all_values.end(), queries.begin(), queries.end());
sort(all_values.begin(), all_values.end());
all_values.erase(unique(all_values.begin(), all_values.end()), all_values.end());
for (int i = 0; i < all_values.size(); ++i)
val2idx[all_values[i]] = i + 1; // 索引从 1 开始
// 构建线段树
int m = all_values.size();
build(1, 1, m);
// 插入初始数组
for (int x : a) {
int pos = val2idx[x];
update(1, pos);
}
// 处理查询
for (int x : queries) {
int pos = val2idx[x];
int sum_less = query(1, 1, pos - 1);
int cnt = query(1, pos, pos);
cout << sum_less + 1 << " " << sum_less + cnt + 1 << "\n";
update(1, pos); // 插入新元素
}
return 0;
}
区间修改版本
#include <bits/stdc++.h>
using namespace std;
#define int long long // 定义宏简化长整型声明
const int N = 2e5 + 10; // 总数据量两倍空间
// 线段树节点结构体
struct Node {
int l, r; // 当前节点管理的区间范围[l, r]
int sum; // 区间内元素总个数
int tag; // 懒标记（用于区间操作的延迟更新）
} tr[N * 4]; // 线段树数组，4倍空间
vector<int> all_values; // 存储所有需要离散化的数值
map<int, int> val2idx; // 数值到离散化索引的映射表
// 获取左子节点索引
int ls(int u) { return u << 1; } // 等价于 u*2
// 获取右子节点索引
int rs(int u) { return u << 1 | 1; } // 等价于 u*2+1
// 合并左右子树信息到父节点
void pushup(int u) {
// 父节点的sum等于左右子节点的sum之和
tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;
}
// 下推懒标记到子节点
void pushdown(int u) {
if (tr[u].tag) { // 仅在有标记时处理
// 更新左子节点
tr[ls(u)].tag += tr[u].tag; // 累加标记值
tr[ls(u)].sum += (tr[ls(u)].r - tr[ls(u)].l + 1) * tr[u].tag; // 更新区间总和
// 更新右子节点
tr[rs(u)].tag += tr[u].tag;
tr[rs(u)].sum += (tr[rs(u)].r - tr[rs(u)].l + 1) * tr[u].tag;
tr[u].tag = 0; // 清空当前节点的标记
}
}
// 构建线段树
void build(int u, int l, int r) {
tr[u] = {l, r, 0, 0}; // 初始化节点信息
if (l == r) return; // 到达叶子节点
int mid = (l + r) >> 1; // 计算中点
build(ls(u), l, mid); // 递归构建左子树
build(rs(u), mid + 1, r); // 递归构建右子树
pushup(u); // 合并子树信息
}
/* 区间更新函数
u: 当前节点索引
l,r: 目标更新区间
d: 增量值 */
void update(int u, int l, int r, int d) {
if (l <= tr[u].l && tr[u].r <= r) { // 完全覆盖当前节点区间
tr[u].sum += (tr[u].r - tr[u].l + 1) * d; // 更新区间总和
tr[u].tag += d; // 记录懒标记
return;
}
pushdown(u); // 先下推已有标记
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid) update(ls(u), l, r, d); // 递归更新左子树
if (r > mid) update(rs(u), l, r, d); // 递归更新右子树
pushup(u); // 更新当前节点信息
}
/* 区间查询函数
返回区间[l,r]的元素总个数 */
int query(int u, int l, int r) {
if (l > r) return 0; // 无效区间处理
if (l <= tr[u].l && tr[u].r <= r) // 完全覆盖当前节点区间
return tr[u].sum;
pushdown(u); // 下推标记确保数据最新
int mid = (tr[u].l + tr[u].r) >> 1;
int res = 0;
if (l <= mid) res += query(ls(u), l, r); // 累加左子树结果
if (r > mid) res += query(rs(u), l, r); // 累加右子树结果
return res;
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步加速输入输出
cin.tie(0); // 解除cin与cout的绑定
// 输入处理
int n, q; // 初始元素个数n，查询次数q
cin >> n >> q;
vector<int> a(n), queries(q); // 初始数组和查询数组
// 读取初始数组
for (int& x : a) cin >> x;
// 读取所有查询值
for (int& x : queries) cin >> x;
// ========== 离散化处理 ==========
all_values = a; // 初始数组元素
all_values.insert(all_values.end(), queries.begin(), queries.end()); // 追加查询值
sort(all_values.begin(), all_values.end()); // 排序
// 去重（unique返回去重后的尾迭代器，erase删除重复元素）
all_values.erase(unique(all_values.begin(), all_values.end()), all_values.end());
// 建立离散化映射表（数值->连续索引）
for (int i = 0; i < all_values.size(); ++i)
val2idx[all_values[i]] = i + 1; // 索引从1开始，避免线段树处理0
// ========== 线段树初始化 ==========
int m = all_values.size(); // 离散化后的数值种类数
build(1, 1, m); // 在[1,m]区间构建线段树
// 插入初始数组元素
for (int x : a) {
int pos = val2idx[x]; // 获取离散化位置
update(1, pos, pos, 1); // 单点增加计数
}
// ========== 处理每个查询 ==========
for (int x : queries) {
int pos = val2idx[x]; // 获取当前值的离散化位置
// 查询比当前值小的元素总个数（区间[1,pos-1]）
int sum_less = query(1, 1, pos - 1);
// 查询当前值的现有数量（单点查询）
int cnt = query(1, pos, pos);
// 输出插入区间（闭区间）
cout << sum_less + 1 << " " << sum_less + cnt + 1 << "\n";
// 将当前值插入线段树（计数+1）
update(1, pos, pos, 1);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
char a[2];
bool ok = false;
int n;
cin >> n;
string s;
cin >> s;
if (n <= 3) {
cout << "YES" << endl;
return;
}
int cnt = 0;
a[0] = s[0];
a[1] = s[1];
cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] != a[i % 2]) cnt++;
}
if (cnt <= 1 && a[0] != a[1]) ok =true;
a[0] = s[2];
a[1] = s[1];
cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] != a[i % 2]) cnt++;
}
if (cnt <= 1 && a[0] != a[1]) ok = true;
a[0] = s[2];
a[1] = s[3];
cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] != a[i % 2]) cnt++;
}
if (cnt <= 1 && a[0] != a[1]) ok = true;
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
while (t--) {
solve();
}
return 0;
}
求差分后的极差最小，可修改原元素，思路就是预处理前后缀min和max。模拟每一次修改，每次修改取中，因为减少影响极差，首尾得单独枚举
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
const int N = 1e5+10;
void read(){
ios::sync_with_stdio(false);
cin.tie(0);
}
int n,k;
int a[N],b[N];
int lmax[N],rmax[N];
int lmin[N],rmin[N];
signed main(){
read();
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=2;i<=n;i++){
b[i-1]=a[i]-a[i-1];
}
if(n<=3){
cout<<"YES\n";
return 0;
}
lmin[1]=b[1];
lmax[1]=b[1];
for(int i=2;i<n;i++){
lmax[i]=max(lmax[i-1],b[i]);
lmin[i]=min(lmin[i-1],b[i]);
}
rmin[n-1]=b[n-1];
rmax[n-1]=b[n-1];
for(int i=n-2;i>=1;i--){
rmax[i]=max(rmax[i+1],b[i]);
rmin[i]=min(rmin[i+1],b[i]);
}
bool c=false;
lmin[0]=1e18;
rmin[n]=1e18;
lmax[0]=-1e18;
rmax[n]=-1e18;
//枚举中间
for(int i=2;i<n;i++){
int len1=(b[i]+b[i-1])/2;
int len2=(b[i]+b[i-1])-len1;
int mmax=max({lmax[i-2],rmax[i+1],len1,len2})-min({lmin[i-2],rmin[i+1],len1,len2});
if(mmax<=k){
c=true;
}
}
//枚举两端
if(rmax[2]-rmin[2]<=k){
c=true;
}
if(lmax[n-2]-lmin[n-2]<=k){
c=true;
}
if(c) cout<<"YES\n";
else cout<<"NO\n";
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const int INF = 1e18;
void read() {
ios::sync_with_stdio(false);
cin.tie(0);
}
string s;
int n;
int dp1[N];
int dp2[N];
int pred[N],prex[N],pres[N];
signed main() {
read();
cin>>n>>s;
s='?'+s;
for(int i=1;i<=n;i++){
if(s[i]<='Z'&&s[i]>='A'){
pred[i]=1;
}
if(s[i]<='z'&&s[i]>='a'){
prex[i]=1;
}
if(s[i]<='9'&&s[i]>='0'){
pres[i]=1;
}
pred[i]+=pred[i-1];
prex[i]+=prex[i-1];
pres[i]+=pres[i-1];
}
for(int i=8;i<=n;i++){
dp1[i]=dp1[i-1];
dp2[i]=dp2[i-1];
for(int j=8;j<=20;j++){
if(j>i) break;
int ok1=pred[i]-pred[i-j];
int ok2=prex[i]-prex[i-j];
int ok3=pres[i]-pres[i-j];
if(ok1&&ok2&&ok3){
if(dp1[i]<dp1[i-j]+1){
dp1[i]=dp1[i-j]+1;
dp2[i]=max({dp2[i],dp2[i-j]+j});
}else if(dp1[i]==dp1[i-j]+1){
dp2[i]=max({dp2[i],dp2[i-j]+j});
}
}
}
}
cout<<dp1[n]<<" "<<dp2[n];
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ls(u) (u << 1)
#define rs(u) (u << 1 | 1)
const int N = 2e5 + 10;
struct no {
int l, r;
int sum;
} tr[N * 4];
int n, q;
vector<int> alls;
vector<int> a, qs;
map<int, int> mp;
void pushup(no &u, no &l, no &r) {
u.sum = l.sum + r.sum;
}
void bd(int u, int l, int r) {
tr[u] = {l, r, 0};
if (l == r) {
return;
}
int mid = (l + r) >> 1;
bd(ls(u), l, mid);
bd(rs(u), mid + 1, r);
pushup(tr[u], tr[ls(u)], tr[rs(u)]);
}
void updata(int u, int pos, int cnts) {
if (tr[u].l == pos && tr[u].r == pos) {
tr[u].sum += cnts;
} else {
int mid = (tr[u].l + tr[u].r) >> 1;
if (pos <= mid) {
updata(ls(u), pos, cnts);
} else {
updata(rs(u), pos, cnts);
}
pushup(tr[u], tr[ls(u)], tr[rs(u)]);
}
}
int qu(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u].sum;
} else {
int mid = (tr[u].l + tr[u].r) >> 1;
int sum = 0;
if (l <= mid) {
sum += qu(ls(u), l, r);
}
if (r > mid) {
sum += qu(rs(u), l, r);
}
return sum;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
a.resize(n);
qs.resize(q);
alls.resize(n + q);
for (int i = 0; i < n; i++) {
cin >> a[i];
alls[i] = a[i];
}
for (int i = 0; i < q; i++) {
cin >> qs[i];
alls[i + n] = qs[i];
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 0; i < n + q; i++) {
mp[alls[i]] = i;
}
bd(1, 0, n + q - 1);
for (int i = 0; i < n; i++) {
int pos = lower_bound(alls.begin(), alls.end(), a[i]) - alls.begin();
updata(1, pos, 1);
}
for (int x : qs) {
int pos = lower_bound(alls.begin(), alls.end(), x) - alls.begin();
int count_less = (pos > 0) ? qu(1, 0, pos - 1) : 0;
int count_equal = qu(1, pos, pos);
int left = count_less + 1;
int right = count_less + count_equal + 1;
cout << left << " " << right << "\n";
updata(1, pos, 1);
}
}
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
ll inv[200005] = {1}; // 代表 1/i
ll inf[200005] = {1}; // 代表 1/1 * 1/2 * ... * 1/i
ll onf[200005] = {1}; // 代表 1 * 2 * ... * i
// 初始化逆元、阶乘逆元和阶乘
void Init_inv(int n) {
for (int i = 1; i <= n; i++) {
if (i == 1) {
inv[1] = 1, inf[1] = 1, onf[1] = 1;
} else {
inv[i] = (((-MOD / i) * inv[MOD % i]) % MOD + MOD) % MOD;
inf[i] = (inf[i - 1] * inv[i]) % MOD;
onf[i] = (onf[i - 1] * i) % MOD;
}
}
}
// 计算组合数 C(a, b)
ll C(ll a, ll b) {
if (a < 0 || b < 0 || a > b) return 0;
return ((onf[b] * inf[b - a]) % MOD * inf[a]) % MOD;
}
ll f(ll l, ll r, ll n, ll sum[]) {
// 可插入的空位
ll len = n - (sum[r] - sum[l - 1]) - (r - l);
if (len < 0) return 0;
return C(r-l+1,len+r-l+1);
}
int main() {
Init_inv(200000); // 初始化逆元、阶乘逆元和阶乘
ll n, m;
cin >> n >> m;
ll a[100005] = {0}; // 存储数字
ll sum[100005] = {0}; // 前缀和
ll w[10] = {3, 1, 2, 2, 4, 2, 3, 2, 3, 3}; // 数字对应的宽度
string s;
cin >> s;
for (int i = 0; i < m; i++) {
a[i + 1] = s[i] - '0'; // 将字符转换为数字
sum[i + 1] = sum[i] + w[a[i + 1]]; // 计算前缀和
}
ll res = 0;
for (int i = 0; i <= m; i++) {
ll l = 0, r = 0;
if (i == 0) {
l = 1; // 如果左边没有数字，只有一种方案
} else {
l = f(1, i, n, sum); // 计算左边的方案数
}
if (i == m) {
r = 1; // 如果右边没有数字，只有一种方案
} else {
r = f(i + 1, m, n, sum); // 计算右边的方案数
}
res = (res + l * r) % MOD; // 累加结果
}
cout << res << endl; // 输出结果
return 0;
}
