QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525470#8061. Add or Multiplyquannnguyen2009WA 1ms7812kbC++144.5kb2024-08-20 16:52:092024-08-20 16:52:09

Judging History

你现在查看的是最新测评结果

  • [2024-08-20 16:52:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7812kb
  • [2024-08-20 16:52:09]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N=2e5+5, mod = 1e9+7, inf = 1e18;

int n, q;
int a[N];
int op[N]; // luu op o vi tri i
int g[N][2]; //luu gia tri cac khoang
set<int> st[2]; //luu idx cac khoang
int ans[2];
vector<int> seg;

int binpow(int a, int b) {
    int ans = 1;
    while(b>0) {
        if(b&1) ans = (ans*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return ans;
}

void bld(int node, int l, int r) {
    if(l==r) {
        seg[node] = a[l];
        return;
    }
    int mid = (l+r)>>1;
    bld(node<<1, l, mid); bld(node<<1|1, mid+1, r);
    seg[node] = (seg[node<<1]*seg[node<<1|1])%mod;
}

void upd(int node, int l, int r, int idx, int val) {
    if(l>idx || r<idx) return;
    if(l==r) {
        seg[node] = val;
        return;
    }
    int mid = (l+r)>>1;
    upd(node<<1, l, mid, idx, val); upd(node<<1|1, mid+1, r, idx, val);
    seg[node] = (seg[node<<1]*seg[node<<1|1])%mod;
}

int get(int node, int l, int r, int ql, int qr) {
    if(ql>r || qr<l) return 1;
    if(ql<=l && r<=qr) return seg[node];
    int mid = (l+r)>>1;
    return (get(node<<1, l, mid, ql, qr)*get(node<<1|1, mid+1, r, ql, qr))%mod;
}


signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    char c;
    for (int i=1; i<2*n; i++) {
        cin >> c;
        if(i%2==1) {
            a[i/2+1] = (c-'0');
        } else {
            if(c=='+') op[i/2+1]=0;
            else op[i/2+1]=1;
        }
    }
    seg.resize(4*n+5);
    bld(1, 1, n);

    for (int i=1; i<=n; i++) {
        int idx = i;
        int res = a[idx];
        while(idx<n && op[idx+1]) {
            idx++; res = (res*a[idx])%mod;
        }
        g[i][0] = res;
        st[0].insert(i);
        ans[0] = (ans[0]+res)%mod;
        i = idx;
    }
    for (int i=1; i<=n; i++) {
        int idx = i;
        int res = a[idx];
        while(idx<n && !op[idx+1]) {
            idx++; res = (res*a[idx])%mod;
        }
        g[i][1] = res;
        st[1].insert(i);
        ans[1] = (ans[1]+res)%mod;
        i = idx;
    }

    int t = 0;
    cout << ans[t] << '\n';
    while(q--) {
        char type; cin >> type;
        if(type=='a') {
            t = 1-t;
        } else if(type=='s') {
            int x, y; cin >> x >> y;
            int gx = *prev(st[0].upper_bound(x)), gy = *prev(st[0].upper_bound(y));
            int vx = binpow(a[x], mod-2), vy = binpow(a[y], mod-2);
            ans[0] = (ans[0]-g[gx][0]+mod)%mod; ans[0] = (ans[0]-g[gy][0]+mod)%mod;
            g[gx][0] = (g[gx][0]*vx)%mod; g[gx][0] = (g[gx][0]*a[y]);
            g[gy][0] = (g[gy][0]*vy)%mod; g[gy][0] = (g[gy][0]*a[x]);
            ans[0] = (ans[0]+g[gx][0])%mod; ans[0] = (ans[0]+g[gy][0])%mod;

            gx = *prev(st[1].upper_bound(x)), gy = *prev(st[1].upper_bound(y));
            ans[1] = (ans[1]-g[gx][1]+mod)%mod; ans[1] = (ans[1]-g[gy][1]+mod)%mod;
            g[gx][1] = (g[gx][1]*vx)%mod; g[gx][1] = (g[gx][1]*a[y]);
            g[gy][1] = (g[gy][1]*vy)%mod; g[gy][1] = (g[gy][1]*a[x]);
            ans[1] = (ans[1]+g[gx][1])%mod; ans[1] = (ans[1]+g[gy][1])%mod;
            upd(1, 1, n, x, a[y]); upd(1, 1, n, y, a[x]);
            swap(a[x], a[y]);
        }  else {
            int idx; cin >> idx; idx++;
            int gn = idx, gp = *prev(st[op[idx]].upper_bound(idx-1));
            ans[op[idx]] = (ans[op[idx]]-g[gp][op[idx]]+mod)%mod; ans[op[idx]] = (ans[op[idx]]-g[gn][op[idx]]+mod)%mod;
            g[gp][op[idx]] = (g[gp][op[idx]]*g[gn][op[idx]])%mod; g[gn][op[idx]] = 0;
            ans[op[idx]] = (ans[op[idx]]+g[gp][op[idx]])%mod;
            st[op[idx]].erase(gn);

            gp = *prev(st[!op[idx]].upper_bound(idx));
            int en;
            if(st[!op[idx]].upper_bound(idx)==st[!op[idx]].end()) en=n+1;
            else en = *st[!op[idx]].upper_bound(idx);
            ans[!op[idx]] = (ans[!op[idx]]-g[gp][!op[idx]]+mod)%mod; ans[!op[idx]] = (ans[!op[idx]]-g[idx][!op[idx]]+mod)%mod;
            g[gp][!op[idx]] = get(1, 1, n, gp, idx-1); g[idx][!op[idx]] = get(1, 1, n, idx, en-1);
            ans[!op[idx]] = (ans[!op[idx]]+g[gp][!op[idx]])%mod; ans[!op[idx]] = (ans[!op[idx]]+g[idx][!op[idx]])%mod;
            st[!op[idx]].insert(idx);
        }
        cout << ans[t] << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7812kb

input:

3 4
2+3*4
s 1 2
a
f 2
a

output:

14
11
10
24
9

result:

ok 5 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 5692kb

input:

15 11
8*5*5*5*8*5*5*5*8*5*5*5+1+2+3
f 14
s 15 15
s 1 1
s 15 1
s 1 15
f 13
f 1
a
f 1
f 12
a

output:

1000000006
0
0
0
375000017
0
1000000006
125000014
101
61
62
750000008

result:

wrong answer 10th lines differ - expected: '74', found: '61'