视频讲题 https://www.bilibili.com/video/BV1JS4y1C7z5
视频讲题ppt下载
jiangly 1h 9min AK实况 https://www.bilibili.com/video/BV1534y117GQ

难度预计：

easy: E H K

medium: F I C D A J

medium-hard: G B

hard: L

实际难度：

EHKFCAJIDGBL

预计ak人数：15

实际ak人数：14

写在前面的话

本场比赛本来是准备放在第一场的，因不可抗因素不得不调整到第四场。难度总体偏低，除了最后一题以外严格意义上都不是特别难，很考验大家的知识点基本功，希望赛场中没过的同学也可以多多补题，提升自己的算法能力~

level.0 E 真假签到题

对标cf难度：800

知识点：数学，记忆化搜索（划掉）

签到题。直接粘贴函数的话会超时（复杂度为 ）。但本质上函数为 ，所以输入什么就输出什么即可。

如果没看出来也没关系，可以通过找规律打表发现，或者直接套一个记忆化搜索（复杂度为 ）都可以通过。

证明：

首先该函数是：

当 时，有 成立。

假设对于所有的 有 成立。

那么对于 而言， 由于此时 ，所以一定有 且 。

于是有 。

因此根据数学归纳法，对于所有 ， 。

证毕。

参考代码（python）：

print(input())

参考代码（记忆化搜索）：

#include<bits/stdc++.h>
using namespace std;
map<long long,long long>mp;
long long f(long long x){
    if(x==1)return 1;
    if(mp[x])return mp[x];
    return mp[x]=f(x/2)+f(x/2+x%2);
}
int main(){
    long long x;
    cin>>x;
    cout<<f(x);
}

level.1 H 真真真真真签到题

对标cf难度：1000

知识点：立体几何，博弈

首先显然紫会选择中间。如果紫不选中间，那么小红选择离紫最远哪个角落一定比离中间要更远一些。

当紫选择了中间以后，小红必然选择任意一个角。

所以现在的问题变成了：已知正方体中心到顶点的距离为 ，求正方体的体积。

假设边长为，那么根据勾股定理有，所以计算出

最终输出边长的三次方即可。

建议：本题由于输出是浮点数，所以可以用pow函数。一般整数的乘方不建议用pow函数（容易出现精度问题），建议用for循环或者快速幂进行模拟。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    double x;
    cin>>x;
    x=x*2/sqrt(3);
    printf("%.7f",pow(x,3));
}

level.2 K 小红的真真假假签到题题

对标cf难度：1100

知识点：构造，位运算

本题要求构造一个数，为给定的数的倍数，并且二进制下包含的子串，并且 中'1'的数量和 中 '1'的数量不能相等。

如果没有最后一个条件，输出 即可。因为 是 的二进制后面添加一个 '0'，显然满足前两个条件。

现在有了 '1' 数量不等的限制条件，那么就不能用上面的方式构造。

一个最简单的构造方式就是，将 的二进制重复写两次。显然满足子串条件和'1'不等条件。倍数条件也很容易证明：将 的二进制写两次等价于将 后面添加一些'0'，再加上 。而第一步操作也就是乘上一个2的幂，显然一直都满足是的倍数这一条件。

参考代码（解法1）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll x;
    cin>>x;
    int i;
    for(i=0;i<=32;i++)if(1LL<<i>x)break;
    cout<<x*(1LL<<i)+x;

}

当然还有个更简单的方式：由于 的二进制一定不超过30位（因为x不大于1e9），所以直接将 后面加30个'0'之后加x也可以，这样必然不会超过 的限制。

提示：灵活使用位运算运算符可以大大减少码量哦~另外位运算的运行速度在计算机底层是最快的，多用位运算可以减少代码的运行常数。

一些常用的位运算技巧：

if(x&1)... 等价于 if(x%2==1)... 判断x是否是奇数。

x>>=1 等价于 x/=2

x<<=1 等价于 x*=2

1<<x 等价于 2的x次方，常用于状压枚举、状压dp。

x&(-x) 为 x 的最低位的 '1' 对应的值，常用于树状数组。

l+r>>1 等价于 (l+r)/2，常用于二分。

其他的还有很多，就不一一列举了。

参考代码（解法2）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll x;
    cin>>x;
    cout<<(x<<30)+x;
}

level.3 F 小红的记谱法

对标cf难度：1200

知识点：模拟

本题最大的难度是读题，题目读懂了其实很简单。

不难发现，'<' 代表降八度，'>'代表升八度。那么用一个变量统计当前八度的情况，然后对应哪个音直接输出即可，后面根据八度的情况来添加对应数量的'.'或者'*'即可。

注：之所以出这么长的题面也是为了让大家适应比赛，众所周知，xcpc的题面有很多又臭又长，而且是全英文题面，大家必须学会在读题的时候迅速找到关键信息并转化为解题的要素。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int cnt=0,i;
    string s;
    cin>>s;
    for(i=0;i<s.length();i++){
        if (s[i]=='>')cnt++;
        else if(s[i]=='<')cnt--;
        else{
            if(s[i]=='C')cout<<1;
            if(s[i]=='D')cout<<2;
            if(s[i]=='E')cout<<3;
            if(s[i]=='F')cout<<4;
            if(s[i]=='G')cout<<5;
            if(s[i]=='A')cout<<6;
            if(s[i]=='B')cout<<7;
            if(cnt>0)for(int j=0;j<cnt;j++)cout<<'*';
            else for(int j=cnt;j<0;j++)cout<<'.';
        }
    }
    cout << endl;
}

level.3 I 爆炸的符卡洋洋洒洒

对标cf难度：1300

知识点：01背包

01背包的变种题。

传统01背包的模型是，每个物品有一个重量和一个价值，问总重量不超过 能取到的最大价值。

而这道题的模型变成了：总重量必须是 的倍数时能取到的最大价值。

解法其实是一样的，不同的是本来要维护前 个物品重量为 的最大值，现在变成了 前 个物品重量模 为 的最大值。这种技巧大家一定要熟练掌握。

转移方程：

这里要注意负数取模的技巧：先转为绝对值小于 的负数，然后加 再模 。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1010][2],dp[1010][1010];
int main(){
    int n,k,i,j;
    cin>>n>>k;
    for(i=1;i<=n;i++)cin>>a[i][0]>>a[i][1];
    for(i=0;i<=n;i++)for(j=0;j<=k;j++)dp[i][j]=-1e16;
    //注意这里的初始化一定要尽可能小！代表是取不到的。
    dp[0][0]=0;
    //前0件物品，显然取到的最大威力为0。此时消耗魔力模p等于0
    for(i=1;i<=n;i++){
        for(j=0;j<k;j++){
            dp[i][j]=dp[i-1][j];
            //这一部分是不取第i个符卡。
            dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i][0]%k+k)%k]+a[i][1]);
            //这一部分是取第i个符卡，那么目前的威力如果模k为j的话，一定是从“前i-1个符卡，威力模k为j-a[i]转移而来”
        }
    }
    if(dp[n][0]<=0)cout<<-1;
    else cout<<dp[n][0];
}

level.3 C 蓝彗星

对标cf难度：1300

知识点：差分，前缀和

给定每个彗星的种类，以及开始的时间。持续时间均为 。问有多少时间能看到蓝彗星看不到红彗星。

看到这个题面很容易想到差分的做法。我们最终的目的是想知道每个时刻有没有蓝彗星和红彗星，由于每颗彗星的时间是给定的一个区间，那么可以直接对值域进行差分，最终求一个前缀和即可。

在操作进行结束以后，我们需要对每个时刻进行枚举，统计只包含蓝彗星不包含红彗星的时刻数量。

请务必注意，本题的值域数组要开到2e5！因为如果最后一颗彗星在1e5的时刻出现，持续了1e5的时刻，那么将持续到2e5秒。只开1e5的话会发生段错误。

差分介绍：

一个数组，有多次操作，每次对某个区间 上每个数加上 ，问最终的数组是什么样子。

我们不妨假设初始的数组全是0。当我们对 区间上每个数加上 以后，这个数组就变成了 0,0,...,0,x,x,...,x,0,0,0

如果我们只对两个位置的数进行操作：，当我们做一次前缀和以后，我们发现，这个数组就变成了我们想要的样子。（前缀和是指，对于新数组 ， 代表a数组中前i项之和。 数组可以通过 得出）。

因此我们可以先对每个区间修改只修改两个数：，在最后做一次前缀和就可以了。这就是差分的基本思想。

进阶：如果这道题， 和 的数据范围是 怎么做？（提示：离散化）

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
string s;
int sum1[202020],sum2[202020];
int main(){
    int i,x;
    cin>>n>>k;
    string s;
    cin>>s;
    for(i=0;i<n;i++){
        cin>>x;
        if(s[i]=='B')sum1[x]++,sum1[x+k]--;
        else sum2[x]++,sum2[x+k]--;
    }
    int res=0;
    for(i=1;i<=2e5;i++)sum1[i]+=sum1[i-1],sum2[i]+=sum2[i-1],res+=(sum1[i]&&!sum2[i]);
    cout<<res;
}

level.4 D 雪色光晕

对标cf难度：1400

知识点：计算几何

本题要求一个固定的点到一条折线的最短距离。由于折线可以看成是很多条线段，所以可以规约成点到线段的最短距离。

（虽然这个是板子，但不建议直接去百度，毕竟赛场上没有百度）

显然，最终的答案一定为以下两种情况的一种：点到直线的最短距离、或点到线段某个端点的最短距离。

什么时候会遇到第二种情况呢？当且仅当点到直线的最短距离所对应的那个点不在线段上。

所以这道题一个最笨的方法就是：先根据线段求出直线两点式，然后求斜率乘积为-1（这样才能垂直）的直线，求出点斜式（还要特判斜率不存在的情况），这样求出两个直线交点，判断交点在不在线段上。如果在的话直接输出初始点到交点距离，否则输出初始点到线段两个端点的最小那个距离。

如果这道题用这种方法来做，计算量将非常大，题目难度也直接飙上1700+。事实上，本题有更简单的做法：

首先如何判断最终能不能取到点到直线距离呢？很简单，把点 和线段两个端点 和 ，这三个点连接成一个三角形，判断该三角形的角 和角 是否是钝角即可。判断钝角可以直接用勾股定理： 则角 为钝角。

然后如何求点到直线的距离呢？也很简单，到直线 的距离即三角形 中边上的高。直接用 即可。而三角形面积可以直接用海伦公式：。

可以发现，换一个做法，原本计算量巨大的题目将极大的减少做题的负担。在赛场上如果发现某题计算量非常大，不妨洗个脸冷静一下，换一个思路可能会豁然开朗。

*请注意，本题如果直接用网上的long long 存点的板子，可能会导致答案错误。因为在计算过程中会出现超过10^9的情况，这样在计算勾股定理的时候再一个平方就会出现爆long long精度的问题。解决办法要么使用__int128或者高精度，要么直接用double存点。 *

参考代码：

#include<bits/stdc++.h>
using namespace std;
struct point{
    double x,y;
    point(double x,double y):x(x),y(y){}
};
double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double ar(point A,point B,point C){ //三点三角形面积
    double a=dis(B,C),b=dis(A,C),c=dis(A,B);
    double p=(a+b+c)/2;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
int jud(point A,point B,point C){       //判断角ABC是钝角
    double a=dis(B,C),b=dis(A,C),c=dis(A,B);

    return b*b>a*a+c*c;
}
double f(point a,point b,point c){  //c点到ab线段的最小距离
    double d1=dis(a,c),d2=dis(b,c);
    if(jud(c,a,b)||jud(c,b,a))
        return min(d1,d2);
    double s=ar(a,b,c);
    double d3=2*s/dis(a,b);
    return min(min(d1,d2),d3);
}
int main(){
    int n,i,j,k;
    double x,y,x0,y0;
    cin>>n;
    cin>>x0>>y0>>x>>y;
    point purple(x,y);
    point red(x0,y0);
    double res=1e16;
    for(i=0;i<n;i++){
        double xt,yt;
        cin>>xt>>yt;
        point temp(red.x+xt,red.y+yt);
        res=min(res,f(red,temp,purple));
        red=temp;
    }
    printf("%.8f",res);
}

level.4 A R

对标cf难度：1500

知识点：双指针，字符串

本题要求有多少子串包含至少 个 'R'字母，且不包含 'P'字母。

这里介绍两种方法解决本题。

方法一：正难则反

我们首先统计有多少个不包含'P'的字符串，然后这些字符串中会有一些是非法的（包含字符'R'数量少于个），把这些字符串的数量减去即可。

具体的操作如下（可结合代码进行理解）：

1.统计不包含'P'的字符串数量（对于每个不含'P'的长度为 的子串，共可以贡献 个子串）

2.先减去不含 'R' 的数量

3.枚举正好有 个'R' 的情况，求子串数量。

总复杂度为

参考代码：

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

string s;
ll pr[202020],ed[202020];      //每个R前面有多少非R非P，后面有多少非R非P
ll sump[202020];
int main(){
    int i,j,k,n;
    cin>>n>>k;
    cin>>s;
    ll res=0,cnt=0;
    for(i=0;i<s.length();i++){//第一步 计算没有P的数量
        sump[i+1]=sump[i];
        if(s[i]!='P')cnt++;
        else{
            sump[i+1]++;
            res+=cnt*(cnt+1)/2;
            cnt=0;
        }
    }
    res+=cnt*(cnt+1)/2;
    cnt=0;
    for(i=0;i<s.length();i++){              //预处理每个'R'前缀的非'R'非'P'的数量
        if(s[i]!='R'&&s[i]!='P')cnt++;
        else {
            res-=cnt*(cnt+1)/2;         //减去长度为0的部分。
            if(s[i]=='R')pr[i]=cnt;
            cnt=0;
        }
    }
    res-=cnt*(cnt+1)/2;
    cnt=0;
    for(i=s.length()-1;i>=0;i--){         //预处理每个'R'后缀的非'R'非'P'的数量
        if(s[i]!='R'&&s[i]!='P')cnt++;
        else {
            if(s[i]=='R')ed[i]=cnt;
            cnt=0;
        }
    }
    vector<int>rs;          //存所有'R'的坐标
    for(i=0;i<s.length();i++){     
        if(s[i]=='R')rs.push_back(i);
    }
    int tong[1010]={};
    for(i=0;i<rs.size();i++){   //把小于k个'R'子串数量减去
        for(j=0;j<k-1;j++){
            if(i<rs.size()-j&&sump[rs[i+j]+1]==sump[rs[i]]){   //需要特判中间没有'P'
                tong[j]+=(pr[rs[i]]+1)*(ed[rs[i+j]]+1);
                res-=(pr[rs[i]]+1)*(ed[rs[i+j]]+1);
            }
        }
    }
    cout<<res;
}

方法二：化整为零

由于最终求的字符串不能包含字母'P'，所以我们可以根据初始的'P'字符先将字符串切成很多小字符串。

然后问题就变成了，求一个字符串，有多少字符至少包含了 个 'R'。

这个问题如果枚举右端点，显然左端点是满足单调性的。可以用二分或者双指针来求出左端点的位置。

总复杂度为

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
string s;
long long res=0;
void gao(string t){    //求字符串t中有多少子串包含至少k个'R'
    int i,j=0,temp=0;
    for(i=0;i<t.length();i++){//枚举右端点，找第一个不合法的左端点
        temp+=t[i]=='R';
        while(j<=i&&temp==k){
            temp-=t[j++]=='R';
        }
        //在这个左端点前面的都是合法的。
        res+=j;

    }
}
int main(){
    int i;
    cin>>n>>k>>s;
    string t="";
    for(i=0;i<n;i++){
        if(s[i]=='P')gao(t),t="";
        else t+=s[i];
    }
    gao(t);
    cout<<res;
}

level.4 J 区间合数的最小公倍数

对标cf难度：1500

知识点：数论

本题需要求区间所有合数的最小公倍数，也就是需要统计区间内每个素数出现的最高的幂。

这里再解释一下这句话的含义。例如， ， ，那么它们的最小公倍数就是 ，也就是每个素数的幂取最大值。

由于本题的数据范围较小（本来是想出到1e7考线性筛的，但考虑到为了萌新，于是放过了 判素数的做法），因此可以直接暴力来做：枚举每个素数，找到落在该区间的最大因子即可。

复杂度

使用线性筛的话复杂度为 ，后面枚举素数因子和前面的做法是一样的，总复杂度为 ，其中 为不超过 的素数个数，约为 ，所以大概复杂度也是 级别。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
int pr[101010];
int cnt=0;
int f(int x){
    int i;
    for(i=2;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}
int main(){
    int i;
    for(i=2;i<=30000;i++){
        if(f(i))pr[cnt++]=i;
    }
    int l,r,j;
    cin>>l>>r;
    ll res=1;
    for(i=0;pr[i]*2<=r;i++){
        for(j=pr[i];j<=r;j*=pr[i]){
            if(r/j==(l-1)/j)break;
        }
        res*=j/pr[i];
        res%=mod;
    }
    if(res==1)cout<<-1;
    else cout<<res;
}

level.5 G 子序列权值乘积

对标cf难度：1800

知识点：枚举，欧拉降幂

一个长度为 的数组，显然有 个非空子序列。如果我们去枚举每个子序列然后求其权值，复杂度将到达恐怖的 ，显然会超时。

我们可以观察到，当排序了以后，如果确定了最大值和最小值，它们中间的数取不取对结果是没有影响的。因此，通过这种方式可以枚举最大值和最小值，中间的部分规约在一起，利用欧拉降幂进行计算，这样复杂度为 ，这样还是不够。

我们看看这些指定了最大值和最小值的区间有什么特点呢？如果区间长度 为 ，那么中间的数有【取】或【不取】两种状态，因此有 的权值贡献。对于长度固定的情况，那么贡献的次数也就固定了。因此这部分可以利用乘法分配律合并起来。

这样我们最终只需要枚举区间长度就可以了。

举个例子，对于数组 [1,3,5,5,6] 而言（不妨设已经排好序了）。

我们枚举长度 2，最终带来的权值收益是

我们枚举长度 3，最终带来的权值收益是

我们枚举长度 4，最终带来的权值收益是

我们枚举长度 5，最终带来的权值收益是

根据公式 ，这些幂相同的底数都是可以合并的。合并之后我们发现，让枚举的长度变大的时候，它们的乘积是可以 进行维护的，因为只除掉了两个数。这部分可以用逆元解决。（如果枚举的长度从大到小，甚至不需要逆元）

那么最终的问题就是怎么解决计算 了。这就是这里要介绍的欧拉降幂：

根据费马小定理，当 和 互素时，有。

那么我们要计算 模 的值，可以先把 写成 的形式，即求 ，前部分模 为1，所以答案就是 。v是什么？正是 对 取模的值。

也就是说，我们要求 ，如果 是个比较大的数（可能是个幂的形式），可以先让 对 取模，是不影响最终答案的正确性的（前提是 和 互素）。这个取模就叫做欧拉降幂。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[200010];
int mod=1e9+7;
ll power(ll a,ll b,ll mod){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x,ll mod){
    return power(x,mod-2,mod);
}
int main(){
    int n,i;
    cin>>n;
    ll res=1,cnt=1,tmp=1;
    for(i=0;i<n;i++){ 
        cin>>a[i];
        res=res*a[i]%mod;
        tmp=tmp*a[i]%mod*a[i]%mod;
    }
    sort(a,a+n);
    ll l=0,r=n-1;
    while(l<n-1){
        tmp=tmp*inv(a[l++],mod)%mod*inv(a[r--],mod)%mod;
        res=res*power(tmp%mod,power(2,l-1,mod-1),mod)%mod%mod;
    }
    for(i=0;i<n;i++)res=res*a[i]%mod;
    cout<<res;
}

level.5 B 进制

对标cf难度：1900

知识点：线段树

这道题属于线段树的一个综合应用，考察大家对线段树原理的理解（如果只会抄板子想必是过不了的）。

首先给没接触过线段树、或者听说过但不了解线段树的同学介绍一下。线段树是一个比较特殊的数据结构。相比于普通暴力的 修改， 查询，或前缀和的 修改， 查询，线段树取了个折中，达成了 修改， 查询。这样就能解决那些一边修改一边查询的题目。

线段树的原理也比较好理解。它的本质其实是一颗二叉树，根节点代表了[1,n]区间。对于每个代表区间 的节点，它的左儿子代表 区间，右儿子代表 区间。其中。

这样让我们修改数组中一个数的时候，我们将处理代表包含该数的区间的一系列节点。同理，当我们进行区间查询时，我们也需要查询一系列节点，找到每个节点对答案的贡献即可。

这道题的难点是进制查询，当我们在合并区间的时候，我们需要注意，假设对于 进制而言，左区间的权值为 ，右区间的权值为 ，那么左右区间合并后，权值应该变成 ，其中 代表右区间的长度。

那么这道题的思路就很清晰了，首先找到查询区间的最大值（用另一个线段树解决），来决定选用几进制。之后在对应的进制线段树上查询该区间的值即可。修改同理，当修改一个数的时候要处理它对所有包含该数的区间所造成的影响。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
string s;
int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
struct bigtree
{
    int l,r,ma;     //区间最大值
};

bigtree bt[410101];
void buildBT(int p,int l,int r){
    bt[p].l=l,bt[p].r=r;
    if(l==r){bt[p].ma=s[l-1]-'0';return;}
    int mid=l+r>>1;
    buildBT(p*2,l,mid);
    buildBT(p*2+1,mid+1,r);
    bt[p].ma=max(bt[p*2].ma,bt[p*2+1].ma);
}
int askma(int p,int l,int r){
    int res=0;
    if(bt[p].l>=l&&bt[p].r<=r){return bt[p].ma;}
    int mid=bt[p].l+bt[p].r>>1;
    if(mid>=l){
        res=max(res,askma(p*2,l,r));
    }
    if(mid+1<=r){
        res=max(res,askma(p*2+1,l,r));
    }
    return res;
}
void changeBt(int p,int id,int x){
    if(bt[p].l==id&&bt[p].r==id){
        bt[p].ma=x;
        return ;
    }
    int mid=bt[p].l+bt[p].r>>1;
    if(mid>=id){changeBt(p*2,id,x);}
    if(mid+1<=id){changeBt(p*2+1,id,x);}
    bt[p].ma=max(bt[p*2].ma,bt[p*2+1].ma);

}
struct jztree       //进制线段树
{
    int l,r;    
    ll res;
};
jztree t[400100][11];
void buildJZ(int p,int l,int r,int x){      //x进制线段树的构建
    t[p][x].l=l,t[p][x].r=r;
    if(l==r){t[p][x].res=s[l-1]-'0';return;}
    int mid=l+r>>1;
    buildJZ(p*2,l,mid,x);
    buildJZ(p*2+1,mid+1,r,x);
    int len=t[p*2+1][x].r-t[p*2+1][x].l+1;
    t[p][x].res=(t[2*p][x].res*power(x,len)%mod+t[2*p+1][x].res)%mod;
}
ll askans(int p,int l,int r,int x){    //查询x进制线段树中，l到r段的值。
    int res1=0,res2=0;
    if(t[p][x].l>=l&&t[p][x].r<=r){return t[p][x].res%mod;}
    int mid=bt[p].l+bt[p].r>>1;
    if(mid>=l){
        res1=askans(p*2,l,r,x);
    }
    if(mid+1<=r){
        res2=askans(p*2+1,l,r,x);
        int len=min(r,t[p*2+1][x].r)-mid;
        return (res1*power(x,len)+res2)%mod;
    }
    else return res1;
}
void addans(int p,int id,int k,int x){  //将x进制线段树上的id位改成k
    if(t[p][x].l==id&&t[p][x].r==id){
        t[p][x].res=k;
        return ;
    }
    int mid=t[p][x].l+t[p][x].r>>1;
    if(mid>=id){addans(p*2,id,k,x);}
    if(mid+1<=id){addans(p*2+1,id,k,x);}
    int len=t[p*2+1][x].r-t[p*2+1][x].l+1;
    t[p][x].res=(t[2*p][x].res*power(x,len)%mod+t[2*p+1][x].res)%mod;
}
signed main(){
    int n,m,i;    
    cin>>n>>m;

    cin>>s;
    buildBT(1,1,n);
    for(i=2;i<=10;i++){
        buildJZ(1,1,n,i);
    }
    while(m--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            changeBt(1,l,r);
            for(i=2;i<=10;i++)addans(1,l,r,i);
        }
        else{
            int ma=askma(1,l,r)+1;
            if(ma==1)ma++;
            cout<<askans(1,l,r,ma)%mod<<'\n';
        }

    }

}

level.6 L 在这冷漠的世界里光光哭哭

对标cf难度：2300

知识点：前缀和，二分

我们先假设这道题数据范围是 ，那么显然可以用 进行预处理：dp[i][j][k][h]代表前i个字符中，有多少子序列为第j、k、h个字母的字符串。这样后面每次查询就可以达成O(1)了。

但这样显然是过不了 的数据的，所以做法需要优化。

我们先做一个这样的前缀和，对于第 个字符是 ，字符串的前 个字符里，包含子序列 "ixj" 的数量是 。注意，这里的 "ixj" 中的 和 分别代表第 个字母和第 个字母。这样的预处理的复杂度是

之后，当我们想要查询区间 内有多少个子序列 abc 时，我们可以这样统计：

首先要把中间的字母 "b" 锁定在 区间。可以通过二分找到区间内第一个 "b"的位置的前一个坐标 和最后一个 "b" 的位置坐标 ，那么 即只包含 区间内的 的子序列 abc的数量。(注意dp方程里的a和c要对应成第几个字母的下标)。

之后我们需要减去不合法的部分。我们要减去的不合法情况有以下三种：

其中，中括号代表 区间。这样，我们还需要做到 查询长度为 2 的子序列。这个当然可以通过 复杂度的预处理做到：

当我们预处理出了 代表前个字符，包含子序列 "jk" 的数量以后，我们查询 中包含多少个 "ab"子序列只需要进行如下操作：

首先用 ，这样就计算出了前个字母比前 个字母多了多少"ab"。之后还需要减去 区间的"a"数量乘以 区间的 "b"数量，这代表了 "a" 落在前部分区间， "b" 落在中间区间的情况，最后就计算出了 区间中 "ab" 子序列的数量。

这样最终问题就得以解决了。总复杂度为

参考代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
ll op[80020][26],sum2[80020][26][26],dp[80020][26][26],ed[80020][26],temp[26][26][26];
vector<int>ids[26];
ll check(int l,int r,int x,int y){
    return sum2[r][x][y]-sum2[l-1][x][y]-op[l-1][x]*(op[r][y]-op[l-1][y]);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,q,i,j,k,x,y,z;
    cin>>n>>q;
    //对于第k个字母是x,那么只取前k个字符x，ixj子序列的数量是dp[k][i][j]。
    //当询问[l,r]区间"abc"数量的时候，我们先用dp[最后一个b][a][c]-dp[第一个b前面的b][a][c]，得到区间的b，配合全段a和c的子序列数量，然后减去取到l左边的a 或者r右边的c的情况。
    string s;
    cin>>s;
    for(i=0;i<26;i++)ids[i].push_back(0);
    for(i=1;i<=n;i++){
        ids[s[i-1]-'a'].push_back(i);
        for(j=0;j<26;j++)op[i][j]=op[i-1][j];
        op[i][s[i-1]-'a']++;
        for(j=0;j<26;j++){
            for(k=0;k<26;k++){
                sum2[i][j][k]=sum2[i-1][j][k];
            }
            sum2[i][j][s[i-1]-'a']+=op[i-1][j];
        }
    }
    for(i=n;i>0;i--){
        for(j=0;j<26;j++)ed[i][j]=ed[i+1][j];
        ed[i][s[i-1]-'a']++;
    }
    for(i=1;i<=n;i++){
        for(j=0;j<26;j++){
            for(k=0;k<26;k++){
                dp[i][j][k]=temp[s[i-1]-'a'][j][k]+=op[i-1][j]*ed[i+1][k];
            }
        }
    }
    while(q--){
        int l,r;
        string t;
        cin>>l>>r>>t;
        int x1=t[0]-'a',x2=t[1]-'a',x3=t[2]-'a';
        if(op[r][x2]-op[l-1][x2]==0){cout<<0<<'\n';continue;}
        int l1=lower_bound(ids[x2].begin(),ids[x2].end(),l)-ids[x2].begin();
        int r1=upper_bound(ids[x2].begin(),ids[x2].end(),r)-ids[x2].begin();
        long long res=dp[ids[x2][r1-1]][x1][x3]-dp[ids[x2][l1-1]][x1][x3];
        cout<<res-op[l-1][x1]*check(l,r,x2,x3)-check(l,r,x1,x2)*ed[r+1][x3]-op[l-1][x1]*(op[r][x2]-op[l-1][x2])*ed[r+1][x3]<<'\n';

    }

}