牛客练习赛100题解

A 小红的小桃子

这道题如果数据为1e18，将是个比较难的exgcd题（需要找非负整数解）。不过本题作为签到题，数据为1e5，所以枚举第一种袋子的数量，检测剩余的桃子能否恰好装进第二种袋子即可。
请注意，某种写法（不剪枝）如果不开longlong可能会发生溢出int导致答案错误！

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int mod = 7 + 1e9;
// const int mod = 998244353;
const int N = 3 + 1e5;

int main() {
    int a, b, x;
    cin >> a >> b >> x;
    for (int i = 0; i <= 1e5; ++i) {
        if ((LL)a * i <= x) {
            LL aa = (LL)a * i;
            if ((x - aa) % b == 0) {
                cout << i << ' ' << (x - aa) / b << endl;
                return 0;
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

B 小红的子序列

解法1：dp（by 小沙）

将每个字符的位置，颜色，数字的奇偶各自当做一维信息，这样的话我们就可以得到一个3维的DP数组，然后我们可以维护前个字符的，最后一个选择的数字的颜色和奇偶信息的最大值，然后寻找转移式可以发现为。模拟该过程即可。

#include<iostream>
#include<algorithm>
#include<vector>
using i64 = long long;
int main(){
    std :: cin.tie(nullptr)->std :: ios :: sync_with_stdio(false);
    std :: string ans;
    i64 n;
    std :: cin >> n;
    std :: vector<int> nums(n),dp(4,0);
    for(int i = 0; i < n; i ++){
        std :: cin >> nums[i];
    }
    std :: cin >> ans;
    for(int i = 0; i < n; i ++){
        int x = (ans[i]=='R') * 2 + nums[i] % 2;
        dp[x] = std :: max (dp[x] , dp[x^3]+ nums[i]);
    }
    std :: cout << std :: max({
       dp[0],dp[1],dp[2],dp[3]
    }) << std :: endl;
    return 0;
}

解法2：贪心（by 兰子）

将所有元素分为4类：红奇数、红偶数、蓝奇数、蓝偶数，然后最终的子序列一定是以下两种之一：…………红奇-蓝偶-红奇-蓝偶………… 或者 …………红偶-蓝奇-红偶-蓝奇…………

由于所有数均为正整数，所以贪心的去取，尽可能取大的就行。例如，假设取了个红奇数，那么下一个红奇数前，找到最大的那个蓝偶数。然后再找下一个蓝偶数前最大的红奇数即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;//unsigned
typedef pair<int, int> pii;

int n;
ll arr[200005];
string s;

ll resx(int flag, int b, int r, char co, char bo){
    ll tmp = 0, resa = 0;
    for (int i = 0; i < n; i ++){
        if (flag){
            if (arr[i] % 2 == r && s[i] == co && tmp){
                resa += tmp;
                flag = 0;
                tmp = arr[i];
            }
            else if (arr[i] % 2 == b && s[i] == bo) tmp = max(tmp, arr[i]);
            if (i == n - 1) resa += tmp;
        }
        else {
            if (arr[i] % 2 == r && s[i] == co) tmp = max(tmp, arr[i]);
            else if (arr[i] % 2 == b && s[i] == bo){
                resa += tmp;
                flag = 1;
                tmp = arr[i];
            }
            if (i == n - 1) resa += tmp;
        }
    }
    return resa;
}

void solve(){

}

int main() {
    cin >> n;
    for (int i = 0; i < n ; i ++)
        cin >> arr[i];
    cin >> s;
    // 蓝偶红奇
    ll res = resx(1, 0, 1, 'R', 'B');
    // //红奇蓝偶
    res = max(resx(1, 1, 0, 'B', 'R'), res);
    // //蓝奇红偶
    res = max(resx(1, 1, 0, 'R', 'B'), res);
    // //红偶蓝奇
    res = max(resx(1, 0, 1, 'B', 'R'), res);
    cout << res;
}

C 小红的删数字

本题情况较多，需要讨论所有的情况。

首先我们可以把所有的数位按模3的值分为3类，同一类本质为等价的。由于0不能删除，所以0可以直接忽略。

  1. 如果原数模3为x，那么小红也必须删除一个模3为x的数。

  2. 接下来相当于小紫先手，小紫必须删一个模3为x的数（x为1或2），之后小红则必须删一个模3为(1-x)的数。

#include<bits/stdc++.h>
using namespace std;
int tong[3];
int main(){
    int n,x,i,sum=0;
    string s;
    cin>>s;
    for(i=0;i<s.length();i++){
        if(s[i]-'0')tong[(s[i]-'0')%3]++;
        sum+=s[i]-'0';
    }
    if(!tong[sum%3])return cout<<"yukari",0;    //小红第一步无法删除
    tong[sum%3]--;    
    if(tong[1]==tong[2]&&tong[0])cout<<"kou";    //小红赢的充要条件：当小紫删一个1或者2时，小红必能删一个2或者1。这要求1和2的数量相等，且最后不能恰好删完。
    else cout<<"yukari";
}

D 小红的构造题

我们可以先构造一个这样的字符串"rererererere……"，可以发现，在第一个re后面添加个d，可以稳定增加 个子序列；在第二个re后面添加个d，可以稳定增加 个子序列……以此类推，在第个re后面添加个d，可以稳定增加 个子序列。

用这种方式可以将最终的字符串长度缩短到级别，可以证明，当小于时是一定可以在长度200000以内构造完成的。

#include<bits/stdc++.h>
using namespace std;
int tong[101010];
int main(){
    long long n,i,j,k,p;
    cin>>n;
    if(n==0)return cout<<"d",0;
    for(i=1;i*i*i/6<=n;i++);
    i--;
    for(j=i;j>0;j--){
        tong[j]+=n/(j*(j+1)/2);
        n%=j*(j+1)/2;
    }
    for(j=1;j<=i;j++){
        cout<<"re";
        while(tong[j]--)cout<<"d";
    }

}

E 小红的公倍数

解法1：珂朵莉树（by兰子）

所谓珂朵莉树，即用set维护区间信息，然后暴力合并区间。

本题保证了数据随机，因此不难发现，很容易产生大量区间满足区间内所有数相等的情况，因此我们可以用set来维护这样的区间信息：[l,r]中所有数为x。

当修改一个区间时，我们可以利用二分找到需要合并的区间，然后将set中的需要合并的区间全部删除。这样最终的平均复杂度是，其中为合并区间时维护区间内因子转移的情况，需要一些技巧来减小常数。

#include<bits/stdc++.h>
using namespace std;
#define S_IT set<segment>::iterator
map<int,int>v[20101];
struct segment{
    int l,r;
    map<int,int>fac;
    int res;
    segment(int l,int r):l(l),r(r){}
    segment(int l,int r,map<int,int>fac,int res):l(l),r(r),fac(fac),res(res){}
    bool operator<(const segment x)const{
        return this->l<x.l;
    }

};
set<segment>s;
S_IT split(unsigned int pos)
{
    S_IT it = s.lower_bound(segment(pos,pos));
    if (it != s.end() && it->l == pos)
    return it;
    --it;
    unsigned int l = it->l, r = it->r;
    map<int,int> fac = it->fac;
    int res=(*it).res;
    s.erase(it);
    s.insert(segment(l, pos - 1,fac,res));
    return s.insert(segment(pos, r, fac,res)).first;
}
const int mod=1e9+7;
int power(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=(long long)res*a%mod;
        b>>=1;
        a=(long long)a*a%mod;
    }
    return res;
}
int assign(int l, int r)
{
    S_IT it2 = split(r + 1), it1 = split(l);
    S_IT it=s.upper_bound(segment(l,r));
    it--;
    map<int,int>fac=(*it).fac;
    for (S_IT it = it1; it != it2; ++it)
    {
        for(auto itt:(*it).fac){
            int x=itt.first,y=itt.second;
            if(!fac.count(x))fac[x]=y;
            else{
                fac[x]=max(fac[x],y);
            }
        }
    }
    int res=1;
    for(auto it:fac){
        res=(long long)res*power(it.first,it.second)%mod;
    }
    while(it2!=s.end()&&(*it2).fac==fac)it2++;
    r=(*it2).l-1;
    it=it1;
    it--;
    while((*it).fac==fac)it--;
    it++;
    it1=it;
    l=(*it).l;
    s.erase(it1, it2);
    s.insert(segment(l, r, fac,res));
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int i,j,x,n,q;
    for(i=2;i<=2e4;i++){
        if(v[i].size())continue;
        for(j=i;j<=2e4;j+=i){
            int cnt=0;
            for(int k=i;j%k==0;k*=i,cnt++);
            v[j][i]+=cnt;
        }
    }
    cin>>n>>q;
    for(i=1;i<=n;i++){
        cin>>x;
        segment temp(i,i);
        temp.fac=v[x];
        temp.res=x;
        s.insert(temp);
    }
    segment temp(n+1,n+1);
    s.insert(temp);
    s.insert(segment(0,0));
    while(q--){
        int l,r;
        cin>>l>>r;
        S_IT it=s.upper_bound(segment(l,r));
        it--;
        if((*it).r>r){
            cout<<(*it).res<<'\n';
            continue;
        }
        cout<<assign(l,r)<<'\n';
    }
}

解法2：st表（by Falfa）

由于数据是随机生成的，所以可以每次便利查询的区间以确定所求的lcm的左端与右端。

对于一个区间的lcm可以考虑对质因子分类，<=141的质因子使用34个st表维护，剩下的<20000的质数（约2200个）可以使用前缀和维护，之后使用快速幂乘起来即可。

总时间复杂度 。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
int p[10010];
map<int,int>pid;
int pcnt;
int S;
int a[20010];
int n,q;
int L[20010];
int R[20010];
int cc[20010][2270];
int st[35][20010][20];
int Log2[20010];
ll ksm(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getmx(int x,int l,int r)
{
    int s = Log2[r - l + 1];
    return max(st[x][l][s], st[x][r - (1 << s) + 1][s]);
}
ll calc(int l,int r)
{
    ll res=1;
    for(int i=1;i<=pcnt;i++)
    {
        int c;
        if(i<=S)
            c=getmx(i,l,r);
        else
            c=(cc[r][i]-cc[l-1][i]>0)?1:0;
        if(c)
            res=res*ksm(p[i],c)%mod;
    }
    return res;
}
int main()
{
    for (int i = 2; i <= 20000; ++i)
            Log2[i] = Log2[i / 2] + 1;
    for(int i=2;i<=20000;i++)
    {
        bool ok=1;
        for(int j=2;j*j<=i;j++)
            if(i%j==0)
            {
                ok=0;
                break;
            }
        if(ok)
        {
            p[++pcnt]=i;
            pid[i]=pcnt;
            if(i<=141)
                S=pcnt;
        }
    }
    cin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        L[i]=i;
        R[i]=i;
        for(int j=1;j<=S;j++)
        {
            while(a[i]%p[j]==0)
            {
                cc[i][j]++;
                a[i]/=p[j];
            }
        }
        if(a[i]>1)
        {
            cc[i][pid[a[i]]]++;
        }
    }
    for(int i=1;i<=S;i++)
    {
        for (int j = 1; j <= n; ++j)
            st[i][j][0] = cc[j][i];
        for (int _i = 1; _i <= 17; ++_i)
            for (int j = 1; j + (1 << _i) - 1 <= n; ++j)
                st[i][j][_i] = max(st[i][j][_i - 1], st[i][j + (1 << (_i - 1))][_i - 1]);
    }
    for(int i=S+1;i<=pcnt;i++)
        for(int j=1;j<=n;j++)
            cc[j][i]+=cc[j-1][i];
    while(q--)
    {
        int l,r;
        cin >> l >> r;
        int _l=n+1,_r=0;
        for(int i=l;i<=r;i++)
        {
            _l=min(_l,L[i]);
            _r=max(_r,R[i]);
        }
        printf("%lld\n",calc(_l,_r));
        for(int i=l;i<=r;i++)
        {
            L[i]=_l;
            R[i]=_r;
        }
    }
    return 0;
}

F 小红的食尸鬼

对于这个题目，我们首先能想到的维护区间方法一般都是线段树，分块等方式，我们可以先看一下关于这个问题的原形，即单次查询一个区间得到的值为多少，我们可以发现可以我们写出来一个这样的DP，a为当前血量的食尸鬼数量，ans为已经造成的伤害。

fors(i,l,r+1)
    if(s[i] == 'A'){
        if(a[0] == 0){
            ans += a[2]+a[1];
            a[0] = a[1]; a[1] = a[2]; a[2] = 0;
        }else if(a[0]+a[1] >= 2){
            ans += a[2]+a[1]+1+a[0]+a[1]+a[2];
            a[0] = a[1] = a[2] = 0;
        }else if(a[0] == 1){
            assert(a[1] == 0);
            ans += 1+a[2] + 1;
            a[0] = a[2]; a[2] = 0;
        }
    }else if(s[i] == 'H'){
        if(a[0]+a[1] > 0){
            ans += a[0]+a[1]+a[2]+2;
            a[0] = a[1] = a[2] = 0;
        }else {
            ans += 2;
            a[0] = a[2]; a[2] = 0;
        }
    }else if(s[i] == 'S'){
        a[2]++;
    }

我们可以贪心的想对于有高血量和低血量的食尸鬼首先应该谁先进攻，显然是高血量的先进攻，因为低血量的进攻之后可能会导致被动触发使得高血量的食尸鬼少进攻一次。

现在我们需要用一个数据结构来维护这个dp的转移方程，加上这个题还存在修改操作，所以我们可以所以我们采用线段树维护DP转移方程。

对于本题线段树来说，他是单点修改，区间查询，也就是说明我们只需要维护区间与区间之间的合并操作即可。

对于区间的合并操作，我们发现实际上1血食尸鬼的数量虽然可以大于两个，但是对于指令来说，他们等价于存在两个，也就是说我们只需要维护关于上场剩余血食尸鬼的数量即可，如果数量大于，其状态于等于一直，但任需要维护数量。但我们可以将状态无限多的食尸鬼场面划分为种状态，随后我们记录对于对于一个初始状态为的初始场面进入一个区间完成操作后，会剩余多少食尸鬼，他们的血量是多少，一个关于食尸鬼数量的一个伤害函数。且通过该方法，我们可以在两个区间合并的时候快速计算出经过前一段区间会留下什么样的状态，他在进入后一段区间之后该从那一个状态开始，最后留下的状态是什么，即可完成合并操作。

对于两两合并操作，我们每次需要的时间时间复杂度，对于单点修改，每次修改一个位置的信息都需要合并次，一共有次操作。

所以整体的时间复杂度为。也就是大常数。

#include <bits/stdc++.h>
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
using namespace std;
typedef long long ll;
inline ll read()
{
    char ch;ll x=0;bool f=true;
    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
    return f?x:-x;
}
const int N=1e5+7;
struct node{
    int edx[27][4],ed[27][4],val[27][4];
    void init(){
        memset(edx,0,sizeof edx);
        memset(ed,0,sizeof ed);
        memset(val,0,sizeof val);
    }
}tr[N<<2];
char s[N];
#define lson o<<1
#define rson o<<1|1
#define mid (l+r>>1)
int getid(int id,int *edx,int *ed){
    int x[4]={0},ans[4]={0},res=0;
    for(int i=3;i;i--)x[i]=id%3,id/=3;
    for(int i=1;i<=3;i++)ans[i]=x[edx[i]]+ed[i];
    for(int i=1;i<=3;i++)res=res*3+min(ans[i],2);
    return res;
}
void upnode(node &v,node &a,node &b){
    v.init();
    for(int i=0;i<27;i++){
        int idend=getid(i,a.edx[i],a.ed[i]);
        v.val[i][0]=a.val[i][0]+b.val[idend][0];
        for(int j=1;j<=3;j++)v.val[i][0]+=a.ed[i][j]*b.val[idend][j];
        for(int j=1;j<=3;j++)v.val[i][j]=a.val[i][j];
        for(int j=1;j<=3;j++)if(a.edx[i][j]!=0)v.val[i][a.edx[i][j]]+=b.val[idend][j];
        for(int j=1;j<=3;j++)v.edx[i][j]=a.edx[i][b.edx[idend][j]];
        for(int j=1;j<=3;j++)v.ed[i][j]=b.ed[idend][j]+a.ed[i][b.edx[idend][j]];
    }
}
void get(node &x,char ch){
    x.init();
    if(ch=='S'){
        for(int i=0;i<27;i++){
            x.ed[i][3]++;
            for(int j=1;j<=3;j++)x.edx[i][j]=j;
        }
    }else if(ch=='A'){
        for(int i=0;i<27;i++){
            if(i==0)for(int j=1;j<=3;j++)x.edx[i][j]=j;
            else if(i<=8){
                for(int j=1;j<=2;j++)x.edx[i][j]=j+1;
                for(int j=1;j<=3;j++)x.val[i][j]=1;
            }
            else if(i<=11){
                x.edx[i][1]=3;
                for(int j=0;j<=3;j++)x.val[i][j]=1;
            }
            else x.val[i][0]=x.val[i][1]=1,x.val[i][2]=x.val[i][3]=2;
        }
    }else {
        for(int i=0;i<27;i++){
            if(i<=2)x.edx[i][1]=3,x.val[i][0]=2,x.val[i][1]=x.val[i][2]=1;
            else x.val[i][0]=2,x.val[i][1]=x.val[i][2]=x.val[i][3]=1;
        }
    }
}
void build(int o,int l,int r){
    if(l==r)return get(tr[o],s[l]);
    build(lson,l,mid),build(rson,mid+1,r);
    upnode(tr[o],tr[lson],tr[rson]);
}
void add(int o,int l,int r,int x,char ch){
    if(l==r)return get(tr[o],ch);
    if(x<=mid)add(lson,l,mid,x,ch);
    else add(rson,mid+1,r,x,ch);
    upnode(tr[o],tr[lson],tr[rson]);
}
node ask(int o,int l,int r,int L,int R){
    if(l==L&&r==R)return tr[o];
    if(R<=mid)return ask(lson,l,mid,L,R);
    else if(L>mid)return ask(rson,mid+1,r,L,R);
    else {
        node x,a=ask(lson,l,mid,L,mid),b=ask(rson,mid+1,r,mid+1,R);
        x.init();
        upnode(x,a,b);
        return x;
    }
}
int main(){
       int n=read(),m=read();
    assert(1<=n&&n<=1e5);
    assert(1<=m&&m<=1e5);
       scanf("%s",s+1);
    for(int i=1;i<=n;i++)assert(s[i]=='S'||s[i]=='A'||s[i]=='H');
       build(1,1,n);
       while(m--){
           int op=read();
        assert(op==1||op==2);
           if(op==1){
               int l=read(),r=read();
               node a=ask(1,1,n,l,r);
               printf("%d\n",a.val[0][0]);
           }else {
               int x=read();char ch;
               scanf("%c",&ch);
            assert(ch=='S'||ch=='A'||ch=='H');
               add(1,1,n,x,ch);
           }
       }
}

放一份jiangly的代码（被jiangly爆杀了

#include <bits/stdc++.h>

using i64 = long long;
template<class Info,
    class Merge = std::plus<Info>>
struct SegmentTree {
    const int n;
    const Merge merge;
    std::vector<Info> info;
    SegmentTree(int n) : n(n), merge(Merge()), info(4 << std::__lg(n)) {}
    SegmentTree(std::vector<Info> init) : SegmentTree(init.size()) {
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = merge(info[2 * p], info[2 * p + 1]);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y));
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
};

// 0.  a1 >= 2
// 1.  a1 = 1, a2 >= 1
// 2.  a1 = 1, a2 = 0, a3 >= 2
// 3.  a1 = 1, a2 = 0, a3 = 1
// 4.  a1 = 1, a2 = 0, a3 = 0
// 5.  a1 = 0, a2 >= 2
// 6.  a1 = 0, a2 = 1, a3 >= 1
// 7.  a1 = 0, a2 = 1, a3 = 0
// 8.  a1 = 0, a2 = 0, a3 >= 2
// 9.  a1 = 0, a2 = 0, a3 = 1
// 10. a1 = a2 = a3 = 0

struct Trans {
    int type;
    int damage;
    int attack[3];
    int shift;
    int place[3];
};

Trans operator+(const Trans &a, const Trans &b) {
    Trans c;
    c.type = b.type;
    c.damage = a.damage + b.damage;
    c.shift = std::min(3, a.shift + b.shift);
    for (int i = 0; i < 3; i++) {
        c.attack[i] = a.attack[i];
        c.damage += b.attack[i] * a.place[i];
        if (i - a.shift >= 0) {
            c.attack[i] += b.attack[i - a.shift];
        }
    }
    for (int i = 0; i < 3; i++) {
        c.place[i] = b.place[i];
        if (i - b.shift >= 0) {
            c.place[i - b.shift] += a.place[i];
        } else {
            c.damage += a.place[i];
        }
    }
    return c;
}

struct Info {
    Trans trans[11];
    Info() {
        for (int i = 0; i < 11; i++) {
            trans[i] = { i, 0, { 0, 0, 0 }, 0, { 0, 0, 0 } };
        }
    }
} S, A, H;

Info getInfo(char c) {
    if (c == 'S') {
        return S;
    } else if (c == 'A') {
        return A;
    } else {
        return H;
    }
}

Info operator+(const Info &a, const Info &b) {
    Info c;
    for (int i = 0; i < 11; i++) {
        c.trans[i] = a.trans[i] + b.trans[a.trans[i].type];
    }
    return c;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    S.trans[0]  = { 0, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[1]  = { 1, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[2]  = { 2, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[3]  = { 2, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[4]  = { 3, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[5]  = { 5, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[6]  = { 6, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[7]  = { 6, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[8]  = { 8, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[9]  = { 8, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };
    S.trans[10] = { 9, 0, { 0, 0, 0 }, 0, { 0, 0, 1 } };

    A.trans[0]  = { 10, 1, { 0, 1, 1 }, 3, { 0, 0, 0 } };
    A.trans[1]  = { 10, 1, { 0, 1, 1 }, 3, { 0, 0, 0 } };
    A.trans[2]  = { 0, 1, { 0, 1, 1 }, 2, { 0, 0, 0 } };
    A.trans[3]  = { 4, 1, { 0, 1, 1 }, 2, { 0, 0, 0 } };
    A.trans[4]  = { 10, 1, { 0, 1, 1 }, 2, { 0, 0, 0 } };
    A.trans[5]  = { 0, 0, { 0, 1, 1 }, 1, { 0, 0, 0 } };
    A.trans[6]  = { 1, 0, { 0, 1, 1 }, 1, { 0, 0, 0 } };
    A.trans[7]  = { 4, 0, { 0, 1, 1 }, 1, { 0, 0, 0 } };
    A.trans[8]  = { 5, 0, { 0, 1, 1 }, 1, { 0, 0, 0 } };
    A.trans[9]  = { 7, 0, { 0, 1, 1 }, 1, { 0, 0, 0 } };
    A.trans[10] = { 10, 0, { 0, 1, 1 }, 1, { 0, 0, 0 } };

    H.trans[0]  = { 10, 2, { 0, 0, 0 }, 3, { 0, 0, 0 } };
    H.trans[1]  = { 10, 2, { 0, 0, 0 }, 3, { 0, 0, 0 } };
    H.trans[2]  = { 10, 2, { 0, 0, 0 }, 3, { 0, 0, 0 } };
    H.trans[3]  = { 10, 2, { 0, 0, 0 }, 3, { 0, 0, 0 } };
    H.trans[4]  = { 10, 2, { 0, 0, 0 }, 3, { 0, 0, 0 } };
    H.trans[5]  = { 10, 2, { 0, 0, 0 }, 3, { 0, 0, 0 } };
    H.trans[6]  = { 10, 2, { 0, 0, 0 }, 3, { 0, 0, 0 } };
    H.trans[7]  = { 10, 2, { 0, 0, 0 }, 3, { 0, 0, 0 } };
    H.trans[8]  = { 0, 2, { 0, 0, 0 }, 2, { 0, 0, 0 } };
    H.trans[9]  = { 4, 2, { 0, 0, 0 }, 2, { 0, 0, 0 } };
    H.trans[10] = { 10, 2, { 0, 0, 0 }, 2, { 0, 0, 0 } };

    int n, q;
    std::cin >> n >> q;

    std::string s;
    std::cin >> s;
    SegmentTree<Info> seg(n);
    for (int i = 0; i < n; i++) {
        seg.modify(i, getInfo(s[i]));
    }

    for (int i = 0; i < q; i++) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int l, r;
            std::cin >> l >> r;
            l--;
            std::cout << seg.rangeQuery(l, r).trans[10].damage << "\n";
        } else {
            int x;
            char c;
            std::cin >> x >> c;
            x--;
            seg.modify(x, getInfo(c));
        }
    }

    return 0;
}
全部评论
诸位大佬 D题i*i*i/6是嘛意思呀
1 回复 分享
发布于 2022-06-12 19:39
%%%兰子小沙tql
1 回复 分享
发布于 2022-06-10 22:44
%%%兰子tql
1 回复 分享
发布于 2022-06-10 21:52
%%%小沙tql
1 回复 分享
发布于 2022-06-10 21:43
诸位大佬 D题i*i*i/6是嘛意思呀
点赞 回复 分享
发布于 2022-07-14 09:22
F/tuu
点赞 回复 分享
发布于 2022-06-11 07:03
E题的第二种解法。 修改转成查询用线段树维护每个位置左端位置和右端位置可以变成 q*logn。 大于sqrt(2w)的质数可以用莫队。  这样不是随机的也一样。 复杂度是O(q*logn + q*34*logn + (q+n)*sqrt(n))。
点赞 回复 分享
发布于 2022-06-11 00:12

相关推荐

10-24 16:03
黑龙江外国语学院 大数据开发工程师
点赞 评论 收藏
分享
10-23 20:13
门头沟学院 Java
点赞 评论 收藏
分享
09-13 08:07
南京晓庄学院 财务
点赞 评论 收藏
分享
09-22 22:22
中山大学 Java
鹅孝子 all in 转正的下场
整个秋招没有浪费一丁点躺的时间去背八股刷力扣，纯躺了
乌鱼子萨奇：羡慕你啊，直接转正了，都不用经历秋招的炼狱，但是你少经历了很多痛苦的事情啊
点赞 评论 收藏
分享
头像
今天 09:15
门头沟学院 人工智能
我的家人们，我真的没有被骗
2024年12月31日，我的offer给到了我的邮箱，同步，我也把这个喜讯给到我的家人们。当我爹妈看到我的薪资时：“你是不是被骗了哦，是不是哦？”“你莫去搞诈骗啊。”“他是不是多打了一个0哦。”超乎他们认知的工资，让他们忽略了偌大的菊花标志，认为我是一个心思单纯的小孩，质疑我的秋招结果。当我再三解释之后，我妈居然还在担心。“这么高的工资，工作压力不晓得好大。”“你要不还是留在重庆嘛，深圳那些地方压力大得很。”不过我在家里的话语权自我大二外出打拼一来，逐渐获得了家庭的主导权，我认准的事情，父母也没有办法干扰到我。经常也有人再问，我到底是干什么的。我是研发族-云服务技术-....-解决方案架构师我...
点赞 评论 收藏
分享
评论
14
2
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 牛客树洞，我想对你说 #
21299次浏览 139人参与
# 选择和努力，哪个更重要？ #
111544次浏览 858人参与
# 快手技术岗信息交流阵地 #
9123次浏览 63人参与
# 大学最后一个寒假，我想…… #
56428次浏览 618人参与
# 哪些公司校招卡第一学历 #
215766次浏览 770人参与
# 求职中的尴尬瞬间 #
8591次浏览 67人参与
# 应届生被毁约被毁意向了怎么办 #
48812次浏览 282人参与
# 除了主业以外，你还有哪些其他收入？ #
32909次浏览 299人参与
# 牛客周边新品开箱 #
12447次浏览 91人参与
# 牛友的志愿填报指南 #
37438次浏览 189人参与
# 25届非技术实习投递记录 #
133053次浏览 993人参与
# 如何KTV领导 #
74942次浏览 509人参与
# 为什么国企只招应届生 #
209821次浏览 1241人参与
# 硬件人的春招flag #
53743次浏览 435人参与
# 怎么给家人解释你的工作？ #
16630次浏览 97人参与
# 机械人避雷的岗位/公司 #
31026次浏览 250人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
138679次浏览 886人参与
# 你最近一次加班是什么时候？ #
94915次浏览 518人参与
# 得物app工作体验 #
31003次浏览 69人参与
# 国企还是互联网，你怎么选？ #
173642次浏览 1318人参与
# 一句话证明你还在找工作 #
8549次浏览 90人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务