社区讨论

一个问题

UUNNN
P6373「StOI-1」IOI计数参与者 2已保存回复 10

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@mhjrycz4
此快照首次捕获于
2025/11/04 07:31
4 个月前
此快照最后确认于
2025/11/04 07:31
4 个月前
查看原帖
Rt，请问下面两个代码有区别吗，为什么前者样例二过不了但是后者就可以 AC？
CPP
#include <iostream>
#include <cstdio>
#include <string>
#define pl(p) p << 1
#define pr(p) (p << 1) | 1
using namespace std;
typedef long long ll;
const ll MAXN = 5e5 + 5;
struct node{
    ll l, r;
    ll i, o, io /*i o*/, oi /*o i*/, ioi /*io i & i oi*/;
    node(){
        i = 0LL;
        o = 0LL;
        io = 0LL;
        oi = 0LL;
        ioi = 0LL;
    }
}ltr[MAXN * 4LL];
ll n, m;
string s;
node getclear(node x){
    node gc;
    gc.l = x.l;
    gc.r = x.r;
    gc.i = 0LL;
    gc.o = 0LL;
    gc.io = 0LL;
    gc.oi = 0LL;
    gc.ioi = 0LL;
    return gc;
}
void pushup(ll p){
    ltr[p] = getclear(ltr[p]);
    ltr[p].i = ltr[pl(p)].i + ltr[pr(p)].i;
    ltr[p].o = ltr[pl(p)].o + ltr[pr(p)].o;
    ltr[p].io = ltr[pl(p)].io + ltr[pr(p)].io + ltr[pl(p)].i * ltr[pr(p)].o;
    ltr[p].oi = ltr[pl(p)].oi + ltr[pr(p)].oi + ltr[pl(p)].o * ltr[pr(p)].i;
    ltr[p].ioi = ltr[pl(p)].ioi + ltr[pr(p)].ioi + ltr[pl(p)].io * ltr[pr(p)].i + ltr[pl(p)].i * ltr[pr(p)].oi;
    return ;
}
void build(ll p, ll l, ll r){
    ltr[p] = getclear(ltr[p]);
    ltr[p].l = l;
    ltr[p].r = r;
    if(l == r){
        if(s[l] == 'I') ltr[p].i = 1LL;
        else if(s[l] == 'O') ltr[p].o = 1LL;
        return ;
    }
    ll mid = (l + r) >> 1LL;
    build(pl(p), l, mid);
    build(pr(p), mid + 1LL, r);
    pushup(p);
    return ;
}
void change(ll p, ll x, char c){
    if(ltr[p].l == ltr[p].r && ltr[p].l == x){
        ltr[p] = getclear(ltr[p]);
        if(c == 'I') ltr[p].i = 1LL;
        else if(c == 'O') ltr[p].o = 1LL;
        return ;
    }
    ll mid = (ltr[p].l + ltr[p].r) >> 1LL;
    if(x <= mid) change(pl(p), x, c);
    else change(pr(p), x, c);
    pushup(p);
    return ;
}
node ask(ll p, ll l, ll r){
    if(l <= ltr[p].l && r >= ltr[p].r) return ltr[p];
    ll mid = (ltr[p].l + ltr[p].r) >> 1LL;
    node sum;
    sum = getclear(sum);
    if(l <= mid){
        node tmp = ask(pl(p), l, r);
        sum.i = sum.i + tmp.i;
        sum.o = sum.o + tmp.o;
        sum.io = sum.io + tmp.io + sum.i * tmp.o;
        sum.oi = sum.oi + tmp.oi + sum.o * tmp.i;
        sum.ioi = sum.ioi + tmp.ioi + sum.io * tmp.i + sum.i * tmp.oi;
    }
    if(r > mid){
        node tmp = ask(pr(p), l, r);
        sum.i = sum.i + tmp.i;
        sum.o = sum.o + tmp.o;
        sum.io = sum.io + tmp.io + sum.i * tmp.o;
        sum.oi = sum.oi + tmp.oi + sum.o * tmp.i;
        sum.ioi = sum.ioi + tmp.ioi + sum.io * tmp.i + sum.i * tmp.oi;
    }
    return sum;
}
int main()
{
    cin >> n >> m;
    cin >> s;
    s = "*" + s;
    build(1LL, 1LL, n);
    while(m--){
        ll opt;
        cin >> opt;
        if(opt == 1LL){
            ll x;
            char c;
            cin >> x >> c;
            change(1LL, x, c);
        }
        else if(opt == 2LL){
            ll l, r;
            node ans;
            ans = getclear(ans);
            cin >> l >> r;
            ans = ask(1LL, l, r);
            printf("%lld\n", ans.ioi);
        }
    }
    return 0;
}
记录
CPP
#include <iostream>
#include <cstdio>
#include <string>
#define pl(p) p << 1
#define pr(p) (p << 1) | 1
using namespace std;
typedef long long ll;
const ll MAXN = 5e5 + 5;
struct node{
    ll l, r;
    ll i, o, io /*i o*/, oi /*o i*/, ioi /*io i & i oi*/;
    node(){
        i = 0LL;
        o = 0LL;
        io = 0LL;
        oi = 0LL;
        ioi = 0LL;
    }
}ltr[MAXN * 4LL];
ll n, m;
string s;
node getclear(node x){
    node gc;
    gc.l = x.l;
    gc.r = x.r;
    gc.i = 0LL;
    gc.o = 0LL;
    gc.io = 0LL;
    gc.oi = 0LL;
    gc.ioi = 0LL;
    return gc;
}
node toge(node a, node b){
    node res;
    res = getclear(res);
    res.i = a.i + b.i;
    res.o = a.o + b.o;
    res.io = a.io + b.io + a.i * b.o;
    res.oi = a.oi + b.oi + a.o * b.i;
    res.ioi = a.ioi + b.ioi + a.io * b.i + a.i * b.oi;
    return res;
}
void pushup(ll p){
    ltr[p] = getclear(ltr[p]);
    ltr[p] = toge(ltr[pl(p)], ltr[pr(p)]);
    return ;
}
void build(ll p, ll l, ll r){
    ltr[p] = getclear(ltr[p]);
    ltr[p].l = l;
    ltr[p].r = r;
    if(l == r){
        if(s[l] == 'I') ltr[p].i = 1LL;
        else if(s[l] == 'O') ltr[p].o = 1LL;
        return ;
    }
    ll mid = (l + r) >> 1LL;
    build(pl(p), l, mid);
    build(pr(p), mid + 1LL, r);
    pushup(p);
    return ;
}
void change(ll p, ll x, char c){
    if(ltr[p].l == ltr[p].r && ltr[p].l == x){
        ltr[p] = getclear(ltr[p]);
        if(c == 'I') ltr[p].i = 1LL;
        else if(c == 'O') ltr[p].o = 1LL;
        return ;
    }
    ll mid = (ltr[p].l + ltr[p].r) >> 1LL;
    if(x <= mid) change(pl(p), x, c);
    else change(pr(p), x, c);
    pushup(p);
    return ;
}
node ask(ll p, ll l, ll r){
    if(l <= ltr[p].l && r >= ltr[p].r) return ltr[p];
    ll mid = (ltr[p].l + ltr[p].r) >> 1LL;
    node sum;
    sum = getclear(sum);
    if(l <= mid){
        node tmp = ask(pl(p), l, r);
        sum = toge(sum, tmp);
    }
    if(r > mid){
        node tmp = ask(pr(p), l, r);
        sum = toge(sum, tmp);
    }
    return sum;
}
int main()
{
    cin >> n >> m;
    cin >> s;
    s = "*" + s;
    build(1LL, 1LL, n);
    while(m--){
        ll opt;
        cin >> opt;
        if(opt == 1LL){
            ll x;
            char c;
            cin >> x >> c;
            change(1LL, x, c);
        }
        else if(opt == 2LL){
            ll l, r;
            node ans;
            ans = getclear(ans);
            cin >> l >> r;
            ans = ask(1LL, l, r);
            printf("%lld\n", ans.ioi);
        }
    }
    return 0;
}
记录

回复

共 10 条回复，欢迎继续交流。

正在加载回复...