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

相关推荐

11-26 01:07
香港大学 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:19
点赞 评论 收藏
分享
今天 13:00
已编辑
北京戏曲艺术职业学院 硬件开发
华为报批
和对接人沟通确认意向，地点等信息，属于第一批。已经报批，结果会在12.5号前公布，最晚推迟两个周。武汉终端硬件电源，bg985本。苦等两个月，一定要给我发offer更新：已经开奖成功🌹
沉淀一会：1.同学你面试评价不错，概率很大，请耐心等待； 2.你的排名比较靠前，不要担心，耐心等待； 3.问题不大，正在审批，不要着急签其他公司，等等我们！ 4.预计9月中下旬，安心过节； 5.下周会有结果，请耐心等待下； 6.可能国庆节前后，一有结果我马上通知你； 7.预计10月中旬，再坚持一下； 8.正在走流程，就这两天了； 9.同学，结果我也不知道，你如果查到了也告诉我一声； 10.同学你出线不明朗，建议签其他公司保底！ 11.同学你找了哪些公司，我也在找工作。
点赞 评论 收藏
分享
11-25 12:32
长春理工大学 金融分析师
重生之我变成了小学生
家人们！大离谱事件发生了！早上我被我妈叫醒，我就想，我都是一个20多岁的成年人了，怎么早上还叫我起床！所以我就没理然后我的屁股遭到了一记重击！等等……这感觉怎么似曾相识……难道是……难道是……我猛然睁开眼睛！日历上显示现在是，，2012年！！我穿越了！！我呆呆地坐在床上，看着我现在幼小的身体，我妈拎着笤帚站在床头，看我愣着出神，超用力地推了一下我的头，顺势我倒在了床上……“你看看这都几点了还不起？不想上学啦！不想上学早说，跟着你爸干活去！别给我浪费钱！”说罢她“嘭”地把门关上离开了难道说……我真的回到了小学？我迅速爬起来，把自己浑身上下摸了一遍，给了自己两耳刮子，啧……真疼啊我，真的回到小学了...
shanxin233：直接买比特币
非技术求职现状
点赞 评论 收藏
分享
评论
14
2
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
236934次浏览 2039人参与
# 机械求职避坑tips #
23526次浏览 249人参与
# 北方华创开奖 #
66920次浏览 552人参与
# 25届秋招总结 #
408952次浏览 4101人参与
# 25届机械人为了秋招做了哪些准备？ #
26198次浏览 363人参与
# 地方国企笔面经互助 #
6892次浏览 17人参与
# 阿里云管培生offer #
62112次浏览 1759人参与
# ai智能作图 #
28080次浏览 331人参与
# 虾皮求职进展汇总 #
89854次浏览 731人参与
# 实习，投递多份简历没人回复怎么办 #
2439982次浏览 34738人参与
# 软件开发投递记录 #
1481087次浏览 23946人参与
# 我的实习求职记录 #
6131219次浏览 84012人参与
# 我在牛爱网找对象 #
74772次浏览 554人参与
# 发工资后，你做的第一件事是什么 #
8908次浏览 41人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
82943次浏览 599人参与
# 机械人怎么评价今年的华为 #
157831次浏览 1351人参与
# 京东求职进展汇总 #
512656次浏览 4678人参与
# 如果可以，你希望哪个公司来捞你 #
33647次浏览 195人参与
# 你觉得通信/硬件有必要实习吗？ #
54751次浏览 697人参与
# 歌尔求职进展汇总 #
42882次浏览 294人参与
# 在职场上，你最讨厌什么样的同事 #
6007次浏览 91人参与
# 如果再来一次，你还会选择这个工作吗？ #
115129次浏览 1137人参与
牛客网
牛客企业服务