Skip to content

11627: 【原1627】不可能数据结构

题目

题目描述

author: Chika 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1627 ## Description

造一道数据结构题是一件很累的事情。

即使是有了坚固的数据结构造题程式，出题人仍然不能够一劳永逸。

问题大概出在，造题程式并不总能生成对的题。

比如，造题程式无意产生了一道出题人认为不可做题，这便成了一道错题。

嘛，出了错题，其实也是没有关系的。出题人可以拿着暴力程序跑一个星期来跑出所需要的测试数据。

一个星期跑不出来就延期一个星期机考好了，至于算法和讲题嘛，也就看看现场ac代码现学现卖咯？

可能对你们来说很不幸的现实是，这道题似乎是个错题。

给你一个初始n个元素的序列，有两种操作。

  1. 将区间里的每一个数写成十进制\(a_1a_2a_3\cdots a_k)\)，然后把这个数变成\(\prod_{i=1}^{k}(a_i + 1) - 1\)
  2. 询问一个区间里面所有数的和。

于是，你能想尽办法，通过这道不可能数据结构题吗？

Input Format

第一行是一个数\(n\)，表示这个序列的长度

接下来一行有\(n\)个数，描述这个数列。

接下来是一个数\(q\)，描述事件个数

对于之后的\(q\)行，每行描述一个事件。

  • 0 x y，将\([x, y]\)里面的每一个数做上述变形。
  • 1 x y，询问\([x, y]\)里面所有数的和。

Output Format

对于每一个询问操作，输出对应的答案。

Sample Input

3
1 2 3
1
1 2 3

Sample Output

5

Limits

  • 对于60%的数据，\(n \leq 500\)
  • 对于100%的数据，\(n \leq 100000\)，\(0 \leq a_i \leq 10^9\)

zqy2018's solution 

/*
    Hint: try brute force
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[100005], lis[100005], tot;
ll c[100005] = {0};
set<int> st;
inline int lowbit(int x){
    return x & (-x);
}
void add(int r, int k){
    while (r <= n)
        c[r] += k, r += lowbit(r);
}
ll query(int r){
    ll res = 0;
    while (r > 0)
        res += c[r], r -= lowbit(r);
    return res;
}
int calc(int x){
    int res = 1;
    while (x > 0)   
        res *= (x % 10 + 1), x /= 10;
    --res;
    return res;
}
void init(){
    n = read();
    for (int i = 1; i <= n; ++i){
        a[i] = read();
        add(i, a[i]);
        if (calc(a[i]) != a[i]) st.insert(i);
    }
}
void solve(){
    int q = read();
    while (q--){
        int opt = read(), x = read(), y = read();
        if (opt == 0){
            tot = 0;
            auto iter = st.lower_bound(x);
            while (iter != st.end()){
                if (*iter > y) break;
                int pos = *iter, t = a[pos];
                int to = calc(t);
                if (t == to) lis[++tot] = pos;
                else add(pos, to - t), a[pos] = to;
                ++iter;
            }
            for (int i = 1; i <= tot; ++i)
                st.erase(lis[i]);
        }else {
            printf("%lld\n", query(y) - query(x - 1));
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}