牛客练习赛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

相关推荐

14 2 评论
分享
牛客网
牛客企业服务