2025“钉耙编程”中国大学生算法设计暑期联赛（3） · znzryb
## 1008—**01环**
赛时最后靠AI找到了一个hack数据
```cpp
hack:
1
10
1001010110
ans: 2
```
就是这个其他时候，交换都是单向的，只有一个选择，但是第一个，交换有两个选择，就都试一下。
```cpp
ll cal(string &S,char ch){
string origin=S;
S+=S[0];
S+=S[1];
ll ans=0,res=INF;
char chh='0'+((ch-'0')^1);
FOR(i,0,N-1){
char tar= i%2==0?ch:chh;
if(S[i]==tar){
continue;
}
if(i==0){
if(S[N-1]==tar){
swap(S[0],S[N-1]);
S[N]=S[0];
++ans;
continue;
}
}
if(S[i+1]==tar){
swap(S[i],S[i+1]);
if(i==0){
swap(S[N],S[N+1]);
}
ans++;
}else{
S[i]='0'+((S[i]-'0')^1);
if(i==0){
S[N]=S[0];
}
ans++;
}
}
S=origin; // 跑第二遍
res=ans;ans=0;
FOR(i,0,N-1){
char tar= i%2==0?ch:chh;
if(S[i]==tar){
continue;
}
if(S[i+1]==tar){
swap(S[i],S[i+1]);
if(i==0){
swap(S[N],S[N+1]);
}
ans++;
}else{
S[i]='0'+((S[i]-'0')^1);
if(i==0){
S[N]=S[0];
}
ans++;
}
}
res=min(ans,res);
return res;
}
```
::: 源代码
```cpp
// Problem: 01环
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/contest/problem?cid=1174&pid=1008
// Memory Limit: 65536 MB
// Time Limit: 1000 ms
// by Gospel_rock
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
ll cal(string &S,char ch){
string origin=S;
S+=S[0];
S+=S[1];
ll ans=0,res=INF;
char chh='0'+((ch-'0')^1);
// #ifdef LOCAL
// debug(ch);debug(chh);
// #endif
FOR(i,0,N-1){
char tar= i%2==0?ch:chh;
if(S[i]==tar){
continue;
}
if(i==0){
if(S[N-1]==tar){
swap(S[0],S[N-1]);
S[N]=S[0];
++ans;
continue;
}
}
if(S[i+1]==tar){
swap(S[i],S[i+1]);
if(i==0){
swap(S[N],S[N+1]);
}
ans++;
}else{
S[i]='0'+((S[i]-'0')^1);
if(i==0){
S[N]=S[0];
}
ans++;
}
}
S=origin;
res=ans;ans=0;
FOR(i,0,N-1){
char tar= i%2==0?ch:chh;
if(S[i]==tar){
continue;
}
if(S[i+1]==tar){
swap(S[i],S[i+1]);
if(i==0){
swap(S[N],S[N+1]);
}
ans++;
}else{
S[i]='0'+((S[i]-'0')^1);
if(i==0){
S[N]=S[0];
}
ans++;
}
}
res=min(ans,res);
return res;
}
inline void __(){
string S;
cin>>N;
cin>>S;
string S1=S;
ll ans=cal(S,'1'),anss=cal(S1,'0');
#ifdef LOCAL
debug(ans);debug(anss);
debug(S);
debug(S1);
#endif
cout<<min(ans,anss)<<"\n";
}
/*
hack:
1
10
1001010110
ans: 2
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=18476
*/
```
:::
## 1002**小抹爱锻炼**
[https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=817](https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=817)
赛时一发就过了。队友的思路，我的代码。
::: 源代码
```cpp
// Problem: 小抹爱锻炼
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/contest/problem?cid=1174&pid=1002
// Memory Limit: 65536 MB
// Time Limit: 1000 ms
// by Gospel_rock
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,B[MAXN],C[MAXN];
ll Sumb[MAXN],Mxb[MAXN],Mnc[MAXN];
inline void __();
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
inline void __(){
cin>>N>>M;
FOR(i,1,N){
cin>>B[i];
}
FOR(i,1,N){
Mxb[i]=max(Mxb[i-1],B[i]);
}
FOR(i,1,N){
cin>>C[i];
}
Mnc[N+1]=INF;
ROF(i,N,1){
Mnc[i]=min(Mnc[i+1],C[i]);
}
FOR(i,1,N){
if(Mxb[i]>Mnc[i]){
cout<<"NO\n";
return;
}
}
ll sumb=0,sumc=0;
FOR(i,1,N){
sumb+=Mxb[i];
}
FOR(i,1,N){
sumc+=Mnc[i];
}
if(M>=sumb && M<=sumc){
cout<<"YES\n";
return;
}
cout<<"NO\n";
}
/*
AC
14:50
https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=817
*/
```
:::
## 1012核心共振
切比雪夫距离与曼哈顿距离转化+前缀和+队友的公式。
因为有个地方溢出了，WA了一发，改了那个地方就A了。
::: 源代码
```cpp
// Problem: 核心共振
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/contest/problem?cid=1174&pid=1012
// Memory Limit: 65536 MB
// Time Limit: 2000 ms
// by Gospel_rock
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>; using vtll = vector<tll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
// tll xya[MAXN];
ll Sumx[MAXN],Sumy[MAXN];
inline void __();
ll binpow(ll a,ll k){ // 迭代快速幂
ll res=1;
a%=mod; // 防止a*a溢出
while(k>0){
if((k&1)==1) res=a*res%mod;
a=a*a%mod;
k>>=1;
}
return res;
}
bool cmp(const tll &a,const tll &b){
return get<1>(a) > get<1>(b);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
inline void __(){
cin>>N;
ll inv2=binpow(2,mod-2);
vtll xya;
FOR(i,1,N){
ll x,y,a;
cin>>x>>y>>a;
xya.EB((x+y),(x-y),a);
// xya[i]={(x+y),(x-y),a};
}
vtll xxya=xya,yyxa=xya;
sort(all(xxya),greater<>() );
sort(all(yyxa),cmp);
FOR(i,1,N){
Sumx[i]=Sumx[i-1]+get<0>(xxya[i-1]);
}
FOR(i,1,N){
Sumy[i]=Sumy[i-1]+get<1>(yyxa[i-1]);
}
ll ans=0;
// #ifdef LOCAL
// FOR(i,0,SZ(xxya)-1){
// cerr<<get<0>(xxya[i])<<" ";
// }
// cend;
// FOR(i,1,N){
// cerr<<Sumx[i]<<" ";
// }
// cend;
// FOR(i,1,N){
// cerr<<Sumy[i]<<" ";
// }
// cend;
// #endif
FOR(i,0,N-1){
auto [x,y,a]=xya[i];
ll xid=lower_bound(all(xxya),xya[i],greater<>())-xxya.begin()+1;
ll yid=lower_bound(all(yyxa),xya[i],cmp)-yyxa.begin()+1;
ll lans=(Sumx[xid-1]-x*(xid-1))%mod+(Sumy[yid-1]-y*(yid-1))%mod+
(x*(N-xid)-(Sumx[N]-Sumx[xid]))%mod+(y*(N-yid)-
(Sumy[N]-Sumy[yid]))%mod;
lans%=mod;
// #ifdef LOCAL
// debug(xid);debug(yid);
// debug(lans);
// #endif
lans*=a;lans%=mod;
lans*=inv2;lans%=mod;
ans+=lans;ans%=mod;
}
// ans*=2;
ans%=mod;if(ans<0) ans+=mod;
cout<<ans<<"\n";
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=11488
*/
```
:::
## **1007性质不同的数字**
其实还好，没有想象中那么神秘，那么这道题目其实是在问不同的区间覆盖情况有几种，那么实际上我们就差分（异或差分）+离散化就行了。
注意这里不能简单+1（下方的代码是对的）（简单的+1就是查lr[i].SE的idx，然后加的地方直接就是idx+1，这个是不行的，我们不能默认这两个区间是相交的）
```cpp
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vll diff(SZ(li)+5,0);
FOR(i,1,N){
ll l=lower_bound(all(li),lr[i].FI)-li.begin();
ll r=lower_bound(all(li),lr[i].SE+1)-li.begin();
l++,r++;
ll rnd=rng();
diff[l]^=rnd;
diff[r]^=rnd;
}
vll Sum(SZ(li)+5,0);
FOR(i,1,SZ(li)+2){
Sum[i]=Sum[i-1]^diff[i];
}
set<ll> st;
FOR(i,1,SZ(li)+2){
st.insert(Sum[i]);
}
cout<<SZ(st)<<"\n";
```
::: 源代码
```cpp
// Problem: 性质不同的数字
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/contest/problem?cid=1174&pid=1007
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
// by Gospel_rock
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
inline void __(){
cin>>N;
vpll lr(N+5);
vll li;
FOR(i,1,N){
cin>>lr[i].FI>>lr[i].SE;
li.pb(lr[i].FI),li.pb(lr[i].SE),li.pb(lr[i].SE+1);
}
if(N==0){
cout<<1<<"\n";
return;
}
sort(all(li));
li.resize(unique(all(li))-li.begin());
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vll diff(SZ(li)+5,0);
FOR(i,1,N){
ll l=lower_bound(all(li),lr[i].FI)-li.begin();
ll r=lower_bound(all(li),lr[i].SE+1)-li.begin();
l++,r++;
ll rnd=rng();
diff[l]^=rnd;
diff[r]^=rnd;
}
vll Sum(SZ(li)+5,0);
FOR(i,1,SZ(li)+2){
Sum[i]=Sum[i-1]^diff[i];
}
set<ll> st;
FOR(i,1,SZ(li)+2){
st.insert(Sum[i]);
}
cout<<SZ(st)<<"\n";
}
/*
1
2
1 3
5 6
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=20227
*/
```
:::
## 1004**三带一**
$sum为牌数总和，ans为答案，rem为剩余牌数$。
$rem=sum-3\times ans$ 那么剩余的牌的数量一定大于 $rem\ge ans$
$t_i\le rem-(a_i-3t_i)\ \ \Rightarrow \ \ a_i-rem\le 2t_i$
那么第一个式子没什么难的，剩余的这个rem‘B’肯定要比你的三元组多呀。然后移项一下，这个式子摇身一变，变为了$t_i$的下界了，这个好像也挺简单的~~（就是赛时想不到）~~。
然后向上取整除法的写法需要特判<0的情况，因为众所周知，C++的/是向0取整的，
```cpp
inline ll chu(ll x){
if(x<0) return x/2;
if(x%2==0) return x/2;
return x/2+1;
}
```
check函数的写法，这个low怎么说呢，也没啥物理意义，就是纯数学推出来的式子，你就说是不是下界吧（）。
```cpp
auto check=[&](ll ans)->bool{
// 剩余多少个AAAB中的‘B’
ll rem=sum-3*ans;
if(rem<ans){ // 剩余的‘B’都不够，巧妇难为无米之炊
return false;
}
ll high=0,slow=0;
FOR(i,1,13){
ll lhigh=A[i]/3;
ll low=chu(A[i]-rem);
if(low>lhigh){
return false;
}
high+=lhigh;
slow+=max(0ll,low);
}
if(high>=ans && ans>=slow){
return true;
}
return false;
};
```
[https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=22887](https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=22887)
::: 源代码
```cpp
// Problem: 三带一
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/contest/problem?cid=1174&pid=1004
// Memory Limit: 262144 MB
// Time Limit: 1000 ms
// by Gospel_rock
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,A[25];
inline void __();
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
不用想那么复杂，可以先全部当3，然后再看怎么办
看了半天终于算是看懂了
t_i\le rem-(a_i-3t_i) \Rightarrow a_i-rem\le 2t_i
*/
inline ll chu(ll x){
if(x<0) return x/2;
if(x%2==0) return x/2;
return x/2+1;
}
inline void __(){
ll sum=0;
FOR(i,1,13){
cin>>A[i];
sum+=A[i];
}
auto check=[&](ll ans)->bool{
// 剩余多少个AAAB中的‘B’
ll rem=sum-3*ans;
if(rem<ans){ // 剩余的‘B’都不够，巧妇难为无米之炊
return false;
}
ll high=0,slow=0;
FOR(i,1,13){
ll lhigh=A[i]/3;
ll low=chu(A[i]-rem);
if(low>lhigh){
return false;
}
high+=lhigh;
slow+=max(0ll,low);
}
if(high>=ans && ans>=slow){
return true;
}
return false;
};
ll l=0,r=sum/4;
while(l<r){
ll mid=l+r+1>>1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
cout<<l<<"\n";
}
/*
*/
```
:::
## **1009线段染色**
[https://acm.hdu.edu.cn/contest/problem?cid=1174&pid=1009](https://acm.hdu.edu.cn/contest/problem?cid=1174&pid=1009)
又是沟槽的概率题目。
感觉不是我能碰瓷的题目，之后有兴趣了再来看吧。
[https://grok.com/chat/dc6a06d2-50d6-4bb8-a88b-87a1c553307d](https://grok.com/chat/dc6a06d2-50d6-4bb8-a88b-87a1c553307d)
::: AI代码
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007; // 定义模数 10^9 + 7
const int MAXN = 200010; // 定义最大 n 值
// 计算 a^b % mod 的快速幂函数
ll powmod(ll a, ll b, ll mod) {
ll res = 1;
a %= mod;
for (; b; b >>= 1) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}
// Fenwick Tree (Binary Indexed Tree) 类，用于前缀和查询与更新
class Fenwick {
public:
vector<ll> tree; // 树数组
int n; // 大小
Fenwick(int _n) : n(_n), tree(_n + 2, 0) {} // 构造函数
// 更新索引 idx 处的值，增加 val
void update(int idx, ll val) {
idx++;
while (idx <= n + 1) {
tree[idx] = (tree[idx] + val) % MOD;
idx += idx & -idx;
}
}
// 查询前 idx 个元素的和
ll query(int idx) {
idx++;
ll sum = 0;
while (idx > 0) {
sum = (sum + tree[idx]) % MOD;
idx -= idx & -idx;
}
return sum;
}
// 查询 [l, r] 范围的和
ll query(int l, int r) {
if (l > r) return 0;
return (query(r) - query(l - 1) + MOD) % MOD;
}
};
// 线段树类，用于查询范围最大值
class SegMax {
public:
vector<int> tree; // 树数组
int n; // 大小
SegMax(int _n) : n(_n), tree(4 * _n + 10, 0) {} // 构造函数
// 构建线段树
void build(int node, int start, int end, const vector<int>& a) {
if (start == end) {
tree[node] = a[start];
return;
}
int mid = (start + end) / 2;
build(2 * node, start, mid, a);
build(2 * node + 1, mid + 1, end, a);
tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
// 查询 [l, r] 范围的最大值
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return -1;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
int p1 = query(2 * node, start, mid, l, r);
int p2 = query(2 * node + 1, mid + 1, end, l, r);
if (p1 == -1) return p2;
if (p2 == -1) return p1;
return max(p1, p2);
}
};
int main() {
ios::sync_with_stdio(false); // 加速输入输出
cin.tie(0); // 解除 cin 和 cout 的绑定
int t;
cin >> t; // 阅读测试用例数
for (int cas = 0; cas < t; ++cas) { // 循环处理每个测试用例
int n, m;
cin >> n >> m; // 阅读 n 和 m
vector<int> a(n + 1); // 存储每个点的 a_i
for (int i = 1; i <= n; ++i) cin >> a[i]; // 阅读 a 序列
SegMax sm(n); // 创建线段树实例
sm.build(1, 1, n, a); // 构建线段树
vector<int> M(n + 1, -1); // M[r] 存储以 r 为右端点的线段的最大左端点
int maxl = 0; // 所有线段的最大左端点
bool iszero = false; // 标记是否有线段无法被染色（所有点 a_i=0）
for (int i = 0; i < m; ++i) { // 阅读 m 条线段
int l, r;
cin >> l >> r;
M[r] = max(M[r], l); // 更新 M[r]
maxl = max(maxl, l); // 更新 maxl
if (sm.query(1, 1, n, l, r) == 0) iszero = true; // 检查线段是否全为 0
}
if (iszero) { // 如果有线段无法染色，输出 0
cout << 0 << '\n';
continue;
}
vector<int> last_forced(n + 1, 0); // last_forced[i] 是 1 到 i 的最后一个 a_k=10 的位置
for (int i = 1; i <= n; ++i) {
if (a[i] == 10) last_forced[i] = i;
else last_forced[i] = last_forced[i - 1];
}
vector<ll> Q(n + 1, 1); // Q[i] 是从 last_forced[i]+1 到 i 的 (10 - a_k) 乘积
Q[0] = 1; // 初始化 Q[0]
for (int i = 1; i <= n; ++i) {
if (a[i] == 10) Q[i] = 1; // 如果 a[i]=10，重置为 1
else Q[i] = Q[i - 1] * (10LL - a[i]) % MOD; // 否则累乘 (10 - a[i])
}
vector<ll> DP(n + 1, 0); // DP[i] 是以 i 为最后一个染色点的有效配置权重
DP[0] = 1; // 初始化 DP[0]=1
Fenwick ft(n); // 创建 Fenwick Tree 实例
ll val = DP[0] * powmod(Q[0], MOD - 2, MOD) % MOD; // 计算 DP[0]/Q[0]
ft.update(0, val); // 更新到 Fenwick Tree
ll run = -1; // run 是当前的最大左端点约束
for (int i = 1; i <= n; ++i) { // 循环计算每个 i 的 DP
run = max(run, (ll)M[i - 1]); // 更新 run
int mj_seg = max(0LL, run); // 线段约束的最小 j
int mj = max(mj_seg, last_forced[i - 1]); // 总体最小 j（考虑强制点）
ll qsum = ft.query(mj, i - 1); // 查询 sum (DP[j]/Q[j])
ll temp = qsum * Q[i - 1] % MOD; // 乘以 Q[i-1] 得到 sum DP[j] * prod(j+1 to i-1)
DP[i] = (ll)a[i] * temp % MOD; // 计算 DP[i]
val = DP[i] * powmod(Q[i], MOD - 2, MOD) % MOD; // 计算 DP[i]/Q[i]
ft.update(i, val); // 更新到 Fenwick Tree
}
vector<ll> S(n + 2, 1); // S[i] 是从 i 到 n 的 (10 - a_k) 乘积
for (int i = n; i >= 1; --i) {
S[i] = S[i + 1] * (10LL - a[i]) % MOD; // 后缀乘积
}
ll numer = 0; // 分子：所有有效配置的权重
for (int i = 0; i <= n; ++i) {
if (i >= maxl) { // 如果 i >= maxl，可以作为最后一个染色点
numer = (numer + DP[i] * S[i + 1] % MOD) % MOD; // 累加 DP[i] * S[i+1]
}
}
ll inv10 = powmod(10LL, MOD - 2, MOD); // 10 的逆元
ll inv10n = powmod(inv10, n, MOD); // 10^n 的逆元
ll ans = numer * inv10n % MOD; // 最终答案 = numer / 10^n % MOD
cout << ans << '\n'; // 输出答案
}
return 0;
}
```
:::
::: 源代码
```cpp
```
:::